Cinte's Leetcode Record
0%

166. 分数到小数

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

166. 分数到小数

主要难点是对于循环小数的处理，当循环小数出现时，表示计算式子也出现了循环，由于分母在这里是始终保持不变的，所以循环的出现等价于分子的循环，也就是余数的循环。因此，当出现同一个余数2次时，表示开始循环了，而循环小数的起始处就是第一次出现这个余数的时候。使用map来记录每个余数的出现及其第一次出现的位置即可在后续出现时使用括号括起来。

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
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator == 0)
            return "";
        if(numerator == 0)
            return "0";
        // 防止溢出，转换为long
        // 在win32和win64和linux32中，long和int都是32位(双字)，但是在linux64中long为64位
        // 但是long long一般都是64位
        long lNumerator = static_cast<long>(numerator);
        long lDenominator = static_cast<long>(denominator);
        string ret;
        if(lNumerator < 0 ^ lDenominator < 0)
            ret.push_back('-');
        lNumerator = labs(lNumerator);
        lDenominator = labs(lDenominator);
        ret += to_string(lNumerator / lDenominator);
        if(lNumerator % lDenominator)
            ret.push_back('.');
        int index = ret.size() - 1;
        unordered_map<long, int> record;
        while(lNumerator % lDenominator)
        {
            lNumerator = (lNumerator % lDenominator) * 10;
            if(record.count(lNumerator))
            {
                ret.insert(record[lNumerator], "(");
                ret.push_back(')');
                break;
            }
            // 这里记录的是余数而不是当前的数位，因为只有余数相同时才能保证后面都相同
            record[lNumerator] = ++index;
            ret += to_string(lNumerator / lDenominator);
            
        }
        return ret;
    }
};