题目链接：Fraction to Recurring Decimal

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.

For example,

  • Given numerator = 1, denominator = 2, return “0.5”.
  • Given numerator = 2, denominator = 1, return “2”.
  • Given numerator = 2, denominator = 3, return “0.(6)”.

这道题的要求是将分数转化成循环小数。

模拟除法的过程，直到没有余数或者余数重复。不过要注意以下2个问题：

  • 去掉分子分母符号的时候，由于数据有-2147483648，转化成正数可能溢出，因此需要采用long long类型；
  • 如果余数没重复，在map中记录对应位置，便于发现是循环小数时加入左括号‘(’.

时间复杂度：O(n)

空间复杂度：O(n)

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
40
41
42
43
44
45
46
47
48

class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        // 分子为0
        if(numerator == 0)
            return "0";
        
        string res = "";
        
        // 记录符号
        if(numerator < 0 ^ denominator < 0)
            res += "-";
        // 去掉分子分母符号，存在-2147483648，因此要用long long
        long long n = abs((long long)numerator)；
        long long d = abs((long long)denominator);
        // 记录整数部分
        res += to_string(n / d);
        // 整除，直接返回
        if(n % d == 0)
            return res;
        // 记录小数点‘.’
        res += '.';
        
        unordered_map<int, int> map;
        // 模拟除法过程
        for(long long r = n % d; r > 0; r %= d)
        {
            // 余数出现重复，说明生成循环小数
            if(map.find(r) != map.end())
            {
                res.insert(map[r], 1, '(');
                res += ")";
                break;
            }
            // 余数没重复，在map中记录对应位置
            // 便于循环小数时加入左括号‘(’
            map[r] = res.size();
            // 补一个0
            r *= 10;
            // 记录商，即下一位小数
            res += to_string(r / d);
        }
        
        return res;
    }
};