跳转至

166. 分数到小数

题目大意

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 104 。

  • 示例 1：
    • 输入：numerator = 1, denominator = 2
    • 输出："0.5"
  • 示例 2：
    • 输入：numerator = 2, denominator = 1
    • 输出："2"
  • 示例 3：
    • 输入：numerator = 4, denominator = 333
    • 输出："0.(012)"

数据范围：

  • -231 <= numerator, denominator <= 231 - 1
  • denominator != 0

思路&代码

当我们做 两个整数相除（得到小数部分） 时，循环节的本质在于：

  • 小数部分的生成过程是不断「余数 × 10 再除以除数」；
  • 余数的可能取值有限（最多有 除数 - 1 种）；
  • 一旦某个余数重复出现，就说明小数部分开始进入循环。

假设我们要算 a / b，其中 a, b 是整数，且 b > 0。

  1. 先取整部分： \(\text{intPart}=a/b\) 余数：\(r=a\%b\)
  2. 进入小数部分循环：
    每一步：
    • 把余数乘 10：r *= 10
    • 当前小数位 = r / b
    • 更新余数：r = r % b
  3. 判断循环节：
    用一个 map<int, int> 记录「余数 → 小数位下标」。
    • 如果某个余数之前出现过，说明小数开始重复，循环节区间就是 [上一次位置, 当前下标)。
    • 如果余数变成 0，说明小数部分终止（有限小数）。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";

    string res;
    // 处理正负号
    if ((numerator < 0) ^ (denominator < 0)) res += "-";

    long long n = llabs((long long)numerator);
    long long d = llabs((long long)denominator);

    // 整数部分
    res += to_string(n / d);
    long long r = n % d;
    if (r == 0) return res;

    res += ".";

    // 小数部分
    unordered_map<long long, int> seen; // 余数 -> 位置
    string frac;
    int pos = 0;
    while (r != 0) {
        if (seen.count(r)) {
            // 找到循环节
            int start = seen[r];
            frac.insert(start, "(");
            frac.push_back(')');
            res += frac;
            return res;
        }
        seen[r] = pos++;
        r *= 10;
        frac.push_back('0' + (r / d));
        r %= d;
    }

    res += frac;
    return res;
}