0166. Fraction to Recurring Decimal
===================================
题目信息
--------
:题号: 0166. 分数到小数
:难度: Medium
:主题: 哈希表、长除法、有限状态
:原题: `LeetCode 0166 `_
:重点: 将长除法的余数作为完整状态,用状态首次重复的位置界定循环节
题目重述
--------
给定两个 32 位有符号整数 ``numerator`` 和 ``denominator``,将分数
``numerator / denominator`` 转成十进制字符串。输入保证分母不为 0。
整数结果不保留小数点;有限小数写出完整小数部分;无限循环小数用一对圆括号包住循环节。
负号只出现在整个字符串最前面。
自建示例
--------
.. code-block:: text
输入:numerator = 7, denominator = 12
输出:"0.58(3)"
7 / 12 = 0.58333...,非循环前缀是 58,循环节是 3。
.. code-block:: text
输入:numerator = 1, denominator = 6
输出:"0.1(6)"
余数 4 第二次出现时,它第一次出现之前已经生成了非循环数字 1。
.. code-block:: text
输入:numerator = -2147483648, denominator = -1
输出:"2147483648"
结果为正,绝对值超出 32 位有符号整数,但可以由 64 位整数安全保存。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
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 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(remainder / divisor);
result.push_back(static_cast('0' + digit));
remainder %= divisor;
}
return result;
}
};
题解
----
浮点数不是题目的搜索空间
~~~~~~~~~~~~~~~~~~~~~~~~
直觉上可以先做浮点除法,再观察小数数字是否重复。但浮点数只保存有限精度:长循环会被
截断或舍入,某些有限小数也无法在二进制浮点中精确表示。输出要求的是精确的十进制结构,
所以不能从近似值反推循环节。
回到小学长除法:先得到整数部分;若余数非零,就把余数乘 10,商的一位写入答案,
再以新的余数继续。这个过程不会猜测数字,每一步都由整数运算精确确定。
为什么余数是完整状态
~~~~~~~~~~~~~~~~~~~~
固定正分母 ``divisor`` 后,下一位和下一余数完全由当前余数 ``remainder`` 决定:
.. code-block:: text
expanded = remainder * 10
nextDigit = expanded / divisor
nextState = expanded % divisor
因此过去生成过哪些数字并不影响未来;只要某个余数再次出现,从它开始的后续数字就会与
第一次出现时完全相同。长除法只有两种终局:
* 余数变为 0,后面不会再有非零小数位,结果有限;
* 某个非零余数重复,确定性状态转移从此进入循环。
非零余数只可能是 ``1..divisor-1``。即使暂时不知道循环何时开始,状态数有限也保证上述
两种情况必有一个发生。
位置表删除了什么重复工作
~~~~~~~~~~~~~~~~~~~~~~~~
若只用集合记录余数,可以知道“循环已经出现”,却不知道左括号应插在哪里。哈希表
``first_position[remainder]`` 同时记录该余数第一次出现时,下一位数字将在结果字符串中
写入的位置。
检查与记录必须发生在生成下一位之前:此时 ``remainder`` 描述的正是“将要生成的后缀”。
重复时在其首次位置插入 ``'('``,当前字符串尾部就是一个完整周期的末端,再追加
``')'``。每个新余数只处理一次,发现重复后不再重新生成已经确定的循环数字。
具体走读
~~~~~~~~
对 ``1 / 6``,整数部分和小数点先得到 ``"0."``:
.. code-block:: text
当前余数 首次位置 生成数字 新余数 当前结果
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`` 不超过正分母可能产生的不同非零余数数量。