分数到小数。给定两个整数,分别表示分数的分子numerator和分母denominator,以字符串形式返回小数。如果小数部分为循环小数,则将循环的部分括在括号内。输入: numerator = 1, denominator = 2,输出: “0.5”。输入: numerator = 2, denominator = 3,输出: “0.(6)”。力扣166。
1.分子/分母,求得整数部分。
2.分子=分子%10。
3.然后分子=分子*10,然后重复第1步。
时间复杂度:O(lgN)。
空间复杂度:O(lgN)。
代码用golang编写。代码如下:、
package main
import "fmt"
func main() {
a := 3
b := 11
ret := fractionToDecimal(a, b)
fmt.Println(ret)
fmt.Println(3.0 / 11.0)
}
func fractionToDecimal(numerator, denominator int) string {
if numerator == 0 {
return "0"
}
//StringBuilder res = new StringBuilder();
res := make([]byte, 0)
// "+" or "-"
//res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
if (numerator > 0 && !(denominator > 0)) || (!(numerator > 0) && denominator > 0) {
res = append(res, []byte("-")...)
} else {
res = append(res, []byte("")...)
}
num := Abs(numerator)
den := Abs(denominator)
// integral part
//res.append(num / den);
res = append(res, []byte(fmt.Sprint(num/den))...)
num %= den
if num == 0 {
return string(res)
}
// fractional part
res = append(res, []byte(".")...)
map0 := make(map[int]int)
map0[num] = len(res)
for num != 0 {
num *= 10
res = append(res, []byte(fmt.Sprint(num/den))...)
num %= den
if _, ok := map0[(num)]; ok {
index := map0[num]
//res.insert(index, "(")
rescopy := make([]byte, 0)
rescopy = append(rescopy, res[0:index]...)
rescopy = append(rescopy, []byte("(")...)
rescopy = append(rescopy, res[index:]...)
res = rescopy
res = append(res, []byte(")")...)
break
} else {
map0[num] = len(res)
}
}
return string(res)
}
func Abs(a int) int {
if a < 0 {
return -a
} else {
return a
}
}
执行结果如下: