LeetCode 166. 分数到小数

约 6 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 华为 微软
标签
字符串 哈希表 数学

题目描述

✅ 166. 分数到小数

image-20260928220101723

image-20260928220101724

题意分析

给出分子和非零分母，将这个分数转成精确的十进制字符串。整数结果不写小数点，有限小数写到余数为零；无限循环小数则把循环部分用括号括起来，非循环前缀仍保留在括号外。

分子、分母都可能为负，最终只在异号且结果非零时带一个负号。不能先算浮点数再转字符串，因为那样会丢失精度，也无法知道重复的小数位从哪里开始。

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

核心思路

[!blue]

使用整数长除法。先处理符号，再对两个数的绝对值求整数商和余数。整数部分已经确定，后面只需反复处理余数：设正分母为 divisor，将当前余数乘十，所得商是下一位小数，所得余数决定下一轮。

当前余数完整决定后续小数：同一个余数、同一个分母，必然产生相同的下一位和下一余数。如果某个非零余数再次出现，从它第一次出现开始生成的整段小数就会不断重复；某一位商重复并不能说明循环，因为不同余数也可能得到相同数字。

因此用哈希表记录“余数 → 它即将生成的小数位在结果中的位置”。每轮先检查是否出现过当前余数，未出现就记录当前位置，再乘十、写商、更新余数。发现重复时，在首次记录的位置插入左括号，在当前末尾加右括号；余数归零则是有限小数，直接结束。

余数只能在零到分母减一之间变化，非零状态数量有限，所以这个过程一定归零或遇到重复。记录的是完整结果中的位置，整数部分和负号也算在长度里，插入括号时无需重新计算小数偏移。

计算前先扩为 64 位整数再取绝对值，才能容纳 32 位最小负数的绝对值以及余数乘十。零分子提前返回，避免负零；整除时也提前返回，避免多余小数点。

解题步骤

  1. 分子为零直接返回 "0"；否则判断分子、分母是否异号，决定是否添加负号。
  2. 把两数先转换为 64 位，再取绝对值，写入整数商并求余数。
  3. 余数为零时返回整数结果，否则添加小数点并创建余数位置表。
  4. 每轮若当前余数已经出现，在记录位置插入 (，末尾追加 ) 后结束。
  5. 否则先记录当前结果长度，再将余数乘十，追加商的一位，更新余数。
  6. 余数归零时直接返回当前结果，不添加括号。

代码实现

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)
}

复杂度分析

  • 时间复杂度：$O(L)$，L 为最终字符串长度。每个不同余数处理一次，哈希操作平均为常数；最后插入括号或拼接结果至多再复制线性数量的字符。
  • 空间复杂度：$O(L)$，保存结果缓冲区和小数位对应的余数位置。

关键点总结

[!green]

  • 长除法用整数保留精确状态，余数才是识别循环的依据。
  • 记录余数时，它对应的下一位尚未写入，因此该位置就是循环节起点。
  • 同一余数意味着后续状态完全相同，有限状态保证计算能够结束。
  • 先扩展整数类型，再处理绝对值和乘十，符号只在开头统一输出。

易错点总结

[!yellow]

  • 用浮点除法生成字符串，无法保留精确循环节，有限小数也可能受舍入影响。
  • 在 32 位类型里先取绝对值再转换，最小负数已经发生溢出，转换无法补救。
  • 在写出小数位之后才记录它对应的余数位置，左括号会放到错误位置。
  • 只保存余数是否出现，不保存首次输出位置，无法区分非循环前缀和循环节。
  • 看到某个数字重复就加括号，忽略相同商位可能来自不同除法状态。
  • 整除后仍添加小数点，或零分子仍处理负号，产生格式不符合要求的结果。

相似题目

题目 难度 关联与区别
202. 快乐数 简单 同样利用重复状态识别循环，本题状态是除法余数，重复余数确定小数循环节的起点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/22146309
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！