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)".

S: hashmap O(n)

一位一位计算，关键是如何找到重复的位数: 用hashmap记录出现过的被除数，若重复的被除数出现则它第一次出现的位置为重复开始位

用(numerator > 0) ^ (denominator > 0)判断两数符号是否一致，避免相乘overflow

取abs也要换成long避免-2147483648的overflow

    string fractionToDecimal(int numerator, int denominator) {
        string result = "";
        if (denominator == 0) return result;
        if (numerator == 0) return "0";
        if ((numerator > 0) ^ (denominator > 0)) result += "-";
        long n = abs((long)numerator);
        long d = abs((long)denominator);
        result += to_string(n / d);
        n = (long)(n % d);
        if (n == 0) return result;
        result += ".";
        string deci = "";
        n *= 10;
        unordered_map<long, int> index;

        for (int i = 0; n > 0; ++i, n *= 10) {      
            if (index.find(n) != index.end()) {
                int start = index[n];
                result += deci.substr(0, start) + '(' + deci.substr(start) + ')';
                return result;
            }
            long num = n / d;
            index[n] = i;
            deci += to_string(num);
            n = (long)(n % d);
        }
        return result + deci;    
    }