題目

給定兩個整數(shù)分別代表分子和分母，以字符串的方式返回分數(shù)，如果分數(shù)部分重復(fù)，將重復(fù)的部分括在括號中。
如果有多個答案，返回任意一個。

解析

轉(zhuǎn)換成分數(shù)，第一步應(yīng)該將進行整數(shù)除法運算，得到整數(shù)商 integer 和余數(shù) extra。如果余數(shù)為 0 ，直接返回整數(shù)，否則繼續(xù)計算小數(shù)部分。
if extra recurring
find recurring and return
extra10 / numerator = quotient
extra10 % numerator = newextra
就是將分子除以分母，得到商和余數(shù)，余數(shù)進位后作為分子再次做除法。如果余數(shù)開始重復(fù)，就說明商也開始重復(fù)了。

偽代碼

integer = denominator / numerator
extra = denominator / numerator
if extra = 0
  return integer

for extra != 0
  if extra is recurring
    return integer.recurring
  quotient = extra*10 / numerator
   recurring[extra] = quotient idx
   extra = extra*10 % numerator

return integer.nofraction

代碼

func fractionToDecimal(numerator int, denominator int) string {
    var rst string
    neg := false
    var fracs []int
    fracm := make(map[int]int)
    fracl := 0
    if numerator < 0 {
        neg = !neg
        numerator = ^numerator+1
    }
    if denominator < 0 {
        neg = !neg
        denominator = ^denominator+1
    }
    
    integer := numerator / denominator
    numerator = numerator % denominator
    if numerator == 0 {
        rst =  isinteger(integer)
        if integer == 0 {
            return rst
        }
        goto RESULT
    }
    
    for numerator != 0 {
        if k, ok := fracm[numerator]; ok {
            rst =  isrecurring(integer, fracs, k)
            goto RESULT
        }
        quotient := numerator*10 / denominator
        fracs = append(fracs, quotient)
        fracl++
        fracm[numerator] = fracl-1
        
        numerator = numerator*10 % denominator
    }
    rst = isnorecurring(integer, fracs)
RESULT:
    if neg {
        rst = "-" + rst
    }
    return rst
    
}


func isinteger(integer int) string {
    return int2string(integer)
}

func isrecurring(integer int, fracs []int, rec int) string {
    return int2string(integer) + "." + fracs2string(fracs[:rec]) + "(" + fracs2string(fracs[rec:]) + ")"
}

func isnorecurring(integer int, fracs []int) string {
    return int2string(integer) + "." + fracs2string(fracs)
}

func fracs2string(fracs []int) string {
    bs := make([]byte, len(fracs))
    for i := range fracs {
        bs[i] = byte('0' + fracs[i])
    }
    return string(bs)
}

func int2string(integer int) string {
    if integer == 0 {
        return "0"
    }
    var bs []byte
    for integer != 0 {
        bs = append(bs, byte('0' + integer % 10))
        integer = integer/10
    }

    for i:=0;i<len(bs)/2; i++ {
        bs[i], bs[len(bs)-1-i] = bs[len(bs)-1-i], bs[i]
    }
    return string(bs)
}

image.png

后記

1. 題目細節(jié)處理比較繁瑣，要一步一步的來
2. leetcode 改版了，看起來很高級，但是直觀性還需要適應(yīng)