分数转小数如何检测循环节？（LeetCode 166）

简化版

分数转小数本质是模拟竖式除法。整数部分直接相除，小数部分不断让余数乘 10 再除以分母。只要某个余数第二次出现，从第一次出现的位置到当前位置就是循环节，用括号括起来即可。还要处理正负号、0、以及整数溢出，所以计算前转成 long。

详细版

String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";
    StringBuilder ans = new StringBuilder();
    long a = numerator, b = denominator;
    if ((a < 0) ^ (b < 0)) ans.append("-");
    a = Math.abs(a);
    b = Math.abs(b);

    ans.append(a / b);
    long rem = a % b;
    if (rem == 0) return ans.toString();
    ans.append(".");

    Map<Long, Integer> seen = new HashMap<>();
    while (rem != 0) {
        if (seen.containsKey(rem)) {
            int pos = seen.get(rem);
            ans.insert(pos, "(");
            ans.append(")");
            break;
        }
        seen.put(rem, ans.length());
        rem *= 10;
        ans.append(rem / b);
        rem %= b;
    }
    return ans.toString();
}

余数决定后续所有小数位，所以记录“余数第一次出现的位置”就能定位循环起点。时间复杂度与循环节长度有关，最多出现 denominator 种余数。

完整版教学

一、为什么这题要模拟竖式除法

十进制小数的生成过程就是竖式除法：先得到整数部分，再用余数继续产生小数位。

1 / 6:
整数部分 0，余数 1
1 * 10 / 6 = 1，余数 4
4 * 10 / 6 = 6，余数 4
余数 4 再次出现，所以 6 循环

小数位不是凭空来的，每一位都由“当前余数乘 10 后除以分母”得到。

二、为什么重复余数代表循环

当某个余数再次出现时，从这一刻开始，后续运算状态与上一次完全相同：同样的余数、同样的分母，所以会生成同样的小数位序列。

当前余数	下一位	新余数
`1`	`1`	`4`
`4`	`6`	`4`
`4`	`6`	`4`

因此第一次出现该余数的位置就是循环节左括号应该插入的位置。

关键点：不是记录“小数数字是否重复”，而是记录“余数是否重复”。数字重复不一定形成循环，余数重复才意味着后续状态完全复现。

三、哈希表记录什么

哈希表 seen 的 key 是余数，value 是这个余数对应的小数位即将写入的位置，也就是 ans.length()。

seen.put(rem, ans.length());
rem *= 10;
ans.append(rem / b);
rem %= b;

如果余数 rem 再出现，就在 seen.get(rem) 位置插入 "("，并在末尾追加 ")"。

四、符号与零的处理

如果分子是 0，结果必然是 "0"，不需要考虑符号。否则符号由分子和分母是否异号决定：

if ((a < 0) ^ (b < 0)) ans.append("-");

异或表示“只有一个为负”。随后把分子和分母都转为正数继续算。

五、为什么要转成 long

Integer.MIN_VALUE 的绝对值无法用 int 表示：

Integer.MIN_VALUE = -2147483648
abs(-2147483648) 仍可能溢出

所以必须先转 long，再取绝对值。这个边界在整数题里非常常见，面试时主动说出来会显得稳。

六、终止条件与复杂度

循环有两个终止条件：

余数变成 0：有限小数
余数重复：循环小数

分母为 b 时，余数只可能是 0..b-1。如果没有归零，最多经过 b-1 个非零余数就一定重复，所以算法会终止。空间复杂度也是记录这些余数，最坏 O(b)。

七、常见误区与追问

误区：记录出现过的小数位而不是余数。 单个数字重复不能确定循环节，状态重复才行。
误区：忘记在余数第一次出现前记录位置。 位置错了，括号会插偏。
误区：直接对 int 取绝对值。 Integer.MIN_VALUE 会溢出，应该先转 long。
追问：为什么余数重复后一定循环？ 因为后续计算只由余数和分母决定，状态完全相同。
追问：有限小数什么时候结束？ 余数变成 0 时结束。
追问：时间复杂度如何界定？ 与产生的小数位数有关，余数最多有 denominator 种。

八、加强记忆

分数转小数就记住“竖式除法 + 余数定位循环”。整数部分直接除，小数部分每轮 rem *= 10，写商，再取余。哈希表不是存数字，而是存余数到答案下标的映射；余数重现，就把括号插回第一次出现的位置。

简化版

详细版