题目描述#
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 。
示例 1：
输入： numerator = 1, denominator = 2 输出： “0.5”
示例 2：
输入： numerator = 2, denominator = 1 输出： “2”
示例 3：
输入： numerator = 4, denominator = 333 输出： “0.(012)”
提示：
-2^31 <= numerator, denominator <= 2^31 - 1denominator != 0
解题思路#
这道题我们采用长除法的思路来做，这样我们不直接通过浮点数计算，而是一步步将小数部分转换到整数部分，依次得到小数的每一位。
例如： 计算 7 / 4 = 1.75
- 首先是整数部分：7 / 4 = 1 余 3
- 记录余数 3
- 第一位小数：3 * 10=30 , 30/4 = 7 余 2
- 记录余数 2
- 第二位小数：2 * 10=20 , 20/4 = 5 余 0 得到结果为 1.75
再例如： 计算 1 / 6 = 0.1666666…
- 首先是整数部分：1 / 6 = 0 余 1
- 记录余数 1
- 第一位小数： 1 * 10 = 10 , 10 / 6 = 1 余 4
- 记录余数 4
- 第二位小数： 4 * 10 = 40 , 40 / 6 = 6 余 4
- 余数 4 出现过，6 是循环节
Note这种方法相当于每次将小数点往右移一位，以此来得到小数的下一位
因此我们可以总结出以下解题步骤：
1. 整数部分#
这里会有两种情况，
- 除得尽：则答案就是结果的字符串形式
- 除不尽：需要继续处理小数部分
2. 小数部分#
同样是两种情况，
- 通过长除法最终能结束：有限小数，直接把小数部分接上就行
- 通过长除法结束不了：无限循环小数，需要找循环节
3. 怎么找循环节#
我们来看余数部分，假如说余数在某一次和这一次一样的，后面的结果也一定是一样的，也就是发生了循环。 我们通过哈希表，映射一下余数和对应的位置，从而得到循环节。
4. 需要注意的点#
- 需要先判断分子分母的正负，看看答案是否需要加负号
- 因为负数最小到 ，取正会导致溢出，所以需要 long long
Tip在判断结果的正负时，需要讨论分子分母的正负，这里我们可以直接使用异或来解决，异或，同 0 异 1，所以可以这样写：
cppif(x < 0 ^ y < 0) ans.push_back('-');
纠结部分#
在判断循环节部分的代码，我之前是这样写的：
//小数部分
unordered_map<ll,int> index;
int cnt=0;
string decimal;
while(remainder!=0) {
remainder *= 10;
int cur = remainder/y;
remainder %= y;
if(index.count(remainder)) {//之前有过
ans += decimal.substr(0,index[remainder]) + "(" + decimal.substr(index[remainder]) + ")";
return ans;
}
index[remainder] = cnt++;
decimal += (to_string(cur));
}
ans += decimal;结果在解决 1/6 时发现了问题，因为余数依次为 1、4、4，结果在第二次发现 4 时就终止了，这时 ans 是 0.(1)
Error
- 首先是整数部分：1 / 6 = 0 余 1
- 记录余数 4
- 第一位小数： 1 * 10 = 10 , 10 / 6 = 1 余 4
- 余数 4 出现过，1 是循环节
Why因为实际上第一个余数 1 对应的应该是第一位小数，但是这版代码误将下一次的余数和当前的小数点做了对应，自然就不对了
完整代码#
#define ll long long
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
ll x = numerator;
ll y = denominator;
if(x==0) return to_string(0);
string ans;
if(x < 0 ^ y < 0) ans.push_back('-');
x = abs(x),y = abs(y);
//整数部分
ll remainder = x % y;
if(remainder==0) {
ans += to_string(x/y);
return ans;
}else {
ans += to_string(x/y);
}
ans.push_back('.');
//小数部分
unordered_map<ll,int> index;
int cnt=0;
string decimal;
while(remainder!=0) {
if(index.count(remainder)) {//之前有过
ans += decimal.substr(0,index[remainder]) + "(" + decimal.substr(index[remainder]) + ")";
return ans;
}
index[remainder] = cnt++;
remainder *= 10;
int cur = remainder/y;
remainder %= y;
decimal += (to_string(cur));
}
ans += decimal;
return ans;
}
};