LeetCode 166. 分数到小数

2026-05-08 HGNULB 约 6 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 166. 分数到小数

题意分析

给定分子 numerator 和分母 denominator 两个 32 位整数，要求把这个分数写成十进制字符串返回。分母保证不为 0，答案保证长度不超过 $10^4$。

题目真正考的不是「算出小数」，而是把手算除法的一整套书写规则准确地翻译成代码。这些规则一共四条，缺一条就会挂用例：

负号规则：只有当分子分母恰好一正一负时结果才带负号，且负号只出现一次、只出现在最前面。分子为 0 时无论分母正负，答案都是 "0" 而不是 "-0"。

整除规则：能整除时结果没有小数部分，末尾不能留一个孤零零的小数点。

循环节规则：小数部分若开始循环，要把循环的那一段用一对圆括号包起来，非循环的前缀留在括号外，例如 1 / 2 是 "0.5"，2 / 3 是 "0.(6)"，1 / 6 是 "0.1(6)"。

溢出规则：输入是 int，而 -2147483648 取相反数在 int 里表示不出来；除法过程中余数还要反复乘 10，也会冲出 int 范围。全程必须用 64 位整数承载。

约束信号很直接：分母是 32 位整数，说明除法过程中互不相同的余数最多只有 $\lvert denominator\rvert$ 个，规模有限，可以放心地把余数当成状态来记录。

边界情况：分子为 0；分母为负；结果为整数；Integer.MIN_VALUE 作为分子或分母；纯循环（如 2 / 3）与带前缀的混循环（如 1 / 6）。

解法：长除法 + 余数位置表

核心思路

浮点数只能得到有限精度的近似值，无法判断循环节，因此要模拟竖式除法。写完整数部分后，反复执行：

余数 × 10 → 写下一位商 → 得到新余数

对固定分母而言，当前余数唯一决定下一位商和后续余数。若余数变成 0，说明小数有限；若某个非零余数再次出现，之后的状态会与第一次出现时完全相同，因此两次出现之间的数字就是循环节。

用哈希表记录 余数 -> 该余数生成的第一位数字在结果中的下标。登记必须发生在写数字之前；发现重复余数时，才能在正确位置插入左括号。

输入是 32 位整数，但最小整数取绝对值会溢出，余数还要乘 10。因此先转成 64 位整数，再统一处理符号和绝对值。

解题步骤

分子为 0 时直接返回 "0"，避免产生 "-0"。

根据分子、分母是否异号写入负号；将二者转为 64 位正数。

写入整数部分，计算余数；余数为 0 时直接返回。

写入小数点，并在每轮生成数字前记录当前余数的位置。

余数重复时在首次位置插入 (，末尾补 )；余数归零时正常结束。

例如 1 / 6：余数依次为 1、4、4，第二个 4 重复，因此结果是 "0.1(6)"。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }

        StringBuilder answer = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) {
            answer.append('-');
        }

        long dividend = Math.abs((long) numerator);
        long divisor = Math.abs((long) denominator);
        answer.append(dividend / divisor);

        long remainder = dividend % divisor;
        if (remainder == 0) {
            return answer.toString();
        }

        answer.append('.');
        Map<Long, Integer> position = new HashMap<>();
        while (remainder != 0) {
            Integer start = position.get(remainder);
            if (start != null) {
                answer.insert(start.intValue(), '(');
                answer.append(')');
                break;
            }

            position.put(remainder, answer.length());
            remainder *= 10;
            answer.append(remainder / divisor);
            remainder %= divisor;
        }
        return answer.toString();
    }
}

import "strconv"

func fractionToDecimal(numerator int, denominator int) string {
    if numerator == 0 {
        return "0"
    }

    dividend, divisor := int64(numerator), int64(denominator)
    negative := (dividend < 0) != (divisor < 0)
    if dividend < 0 {
        dividend = -dividend
    }
    if divisor < 0 {
        divisor = -divisor
    }

    answer := make([]byte, 0)
    if negative {
        answer = append(answer, '-')
    }
    answer = strconv.AppendInt(answer, dividend/divisor, 10)

    remainder := dividend % divisor
    if remainder == 0 {
        return string(answer)
    }

    answer = append(answer, '.')
    position := make(map[int64]int)
    for remainder != 0 {
        if start, ok := position[remainder]; ok {
            return string(answer[:start]) + "(" + string(answer[start:]) + ")"
        }

        position[remainder] = len(answer)
        remainder *= 10
        answer = strconv.AppendInt(answer, remainder/divisor, 10)
        remainder %= divisor
    }
    return string(answer)
}

复杂度分析

设小数部分生成了 k 位。

时间复杂度：$O(k)$。每个不同余数只处理一次，重复后立即停止；最后插入括号也只需线性复制一次。

空间复杂度：$O(k)$。哈希表和结果字符串都随生成的小数位数增长。

关键点总结

判断循环要看余数是否重复，不能看某一位商是否重复。

哈希表记录的是当前余数即将生成的数字位置，而不是生成数字后的下标。

先扩为 64 位再取绝对值，才能覆盖 Integer.MIN_VALUE。

负号、整数部分、有限小数和循环小数要分阶段处理，逻辑最清晰。

易错点总结

直接使用 double 会丢失循环节和精确信息。

在 32 位整数上调用绝对值，处理最小整数时会溢出。

把余数写入哈希表的时机放在生成数字之后，会使左括号偏移一位。

只记录“余数出现过”而不记录位置，无法确定循环节从哪里开始。

整除后仍追加小数点，会得到 "2." 这类错误格式。

相似题目

题目	难度	考察点
29. 两数相除	中等	禁用乘除取模，用移位倍增做除法，同样要处理最小整数溢出
43. 字符串相乘	中等	大数乘法的竖式模拟，逐位进位而非逐位取余
8. 字符串转换整数 (atoi)	中等	输入方向的规则罗列：空白、符号、越界截断
202. 快乐数	简单	同样靠「状态重复即进入循环」终止，可用哈希表或快慢指针
172. 阶乘后的零	中等	不做实际除法，靠质因子计数直接推导结果
168. Excel 表列名称	简单	反复取模取商做进制转换，难在从 1 开始的偏移