問題

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

例子

• Given numerator = 1, denominator = 2, return "0.5".

• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

分析

模擬除法的運(yùn)算過程。設(shè)numerator = 10， denominator = 6.

1. numerator = 10, denominator = 6, quotient = 1, remander = 4, res = "1.";
2. numerator = remander * 10 = 40, denominator = 6, quotient = 6, remander = 4, res = "1.6";
3. numerator = remander * 10 = 40, denominator = 6, quotient = 6, remander = 4, res = "1.66".

到第三步可以發(fā)現(xiàn)，以后每一步remander都是4，quotient都是6，即開始循環(huán)。res應(yīng)該為"1.(6)".

所以我們要模擬上面的運(yùn)算，直到remander開始重復(fù)某一數(shù)字，設(shè)該數(shù)字為R。用一個(gè)map來保存remander和它出現(xiàn)的位置。在remander第一次出現(xiàn)R的位置插入'('，在最后的位置插入')'。

除此之外，還有考慮一下幾點(diǎn)：

• numerator和denominator異號時(shí)，在res前加'-';
• quotient和remander要定義成long long，防止溢出，例如numerator = -2147483648, denominator = -1;
• 求int的絕對值時(shí)，有溢出的風(fēng)險(xiǎn)，需要先把int轉(zhuǎn)換成long long.

要點(diǎn)

• 理解小數(shù)循環(huán)節(jié)的含義，能夠模擬除法運(yùn)算：不斷用余數(shù)乘10除以除數(shù)，直到余數(shù)為0。當(dāng)余數(shù)開始出現(xiàn)重復(fù)數(shù)字時(shí)，商的小數(shù)開始循環(huán)；
• 注意數(shù)值類型的溢出問題；
• string關(guān)于char的構(gòu)造函數(shù)為string(size_t n, char c).

時(shí)間復(fù)雜度

O(n), n位數(shù)字的長度

空間復(fù)雜度

O(n)

代碼

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string res;
        if (numerator < 0 ^ denominator < 0)
            res += '-';
        long long numer = abs((long long)numerator);
        long long denom = abs((long long)denominator);
        long long quotient = numer / denom;
        long long remander = numer % denom;
        res += to_string(quotient);
        if (remander == 0) return res;
        res += '.';
        unordered_map<long long, int> map;

        while (remander) {
            quotient = remander * 10 / denom;
            if (map.find(remander) != map.end()) {
                res.insert(map[remander], 1, '(');
                res += ')';
                break;
            }
            map[remander] = res.size();
            res += to_string(quotient);
            remander = remander * 10 % denom;
        }

        return res;
    }
};