166. 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)". Hint:

1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
2. Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
3. Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string res;

        if(numerator == 0)  return "0";

        if(numerator < 0 ^ denominator < 0) res += '-';

        long n = abs((long)numerator);
        long d = abs((long)denominator);

        //计算整数部分
        res += to_string(n / d);

        //整除
        if(n % d == 0)  return res;

        //有小数
        res += ".";

        //记录余数r
        unordered_map<int, int> m;
        for(long r = n % d; r; r %= d){
            //余数已经出现过
            if(m.count(r) > 0){
                res.insert(m[r], 1, '(');
                res += ")";
                break;
            }

            //没有出现此余数，则将此余数在字符串中开始位置记录下来
            m[r] = res.size();

            r *= 10;
            res += to_string(r / d);
        }
        return res;
    }
};