LeetCode 166. 分数到小数

◎

本节目标

用余数首次出现的位置识别小数循环节。

查看原题

返回数学建模框架

题意与约束

把两个 32 位整数的商写成字符串；有限小数直接结束，循环部分要用一对括号包住。

第一反应与瓶颈

按长除法不断补零能得到每一位，但若小数循环就不会自然结束。仅知道“某个数字重复”不足以确定循环开始位置。

数学关系与算法推导

一次除法的未来完全由余数决定。哈希表记录“余数首次出现时，结果字符串的下标”；再次遇到同一余数，就在该下标插入左括号并在末尾补右括号。

正确性依据

相同余数除以同一正分母，下一位数字和下一余数必然相同，因此其后缀重复。首次记录保证括号从循环第一次开始的位置插入；余数为零则除法恰好结束。

样例执行过程

2 / 3 的整数部分为 0，余数 2 首次记录在小数点后；补零得到数字 6 和余数 2，再次出现便形成 0.(6)。

代码实现

C++

C++17

#include <cstdlib>
#include <string>
#include <unordered_map>
using namespace std;

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

        const long long dividend = numerator;
        const long long divisor = denominator;
        string result;
        if ((dividend < 0) != (divisor < 0)) {
            result.push_back('-');
        }

        long long absoluteDividend = llabs(dividend);
        const long long absoluteDivisor = llabs(divisor);
        result += to_string(absoluteDividend / absoluteDivisor);
        long long remainder = absoluteDividend % absoluteDivisor;
        if (remainder == 0) {
            return result;
        }

        result.push_back('.');
        unordered_map<long long, int> positions;
        while (remainder != 0) {
            const auto found = positions.find(remainder);
            if (found != positions.end()) {
                result.insert(found->second, "(");
                result.push_back(')');
                break;
            }
            positions[remainder] = static_cast<int>(result.size());
            remainder *= 10;
            result.push_back(static_cast<char>('0' + remainder / absoluteDivisor));
            remainder %= absoluteDivisor;
        }
        return result;
    }
};

Python

Python 3

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return '0'

        result = '-' if (numerator < 0) != (denominator < 0) else ''
        numerator = abs(numerator)
        denominator = abs(denominator)
        result += str(numerator // denominator)
        remainder = numerator % denominator
        if remainder == 0:
            return result

        result += '.'
        positions: dict[int, int] = {}
        while remainder:
            if remainder in positions:
                position = positions[remainder]
                return result[:position] + '(' + result[position:] + ')'
            positions[remainder] = len(result)
            remainder *= 10
            result += str(remainder // denominator)
            remainder %= denominator
        return result

复杂度分析

• 时间复杂度：O(L)，L 为输出长度。
• 空间复杂度：O(L)，用于结果和余数位置。

边界与易错点

• 先将分子、分母提升到 64 位再取绝对值，INT_MIN 不能在 32 位内安全取反。
• 整除时不要留下小数点。
• 符号只在结果非零且两数异号时添加一次。

模式迁移

当一个过程的后续仅由有限状态决定时，记录状态首次位置可以同时检测循环并恢复循环段，例如余数、自动机状态或链表节点。