166. Fraction to Recurring Decimal

Leetcode link

题目简介

这是道数学相关的题，题目给了分子 numerator 与分母 denominator 两个参数，要求我们返回其小数的表达方式

如果该小数是循环小数，则需要用 () 将循环的部份包裹住

此外题目确保了不会出现无限不循环小数

解题思路

想要解这道题我们需要回归除法的计算方法：

1. 将分子除以分母，获得商与余
2. 如果没有余数，则答案就是商，如果有余数，将答案添加一个小数点，然后余数 *10， 继续除
3. 直到余数为 0

这道题我们也可以用这个思路，区别在于我们需要考虑其他场景：

• 是否分子有 0
• 是否两者相除为负数
• 如何判断出现循环

前两者都好判断，后者的话我们需要用一个 Map 来记录曾经出现过的余数，以及余数除后的商的位置

当我们后续出现了相同的余数，就等于出现了循环，此时我们只需要在之前记录的位置以及当前最后位置加上 () 就好

Javascript

/**
 * @param {number} numerator
 * @param {number} denominator
 * @return {string}
 */
var fractionToDecimal = function (numerator, denominator) {
    if (numerator === 0) {
        return '0'
    }

    const res = []
    // handle negative sign
    if (numerator < 0 !== denominator < 0) {
        res.push('-')
    }

    const positiveNumerator = Math.abs(numerator)
    const positiveDenominator = Math.abs(denominator)

    // handle integer part
    res.push(Math.floor(positiveNumerator / positiveDenominator))

    let remainder = positiveNumerator % positiveDenominator
    if (remainder === 0) {
        return res.join('')
    }

    // handle fractional part
    res.push('.')
    const seen = new Map()
    while (remainder !== 0) {
        if (seen.has(remainder)) {
            res.push(')')
            res.splice(seen.get(remainder), 0, '(')
            break;
        }
        seen.set(remainder, res.length)
        res.push(Math.floor(remainder * 10 / positiveDenominator))
        remainder = remainder * 10 % positiveDenominator
    }

    return res.join('')
};