首页 > 代码库 > 【LeetCode】Fraction to Recurring Decimal
【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)".
Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.
这题就是按定义做。
如果不能整除，就不断进行余数补零除以除数。
维护一个映射表map<long long, int> m, 用来记录每个余数对应返回值ret中的位置。
（1）当出现重复的余数r时，说明找到了循环体，根据m[r]找到ret中位置，加上相应的‘(‘和‘)‘将循环体括起来即可返回。
（2）当余数r为0时，返回ret。
注意点：可能出现INT_MIN/-1的越界情况，因此第一步现将int转为long long int
class Solution {public: string fractionToDecimal(int numerator, int denominator) { return Helper(numerator, denominator); } string Helper(long long numerator, long long denominator) { //convert to 64_int in case INT_MIN/-1 overflow //special case if(denominator == 0) return ""; else if(numerator == 0) return "0"; string ret = ""; if((numerator<0) ^ (denominator<0)) {//one of them is negative, with bit or ret += ‘-‘; numerator = abs(numerator); denominator = abs(denominator); } //integer part if(numerator/denominator == 0) //integer part is 0 ret += ‘0‘; else { long long quotient = numerator/denominator; ret += to_string(quotient); if(numerator%denominator == 0) //divisible return ret; else //not divisible, numerator as remainder numerator -= (quotient*denominator); } //decimal part ret += ‘.‘; string demical; map<long long, int> m; //<remainder, index> pair long long r = numerator; while(r) { if(m.find(r) != m.end()) {//remainder ret.insert(m[r], 1, ‘(‘); //insert (iterator p, size_t n, char c); ret += ‘)‘; break; } m[r] = ret.size(); r *= 10; //next digit ret += to_string(r/denominator); r %= denominator; } return ret; }};
【LeetCode】Fraction to Recurring Decimal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。