关于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。