题目描述

给定一个分数的分子分母，请用字符串形式返回该分数的值。
如果这个分数是循环小数，则用括号将循环节括起来。

样例1

输入：分子 = 1, 分母 = 2
输出："0.5"

样例2

输入：分子 = 2, 分母 = 1
输出："2"

样例3

输入：分子 = 2, 分母 = 3
输出："0.(6)"

算法

(模拟，高精度除法) $O(n)$

为了方便处理，我们先将所有负数运算转化为正数运算。
然后再算出分数的整数部分，再将精力集中在小数部分。

计算小数部分的难点在于如何判断是否是循环小数，以及找出循环节的位置。
回忆手工计算除法的过程，每次将余数乘10再除以除数，当同一个余数出现两次时，我们就找到了循环节。
所以我们可以用一个哈希表 unordered_map<int,int> 记录所有余数所对应的商在小数点后第几位，当计算到相同的余数时，上一次余数的位置和当前位置之间的数，就是该小数的循环节。

时间复杂度分析：计算量与结果长度成正比，是线性的。所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    string fractionToDecimal(int _n, int _d) {
        long long n = _n, d = _d;
        bool minus = false;
        if (n < 0) minus = !minus, n = -n;
        if (d < 0) minus = !minus, d = -d;
        string res = to_string(n / d);
        n %= d;
        if (!n)
        {
            if (minus && res != "0") return '-' + res;
            return res;
        }

        res += '.';
        unordered_map<long long, int> hash;
        while (n)
        {
            if (hash[n])
            {
                res = res.substr(0, hash[n]) + '(' + res.substr(hash[n]) + ')';
                break;
            }
            else hash[n] = res.size();
            n *= 10;
            res += to_string(n / d);
            n %= d;
        }
        if (minus) res = '-' + res;
        return res;
    }
};