题目描述
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.
Example1:
Input: numerator = 1, denominator = 2 Output: "0.5"
Example2:
Input: numerator = 2, denominator = 3 Output: "0.(6)"
解题思路
- 主要是判断余数什么时候重复
- 我们可以将余数作为key，此时的size作为value
- 这样一旦有了重复，我们就可以在此时的size位置中 插入 “(“符号， // 根据 mmap[key] 就是要出现重复的位置
- 然后后面再累加一个“)”即可
-
注意 to_string， 溢出，insert(pos， char),
- 将每个出现的余数都放到哈希表中，如果后面没有重复出现，那么由于一直在进行辗转除法，总归是很快会除尽的。
- 但是如果重复出现了，那就说明循环了。
- 但是也许会有读者有疑问，比如0.2525，分子是2525，分母是10000。看似这里重复了2525，但是其实运算过程中的余数分别是：2525、 5250 、 2500、 5000。所以说小数点后的重复与运算过程中的余数的重复是没有必然关系的。
- 相反，如果是2/3，运算中的余数则一直是6，因为2乘以10再除以3等于6，余下2；进一步还是2乘以10再除以3……
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if(numerator == 0){
return "0";
}
if(denominator == 0){
return "";
}
string res;
unordered_map<long, int> appeared;
if((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)){
res += '-';
}
long p_int = abs((long)numerator / (long)denominator);
res += to_string(p_int);
long rem = abs((long)numerator % (long)denominator);
if(rem == 0){
return res;
}
res += ".";
while(rem){
if(appeared.find(rem) != appeared.end()){
res.insert(appeared[rem], "(");
res += ")";
break;
}
appeared[rem] = res.size();
rem *= 10;
res += to_string(rem / abs((long)denominator));
rem %= abs((long)denominator);
}
return res;
}
};
