LeetCode 166：分數轉循環小數——哈希表記錄餘數

題目描述

給定分子 numerator 和分母 denominator，返回小數字符串。若小數部分循環，用括號標記循環節。

示例

• 1/2 → "0.5"
• 2/1 → "2"
• 2/3 → "0.(6)"

核心算法：模擬除法 + 餘數追蹤

1. 處理符號，轉為正數運算（用 long long 防溢出，如 -2147483648）
2. 整數部分直接輸出
3. 餘數為 0 → 結束
4. 小數部分：每步餘數 × 10 除以分母，商為下一位數字
5. 用 unordered_map<long, int> 記錄「餘數 → 在結果字符串中的位置」
6. 若餘數重複 → 找到循環節，插入括號

關鍵細節

• INT_MIN 取絕對值會溢出，必須用 64 位有符號整數
• 餘數為 0 時無循環節
• 字符串插入括號用 insert(pos, "(") 和 push_back(')')

C++ 實現

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        long long n = numerator, d = denominator;
        string res;
        if ((n < 0) ^ (d < 0)) res += '-';
        n = llabs(n); d = llabs(d);
        res += to_string(n / d);
        n %= d;
        if (n == 0) return res;
        res += '.';
        unordered_map<long long, int> pos;
        while (n) {
            if (pos.count(n)) {
                res.insert(pos[n], "(");
                res += ')';
                break;
            }
            pos[n] = res.size();
            n *= 10;
            res += char('0' + n / d);
            n %= d;
        }
        return res;
    }
};

複雜度

• 時間：O(log denominator) —— 餘數最多 denominator 種
• 空間：O(log denominator) —— 哈希表存儲