O(n) time
这道题的hashmap的key必须是余数（被除数）不能用商（数字）因为商可能相同但被除数不同，比如1/333小数部分开始都是0但是被除数是不一样的所以并不是循环节，真正的循环节首尾的被除数必须是一样的！
- 判断被除数是否为0，是0直接返回0
- 判断结果是否为负
- 先处理整数部分，如果余数为0，直接返回结果
- 处理小数部分，用一个hashmap维护小数部分每个数字的下标，方便后边插入左括号
- 如果找到重复的数字，看该数字是否为0，如果是0则没有循环节不需要插入括号
- 用hashmap找到需要插入左括号的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
string integer, decimal;
if ((numerator ^ denominator) < 0) {
integer += '-';
}
long n = labs(numerator), d = labs(denominator);
integer += to_string(n / d);
n %= d;
if (0 == n) return integer;
integer += '.';
unordered_map<int, int> m;
while (n > 0 && m.count(n) == 0) {
m[n] = decimal.length();
n *= 10;
decimal += to_string(n / d);
n %= d;
}
if (n == 0) return integer + decimal;
decimal.insert(m[n], "(");
return integer + decimal + ")";
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
string integer, decimal;
if ((numerator ^ denominator) < 0) {
integer += '-';
}
long n = labs(numerator), d = labs(denominator);
integer += to_string(n / d);
n %= d;
if (0 == n) return integer;
integer += '.';
n *= 10;
int i(-1);
unordered_map<int, int> m;
auto it = m.find(n);
while (it == m.end()) {
m.emplace(n, ++i);
decimal += to_string(n / d);
n %= d;
if (0 == n) return integer + decimal;
n *= 10;
it = m.find(n);
}
decimal.insert(it->second, "(");
return integer + decimal + ')';
}
};
|