首页 > 代码库 > [C++]LeetCode: 82 Fraction to Recurring Decimal
[C++]LeetCode: 82 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).
关键点就是如何确定循环体?
我们用一个hashmap记录每一个余数,以及该余数出现的位置,当出现重复的余数时,说明除法开始进入循环,两个重复余数之间的部分就是循环体。
示例:1/13=0.076923076923076923...,当小数部分第二次出现0时,就意味着开始了循环,那么需要把076923用括号括起来,结果为0.(076923)。
Attention:
1. HashMap的构造
HashMap<key, value>分别对应<当前余数,对应的结果下标(位置)>。这样可以根据key即余数来判断是否进入循环;并且这样之后才能在循环体的第一个数前插入‘(’;这种利用map的方法十分巧妙。既标记了余数,又标记了位置。
2. 考虑正负数,和溢出
考虑结果的正负数,我们先判断符号,然后都转为正数运算。
考虑溢出,如果输入为INT.MIN_VALUE, 取绝对值后会溢出,所以我们需要调整计算的分子分母和余数的类型为long 或 long long.
<span style="font-size:14px;"> //(2)得到绝对值 //int n = abs(numerator); //int d = abs(denominator); long long int n = numerator, d = denominator; n=abs(n); d=abs(d); //(3) 计算整数部分 ret += to_string(n/d); long long int r= n % d; //余数r </span>
溢出结果 将变成负数的除法
30 / 35 test cases passed. | Status: Wrong Answer |
Submitted: 32 minutes ago |
Input: | -1, -2147483648 |
Output: | "0.000000000-4-6-5-6-6-1-2-8-7-30-7-7-3-9-2-5-7-8-1-2-5" |
Expected: | "0.0000000004656612873077392578125" |
3. 先处理特殊情况,分子或分母为0
<span style="font-size:14px;"> //计算特殊情况,分子/分母为0 if(numerator == 0) return "0"; if(denominator == 0) return "";</span>4. 注意我们计算除法的步骤:
(1)先判断符号 (2)计算整数部分,是否有余数,有,加小数点‘.‘,继续计算;无,返回结果 (3)余数补零,和分母作除法,计入结果(r *= 10, ret += to_string(r / d))(4) 如果还有余数,将余数作为下一次计算的分子(r %= d)直到出现循环或者没有余数,结束计算。
5. string的insert函数
string& insert (size_t pos, size_t n, char c);
复杂度:O(1) 空间复杂度O(1) 都是常数。可以表示为分数,说明一定是有理数。AC Code:
<span style="font-size:14px;">class Solution { public: string fractionToDecimal(int numerator, int denominator) { //计算特殊情况,分子/分母为0 if(numerator == 0) return "0"; if(denominator == 0) return ""; string ret; //(1)判断符号位 if(numerator < 0 ^ denominator < 0) ret += '-'; //(2)得到绝对值 //int n = abs(numerator); //int d = abs(denominator); long long int n = numerator, d = denominator; n=abs(n); d=abs(d); //(3) 计算整数部分 ret += to_string(n/d); long long int r= n % d; //余数r if(r == 0) return ret; ret += '.'; //(4) 计算小数部分 unordered_map<int, int> pmap; //记录位置信息 余数的位置 while(r) { //如果这个余数出现过,说明分数除法开始循环 停止计算,在第一次出现的位置插入‘(’,在最后插入‘)’ if(pmap.count(r) == 1) { ret.insert(pmap[r], 1,'('); ret += ')'; return ret; } //记录此时的余数和位置 pmap[r] = ret.size(); //如果没有出现循环,按照手写计算除法的方法计算除法: 补零,做除法;然后取余数,作为下一次计算分子 r *= 10; ret += to_string(r / d); r %= d; } return ret; } };</span>
[C++]LeetCode: 82 Fraction to Recurring Decimal