166. 分數到小數

思路

先把整數部分和符號算出，剩下的部分模擬直式除法處理即可。
兩數的範圍都在整個 $\text{int}$ 的範圍中，相除可能會溢出，因此要轉為 $\text{long long}$。 一旦相除時，發現被除數再次出現，代表進入了循環。

程式碼

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0) return "0";
        string res;
        if((numerator < 0) ^ (denominator < 0)) res += "-"; // 符號判斷
        long long n = abs(1LL * numerator);
        long long d = abs(1LL * denominator);
        res += to_string(n / d); // 整數部分
        n %= d;
        if(n == 0) return res; // 如果整除，不需要小數點。
        res += ".";
        unordered_map<long long, int> pos; // 紀錄被除數出現的位置。
        while(n) {
            if(pos.find(n) != pos.end()) {
                res.insert(pos[n], "(");
                res += ")";
                break;
            }
            pos[n] = res.length();
            n *= 10;
            res += to_string(n / d);
            n %= d;
        }
        return res;
    }
};

複雜度分析

• 空間複雜度：$O(n)$，$n$為「可能出現的餘數有幾種」，因此最多會有 $\text{denominator}$ 種，存在哈希表裡面。
• 時間複雜度：$O(n)$