【leetcode】Fraction to Recurring Decimal

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;
}
};
上一篇:Data Provider 中没有.net framework Data provider for Mysql 的解决方法


下一篇:Sqlite数据库 找不到请求的 .Net Framework Data Provider。可能没有安装