思路: 参考https://discuss.leetcode.com/topic/6079/accepted-cpp-solution-with-explainations/24. 这题的最难点在于找循环体. 循环体是要找分子对于分母的余数何时重复, 如果当前余数在之前出现过了就说明从此时开始循环了, 所以要拿一个哈希记录所有出现过的余数的位置. 然后还有要注意的是所有数字类型都要用长整型, 这样可以避免overflow的情况.
string fractionToDecimal(long long numerator, long long denominator) { // 分母为0直接返回空字符串 if (! denominator) return ""; // 分子为0直接返回"0" if (! numerator) return "0"; string res = ""; // 确定是否有负号 if (numerator < 0 ^ denominator < 0) res += '-'; // 分子分母去符号 long long n = abs(numerator); long long d = abs(denominator); // 结果串添加整数部分 res += to_string(n / d); // 如果整除了就结束, 直接返回结果串 if (! (n % d)) return res; // 添加小数点 res += '.'; long long r = n % d; unordered_map<long long, int> m; while (r) { // 余数出现过了, 添加括号, 返回结果串 if (m.count(r)) { res.insert(m[r], 1, '('); res += ')'; return res; } m[r] = res.length(); // 继续取余, 并把结果添加到结果串中 r *= 10; res += to_string(r / d); r %= d; } return res; }