Fraction to Recurring Decimal -- LeetCode
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记录在哪个位置余数开始出现重复，从而可以插入‘（’。
1 class Solution { 2 public: 3 string fractionToDecimal(int numerator, int denominator) { 4 if (numerator == 0) return "0"; 5 string res; 6 //calculate the sign 7 if (numerator < 0 ^ denominator < 0) res += '-'; 8 int64_t n = abs((int64_t)numerator); 9 int64_t d = abs((int64_t)denominator); 10 11 //get the value before '.' 12 res += std::to_string(n / d); 13 if (n % d == 0) return res; 14 15 res += '.'; 16 //use map to keep index, so that we know where to insert the '(' 17 unordered_map<int64_t, int> remains; 18 for (int64_t r = n % d; r; r %= d) { 19 if (remains.count(r) > 0) { 20 res.insert(remains[r], "("); 21 res += ')'; 22 break; 23 } 24 remains.insert(make_pair(r, res.size())); 25 r *= 10; 26 res += std::to_string(r / d); 27 } 28 return res; 29 } 30 };