166. Fraction to Recurring Decimal

这道题要求把一个分数写成无限循环小数的字符串。

可以写成分数的都是有理数，而有理数要么是有限的，要么是无限循环小数，无限不循环的叫无理数。

题目不难，但是处理起来也得费点劲。用到了哈希表，存的是当前的余数和出现的位置。这样如果出现了重复的余数，就可以知道在哪里加左括号。

还有这个题要分正负，所以在做除法的时候需要用绝对值，如果其中一个数是-2147483648，取绝对值的话在int中存不下，会出错，所以先转换成long long。

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        int s1 = numerator >= 0 ? 1 : -1;
        int s2 = denominator >= 0 ? 1 : -1;
        long long num = abs((long long)numerator);
        long long den = abs((long long)denominator);
        long long out = num / den;
        long long rem = num % den;
        unordered_map<long long, int> m;
        string res = to_string(out);
        if(s1 * s2 == -1 && (out > 0 || rem > 0))
            res = "-" + res;
        if(rem == 0)    return res;
        res += ".";
        string s = "";
        int pos = 0;
        while(rem != 0){
            if(m.find(rem) != m.end()){
                s.insert(m[rem], "(");
                s += ")";
                return res + s;
            }
            m[rem] = pos;
            s += to_string((rem * 10) / den);
            rem = (rem * 10) % den;
            ++pos;
        }
        return res + s;
    }
};