28
03/2015
[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)".
题目意思：
将分数转化成循环小数。大体思想是：用两个map分别记录商及其位置和余数及其位置，若出现了重复的余数，则表示此余数对应位置的商位开始循环。这道题非常多的陷阱。弄了我好久，代码如下所示
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
string result = "";
long long numberatorL = (long long)numerator;
long long denominatorL = (long long)denominator;
if (numberatorL * denominatorL < 0){ //注意负数的情况
result += "-";
numberatorL = -numberatorL;
}
long long quotient = numberatorL / denominatorL; //商
result += intToStr(quotient);
long long remainder = numberatorL % denominatorL; //余数
if (remainder != 0){
result += '.';
int position = -1;
int repeatStartPosition = -1; //循环起始位
map<int, long long> positionToQuotient; //位置到商，从某个位置开始为循环小数
map<long long, int> remainderToPosition; //余数到位置
remainderToPosition.insert(map<int, int>::value_type(remainder, position));
position++;
while (remainder != 0){
remainder *= 10;
quotient = remainder / denominatorL;
remainder = remainder % denominatorL;
positionToQuotient.insert(map<int, int>::value_type(position, quotient));
map<long long, int>::iterator it = remainderToPosition.find(remainder);
if (it != remainderToPosition.end()){ //若余数已经存在过
repeatStartPosition = it->second + 1;
break;
}
remainderToPosition.insert(map<int, int>::value_type(remainder, position));
position++;
}
for (map<int, long long>::iterator it = positionToQuotient.begin(); it != positionToQuotient.end(); it++){
if (it->first == repeatStartPosition){
result += "(";
}
result += intToStr(it->second);
}
if (repeatStartPosition >= 0){
result += ")";
}
}
return result;
}
private:
string intToStr(long long number){
string result = "";
do{
result = (char)(number % 10 + '0') + result;
number /= 10;
} while (number != 0);
return result;
}
};
0 条评论