分数到小数 图解题解

这道题到底在问什么

输入

4 / 333

输出

"0.(012)"

含义

0.012012012… 循环节是 012

最优解：一步一步想明白

1. 3关键魔法:同一个余数必然算出同一串后续小数。所以我们用哈希表记下「每个余数第一次出现在第几位」,余数一旦撞车,就知道循环节从哪儿开始。
2. 4无限循环小数没有终点,光靠多除几位是判断不出来的。必须有个客观信号告诉我们「该停了」——那个信号就是「余数重复了」。
3. 54 ÷ 333 商 0,余 4先算整数部分:4 里一个 333 都装不下,商 0,余下 4。结果先写成 0.,下面四个空格子等着填小数位。余数不为 0,开始长除法。
4. 6查哈希表:4 没出现过要填第 0 个小数位。先问哈希表:余数 4 之前出现过吗?表是空的 → 没有。那就把「余数 4 出现在第 0 位」记进表里,作为日后判循环的依据。
5. 7登记 {4→0},rem 变 40登记完成(高亮那行就是刚记的)。接着像竖式那样给余数补一个 0:rem 从 4 变成 40,准备除以 333 求出这一位的商。
6. 840 ÷ 333 = 040 ÷ 333:装不下,商 0。第 0 个格子填上 0,新余数 = 40 − 0×333 = 40。结果变成 0.0。余数还不是 0,继续下一位。
7. 9查哈希表:40 没出现过填第 1 位。当前余数 40,查表里只有 {4→0},没有 40。登记「余数 40 出现在第 1 位」。
8. 10登记 {40→1},rem 变 400记好账(高亮新行 {40→1}),给余数补 0:rem 变 400。这下 400 比 333 大了,能除出非零的商。
9. 11400 ÷ 333 = 1400 里有 1 个 333,商 1。第 1 个格子填 1,新余数 = 400 − 333 = 67。结果变成 0.01。
10. 12查哈希表:67 没出现过填第 2 位。余数 67,表里有 4 和 40,没有 67。登记「余数 67 出现在第 2 位」。
11. 13登记 {67→2},rem 变 670记下 {67→2}(高亮),余数补 0 变 670。670 比 333 大,继续求商。
12. 14670 ÷ 333 = 2670 里有 2 个 333(666),商 2。第 2 个格子填 2,新余数 = 670 − 666 = 4。结果变成 0.012。注意——这个余数 4,好像见过?
13. 15查哈希表:4 在第 0 位出现过要填第 3 位时,余数又变回了 4。查表——命中!余数 4 早在第 0 位就出现过(高亮那行)。余数重复 = 后面的小数会原样重来 = 找到循环节了!
14. 16第 0~2 位是循环节 → 0.(012)余数 4 第一次出现在第 0 位,所以从第 0 位到现在的 0、1、2 整段就是循环节。在第 0 位前插「(」、末尾补「)」,答案就是 0.(012)。第 3 位不用再填(变灰)。
15. 17余数最多 d 种(d = 分母)。要么除到余数为 0(有限小数,如 1/2),要么 d 步内必然撞车(循环小数)。所以哈希表里最多记 d 个余数,绝不会无限算下去。
16. 18起步:整数 0,余数 1换 1/7 走一遍,体会循环节也可以很长。七个空格子等着填。整数 0,余数 1,开始长除法。
17. 19记 {1→0},10÷7 商 1 余 3余数 1 是新的,记 {1→0};补 0 变 10,10÷7 商 1 余 3。第 0 格填 1。
18. 20记 {3→1},30÷7 商 4 余 2余数 3 新,记 {3→1};30÷7 商 4 余 2。第 1 格填 4。
19. 21记 {2→2},20÷7 商 2 余 6余数 2 新,记 {2→2};20÷7 商 2 余 6。第 2 格填 2。
20. 22记 {6→3},60÷7 商 8 余 4余数 6 新,记 {6→3};60÷7 商 8 余 4。第 3 格填 8。
21. 23记 {4→4},40÷7 商 5 余 5余数 4 新,记 {4→4};40÷7 商 5 余 5。第 4 格填 5。
22. 24记 {5→5},50÷7 商 7 余 1余数 5 新,记 {5→5};50÷7 商 7 余 1。第 5 格填 7。注意——新余数 1,正是最开始那个余数!
23. 251 在第 0 位见过 → 0.(142857)余数 1 第一次出现在第 0 位,所以 142857 整段循环。括起来得 0.(142857)——六位循环节,但靠哈希记账一样精准定位,不靠眼睛猜。
24. 26余数除到 0,直接结束换 1/2 看看「除尽」的情况:整数部分 0,余数 1 补 0 变 10,10÷2 商 5 余 0。余数归 0,循环直接结束,根本用不上哈希表 → 答案 0.5,没有括号。
25. 27余数一开始就是 0再看 2/1:整数部分就是 2,余数 2 % 1 = 0。余数为 0,连小数点都不用加,直接返回 "2"。这就是要先判余数是否为 0 的原因。
26. 31余数撞车却不知从哪插括号假如哈希表记成「余数→那一位的数字」,余数 4 撞车时只知道「当时商是 0」,却不知道这个 0 在结果串的第几位,括号没法插。所以一定要记位置。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def fractionToDecimal(self, numerator, denominator):
        if numerator == 0:
            return "0"
        res = []
        if (numerator < 0) != (denominator < 0):
            res.append("-")              # 符号:异号才为负
        n, d = abs(numerator), abs(denominator)
        res.append(str(n // d))          # 整数部分
        rem = n % d
        if rem == 0:
            return "".join(res)
        res.append(".")
        seen = {}                        # 余数 -> 在 res 中的位置
        while rem != 0:
            if rem in seen:              # 余数重复 = 循环
                res.insert(seen[rem], "(")
                res.append(")")
                break
            seen[rem] = len(res)
            rem *= 10
            res.append(str(rem // d))
            rem %= d
        return "".join(res)

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string res;
        if ((numerator < 0) ^ (denominator < 0)) res += '-';
        long n = llabs((long long)numerator);   // 防 INT_MIN 溢出
        long d = llabs((long long)denominator);
        res += to_string(n / d);
        long rem = n % d;
        if (rem == 0) return res;
        res += '.';
        unordered_map<long, int> seen;          // 余数 -> 位置
        while (rem != 0) {
            if (seen.count(rem)) {
                res.insert(seen[rem], "(");
                res += ')';
                break;
            }
            seen[rem] = (int)res.size();
            rem *= 10;
            res += to_string(rem / d);
            rem %= d;
        }
        return res;
    }
};

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        StringBuilder res = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) res.append('-');
        long n = Math.abs((long) numerator);     // 防 INT_MIN 溢出
        long d = Math.abs((long) denominator);
        res.append(n / d);
        long rem = n % d;
        if (rem == 0) return res.toString();
        res.append('.');
        Map<Long, Integer> seen = new HashMap<Long, Integer>();
        while (rem != 0) {
            if (seen.containsKey(rem)) {
                res.insert(seen.get(rem), "(");
                res.append(')');
                break;
            }
            seen.put(rem, res.length());
            rem *= 10;
            res.append(rem / d);
            rem %= d;
        }
        return res.toString();
    }
}

复杂度

面试官可能追问