Example 3:
Input: numerator = 2, denominator = 3 Output: "0.(6)"
1. 解析
题目大意,将分数转换为循环小数,不是很难,关键点就在于如何查找循环的部分
2. 分析
任何有理数都将分为两部分,整数部分和小数部分,故可以将分数分开进行处理
1) 求解整数部分,若当前分子numerator整除分母denominator,即无小数部分,直接返回numerator / denominator
2) 若当前存在小数部分,即不整除,单独求解小数部分,为了方便查找当前小数部分是否为循环小数,利用hashtable进行存储除数和其对应的小数位置,若当前分子numerator不为0:
①若hashtable不存在当前分子numerator,在hashtable中记录下该位置;
②hashtable存在当前分子numerator,则该位置即为循环开始位置,进行处理后直接返回即可;
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
bool signal = false;
if ( (numerator == 0) || (numerator < 0 && denominator < 0) ||
(numerator > 0 && denominator > 0) )
signal = true; //正数
string res = signal ? "" : "-";
map repeat;
long long long_numerator = abs((long long)numerator);
long long long_denominator = abs((long long)denominator);
if (long_numerator % long_denominator == 0)
return res + to_string(long_numerator / long_denominator);
res += to_string(long_numerator / long_denominator) + "."; //整数部分
long_numerator %= long_denominator;
string str = ""; //小数部分
int pos = 0;
while (long_numerator != 0){
long_numerator *= 10;
if (repeat.count(long_numerator)){ //找到循环部分
str.insert(repeat[long_numerator], "(");
str += ")";
break;
}
else{
repeat[long_numerator] = pos;
}
pos++;
str += to_string(long_numerator / long_denominator);
long_numerator %= long_denominator;
}
return res + str;
}
};