0166. Fraction to Recurring Decimal

题目信息

题号:
  1. 分数到小数

难度:

Medium

主题:

哈希表、长除法、有限状态

原题:

LeetCode 0166

重点:

将长除法的余数作为完整状态,用状态首次重复的位置界定循环节

题目重述

给定两个 32 位有符号整数 numerator 和 denominator,将分数 numerator / denominator 转成十进制字符串。输入保证分母不为 0。

整数结果不保留小数点;有限小数写出完整小数部分;无限循环小数用一对圆括号包住循环节。 负号只出现在整个字符串最前面。

自建示例

输入:numerator = 7, denominator = 12
输出:"0.58(3)"

7 / 12 = 0.58333...,非循环前缀是 58,循环节是 3。
输入:numerator = 1, denominator = 6
输出:"0.1(6)"

余数 4 第二次出现时,它第一次出现之前已经生成了非循环数字 1。
输入:numerator = -2147483648, denominator = -1
输出:"2147483648"

结果为正,绝对值超出 32 位有符号整数,但可以由 64 位整数安全保存。

C++ 实现

#include <cstddef>
#include <string>
#include <unordered_map>

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

        long long dividend = numerator;
        long long divisor = denominator;
        bool negative = (dividend < 0) != (divisor < 0);
        if (dividend < 0) {
            dividend = -dividend;
        }
        if (divisor < 0) {
            divisor = -divisor;
        }

        std::string result;
        if (negative) {
            result.push_back('-');
        }
        result += std::to_string(dividend / divisor);

        long long remainder = dividend % divisor;
        if (remainder == 0) {
            return result;
        }

        result.push_back('.');
        std::unordered_map<long long, std::size_t> first_position;

        while (remainder != 0) {
            auto repeated = first_position.find(remainder);
            if (repeated != first_position.end()) {
                result.insert(repeated->second, 1, '(');
                result.push_back(')');
                break;
            }

            first_position[remainder] = result.size();
            remainder *= 10;
            int digit = static_cast<int>(remainder / divisor);
            result.push_back(static_cast<char>('0' + digit));
            remainder %= divisor;
        }
        return result;
    }
};

题解

浮点数不是题目的搜索空间

直觉上可以先做浮点除法,再观察小数数字是否重复。但浮点数只保存有限精度:长循环会被 截断或舍入,某些有限小数也无法在二进制浮点中精确表示。输出要求的是精确的十进制结构, 所以不能从近似值反推循环节。

回到小学长除法:先得到整数部分;若余数非零,就把余数乘 10,商的一位写入答案, 再以新的余数继续。这个过程不会猜测数字,每一步都由整数运算精确确定。

为什么余数是完整状态

固定正分母 divisor 后,下一位和下一余数完全由当前余数 remainder 决定:

expanded  = remainder * 10
nextDigit = expanded / divisor
nextState = expanded % divisor

因此过去生成过哪些数字并不影响未来;只要某个余数再次出现,从它开始的后续数字就会与 第一次出现时完全相同。长除法只有两种终局:

  • 余数变为 0,后面不会再有非零小数位,结果有限;

  • 某个非零余数重复,确定性状态转移从此进入循环。

非零余数只可能是 1..divisor-1。即使暂时不知道循环何时开始,状态数有限也保证上述 两种情况必有一个发生。

位置表删除了什么重复工作

若只用集合记录余数,可以知道“循环已经出现”,却不知道左括号应插在哪里。哈希表 first_position[remainder] 同时记录该余数第一次出现时,下一位数字将在结果字符串中 写入的位置。

检查与记录必须发生在生成下一位之前:此时 remainder 描述的正是“将要生成的后缀”。 重复时在其首次位置插入 '(',当前字符串尾部就是一个完整周期的末端,再追加 ')'。每个新余数只处理一次,发现重复后不再重新生成已经确定的循环数字。

具体走读

对 1 / 6,整数部分和小数点先得到 "0.":

当前余数  首次位置  生成数字  新余数  当前结果
1         2         1         4       0.1
4         3         6         4       0.16
4         已出现于 3,不再生成数字

第二次见到余数 4 时,在位置 3 插入左括号并在末尾追加右括号,得到 "0.1(6)"。 非循环前缀 1 没有被错误地放进括号。

对 7 / 12,余数依次为 7 -> 10 -> 4 -> 4,对应生成 5、8、3。 余数 4 首次位置在数字 3 之前,所以结果为 "0.58(3)"。若分子能被分母整除, 初始余数就是 0,代码在添加小数点之前返回。

符号与溢出边界

符号只取决于分子、分母是否异号。代码先处理零分子,避免产生 "-0";随后先把两个 int 提升为 long long,再取相反数。若在 32 位中直接对 INT_MIN 取绝对值, 其正值无法表示,会产生溢出。

取绝对值后,余数小于 divisor;两者都来自 32 位整数,因此 remainder * 10 可以安全放在 long long 中。整数部分同样用 64 位计算,能够表示 2147483648。

复杂度

设最终写出的小数数字数为 k。每个不同余数只进入哈希表一次,时间复杂度为 O(k),哈希表额外空间为 O(k);结果字符串本身也占 O(k) 空间。理论上 k 不超过正分母可能产生的不同非零余数数量。