166. Fraction to Recurring Decimal

本文主要是介绍166. Fraction to Recurring Decimal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

166. 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:
输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:
输入: numerator = 2, denominator = 1
输出: "2"
示例 3:
输入: numerator = 2, denominator = 3
输出: "0.(6)"

解法一：

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:string fractionToDecimal(int numerator, int denominator) {if(numerator == 0) return "0";//防止0/denominator = “-0”的情况long a = abs((long)numerator);long b = abs((long)denominator);string res = (numerator ^ denominator) > 0 ? "" : "-";//符号部分;res += to_string(a / b);//整数部分a %= b;//余数if(!a) return res;res += '.';a *= 10;unordered_map<int, size_t> um;//被除数，索引while(a) {//开始处理小数部分res += to_string(a / b);//商um[a] = res.size() - 1;a %= b;//取余数a *= 10;//余数乘10作为下一步的被除数if(um.count(a)) return res.insert(um[a], "(") + ')';}return res;}
};

解法一：

两个整数相除结果一定是个有限小数或者循环小数，所以使用一个哈希表记录计算过程中出现过的被除数，如果遇到重复出现的被除数，说明这里是循环的末尾。