关于golang:golangleetcode中级分数到小数

题目

思路

本题能够拆解为几个小问题解决

1.符号的计算

2.小数点前整数局部的计算

3.小数点后小数的计算

（1）无限的小数，当余数为零时进行计算（2）有限循环小数，当呈现反复的数字时，将循环局部退出字符串（3）有限不循环小数 ，因为分数为有理数，无需思考该类小数

小数的具体计算方法能够应用竖式计算的长除法实现计算

代码

func fractionToDecimal(numerator, denominator int) string {    if numerator%denominator == 0 {        return strconv.Itoa(numerator / denominator)    }    s := []byte{}    if numerator < 0 != (denominator < 0) {        s = append(s, '-')    }    // 整数局部    numerator = abs(numerator)    denominator = abs(denominator)    integerPart := numerator / denominator    s = append(s, strconv.Itoa(integerPart)...)    s = append(s, '.')    // 小数局部    indexMap := map[int]int{}    remainder := numerator % denominator    for remainder != 0 && indexMap[remainder] == 0 {        indexMap[remainder] = len(s)        remainder *= 10        s = append(s, '0'+byte(remainder/denominator))        remainder %= denominator    }    if remainder > 0 { // 有循环节        insertIndex := indexMap[remainder]        s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)        s = append(s, ')')    }    return string(s)}func abs(x int) int {    if x < 0 {        return -x    }    return x}

复杂度剖析

工夫复杂度：O(l)，其中 l 是答案字符串的长度，这道题中 l≤10^4 。对于答案字符串中的每一个字符，计算工夫都是 O(1)。

空间复杂度：O(l)，其中 l 是答案字符串的长度，这道题中 l<10^4。空间复杂度次要取决于答案字符串和哈希表，哈希表中的每个键值对所对应的下标各不相同，因而键值对的数量不会超过 l。