LeetCode Fraction to Recurring Decimal：分數轉循環小數

問題描述

給定分子和分母（整數），返回分數的字符串表示。若小數部分循環，用括號括起循環節。例如 1/2 → "0.5"，2/1 → "2"，2/3 → "0.(6)"。

解題思路

模擬手工除法過程。關鍵：余數出現重複時，從該余數首次出現的位置開始循環。用哈希表記錄「余數 → 在小數部分的位置」。步驟：

1. 處理符號，轉為長整型避免溢出。
2. 整數部分：quotient = num / den，余數 rem = num % den。
3. 若余數為 0 直接返回。
4. 小數部分：循環 rem *= 10; digit = rem / den; rem %= den，記錄 digit 和 rem 的位置。若 rem 重複，插入括號。

代碼實現 (C++)

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

複雜度分析

• 時間複雜度：O(log denominator) 循環節長度。
• 空間複雜度：O(log denominator) 存儲余數位置。

總結

核心在於余數重複檢測，哈希表實現 O(1) 查找。注意負號處理、長整型防溢出、以及插入括號時的字符串操作。