Fraction to Recurring Decimal
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.
For example,
- Given numerator = 1, denominator = 2, return "0.5".
- Given numerator = 2, denominator = 1, return "2".
- Given numerator = 2, denominator = 3, return "0.(6)".
0.16
6 ) 1.00
0
1 0 <-- Remainder=1, mark 1 as seen at position=0.
- 6
40 <-- Remainder=4, mark 4 as seen at position=1.
- 36
4 <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).
如果发现余数曾经出现过，则说明开始循环了，利用一个hash表记录余数出现的位置即可
注意INT_MIN转换成正数会溢出，故需要先把数字先转为long long int
注意余数也要去long long int，因为-1,2147483648这种情况下，余数在计算乘以10的过程中会溢出
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
string ans="";
if(numerator==) return "";
long long int n=numerator;
long long int d=denominator;
n=abs(n);
d=abs(d);
if(numerator<^denominator<) ans.push_back('-');
map<long long int,int> hash;
ans+=to_string(n/d);
long long int rem=n%d;
if(rem!=) ans.push_back('.');
while(rem!=)
{
if(hash.find(rem)!=hash.end())
{
ans.insert(hash[rem],"(");
ans.push_back(')');
break;
}
hash[rem]=ans.length();
ans+=to_string(rem*/d);
rem=(rem*)%d;
}
return ans;
}
};