题目描述
思路解析动画文字版
关键魔法:同一个余数必然算出同一串后续小数。所以我们用哈希表记下「每个余数第一次出现在第几位」,余数一旦撞车,就知道循环节从哪儿开始。
无限循环小数没有终点,光靠多除几位是判断不出来的。必须有个客观信号告诉我们「该停了」——那个信号就是「余数重复了」。
第 0 步 · 算整数部分：先算整数部分:4 里一个 333 都装不下,商 0,余下 4。结果先写成 0.,下面四个空格子等着填小数位。余数不为 0,开始长除法。
小数位 0 · 余数 4 是新的吗?：要填第 0 个小数位。先问哈希表:余数 4 之前出现过吗?表是空的 → 没有。那就把「余数 4 出现在第 0 位」记进表里,作为日后判循环的依据。
小数位 0 · 记账 + 余数 ×10：登记完成(高亮那行就是刚记的)。接着像竖式那样给余数补一个 0:rem 从 4 变成 40,准备除以 333 求出这一位的商。
小数位 0 · 求商：40 ÷ 333:装不下,商 0。第 0 个格子填上 0,新余数 = 40 − 0×333 = 40。结果变成 0.0。余数还不是 0,继续下一位。
小数位 1 · 余数 40 是新的吗?：填第 1 位。当前余数 40,查表里只有 {4→0},没有 40。登记「余数 40 出现在第 1 位」。
小数位 1 · 记账 + 余数 ×10：记好账(高亮新行 {40→1}),给余数补 0:rem 变 400。这下 400 比 333 大了,能除出非零的商。
小数位 1 · 求商：400 里有 1 个 333,商 1。第 1 个格子填 1,新余数 = 400 − 333 = 67。结果变成 0.01。
小数位 2 · 余数 67 是新的吗?：填第 2 位。余数 67,表里有 4 和 40,没有 67。登记「余数 67 出现在第 2 位」。
小数位 2 · 记账 + 余数 ×10：记下 {67→2}(高亮),余数补 0 变 670。670 比 333 大,继续求商。
小数位 2 · 求商：670 里有 2 个 333(666),商 2。第 2 个格子填 2,新余数 = 670 − 666 = 4。结果变成 0.012。注意——这个余数 4,好像见过?
小数位 3 · 余数 4 撞车了!：要填第 3 位时,余数又变回了 4。查表——命中!余数 4 早在第 0 位就出现过(高亮那行)。余数重复 = 后面的小数会原样重来 = 找到循环节了!
括出循环节 · 完成：余数 4 第一次出现在第 0 位,所以从第 0 位到现在的 0、1、2 整段就是循环节。在第 0 位前插「(」、末尾补「)」,答案就是 0.(012)。第 3 位不用再填(变灰)。
余数最多 d 种(d = 分母)。要么除到余数为 0(有限小数,如 1/2),要么 d 步内必然撞车(循环小数)。所以哈希表里最多记 d 个余数,绝不会无限算下去。
再演一例 · 1/7 长循环：换 1/7 走一遍,体会循环节也可以很长。七个空格子等着填。整数 0,余数 1,开始长除法。
1/7 · 第 0 位：余数 1 是新的,记 {1→0};补 0 变 10,10÷7 商 1 余 3。第 0 格填 1。
1/7 · 第 1 位：余数 3 新,记 {3→1};30÷7 商 4 余 2。第 1 格填 4。
1/7 · 第 2 位：余数 2 新,记 {2→2};20÷7 商 2 余 6。第 2 格填 2。
1/7 · 第 3 位：余数 6 新,记 {6→3};60÷7 商 8 余 4。第 3 格填 8。
1/7 · 第 4 位：余数 4 新,记 {4→4};40÷7 商 5 余 5。第 4 格填 5。
1/7 · 第 5 位：余数 5 新,记 {5→5};50÷7 商 7 余 1。第 5 格填 7。注意——新余数 1,正是最开始那个余数!
1/7 · 余数 1 撞车 → 括出循环节：余数 1 第一次出现在第 0 位,所以 142857 整段循环。括起来得 0.(142857)——六位循环节,但靠哈希记账一样精准定位,不靠眼睛猜。
对比 · 1/2 是有限小数：换 1/2 看看「除尽」的情况:整数部分 0,余数 1 补 0 变 10,10÷2 商 5 余 0。余数归 0,循环直接结束,根本用不上哈希表 → 答案 0.5,没有括号。
对比 · 2/1 没有小数：再看 2/1:整数部分就是 2,余数 2 % 1 = 0。余数为 0,连小数点都不用加,直接返回 "2"。这就是要先判余数是否为 0 的原因。
雷区实演 · 记错了存「数字」：假如哈希表记成「余数→那一位的数字」,余数 4 撞车时只知道「当时商是 0」,却不知道这个 0 在结果串的第几位,括号没法插。所以一定要记位置。
边界三连：先想清零分子、INT_MIN 溢出、长循环节三种,代码就稳了。
面试追问：把「为何终止」「溢出/符号」「哈希记位置」三点讲清,是这题面试的得分点。
参考代码
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)复杂度
- 时间复杂度：O(d)，d = 分母。余数只有 0~d−1 种,最多 d 步必然遇到 0 或重复余数,循环至多 d 次
- 空间复杂度：O(d)，哈希表最多存 d 个不同余数;结果串长度也受 d 限制
易错点
面试追问把动画讲成自己的话
追问为什么循环一定会终止?
追问怎么处理负数和溢出?
追问哈希表里键和值分别存什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
阶乘后的零
LeetCode 172 · 中等 · 沿着 数学套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题