Leetcode 166 @Fraction to Recurring Decimal

166. Fraction to Recurring Decimal

Medium

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

这道题难不算难，就是得先观察出这个规律，还有就是一些corner case要覆盖，我最头疼的就是这类数字题，细节太多，关键是谁平时没事会记住这些信息呢？

规律就是：一旦当 dividend % divisor 的remainder ，也就是余数开始循环的时候，说明小数部分就开始循环了，此时可以加上括号了。怎么判断余数开始重复了呢？搬出我们万能的hashmap，每一次把新出现的余数装在hashmap里，对应的value呢，也很特别，是当前fraction(分数)的长度，相当于说下一次放"("时，知道放在哪里。因为第一次在hashmap里找到余数时，fraction此时已经有一个循环的数在上面了。

有几个要考虑的问题，
1. 循环的数会不会不止一位？这样存“（” 只按照往前看一位找，岂不是不对？循环的数字当然可以不止一位，但是每一次出现余数我们都存，下一次再出现已经出现过的余数，说明就是循环开始的地方，往那里插上“（”就对了，再在当前string的末尾插上“）”。随便找一个例子，1/7 = 0. (14285)。

2. INT_MIN = - 2147483648 是valid input，最开始算 sign 的时候，会取它们的绝对值，INT_MAX = 2147483647, 把int_min的绝对值小1，会overflow，所以提前把它们都弄成long，确保不出事儿。

3. 以及记得每一次给remainder * 10。

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
           if (numerator == 0)
           {
               return "0";
           }
           string fraction;
           if (numerator < 0 ^ denominator < 0)
           {
               fraction += "-";
           }
           long dividend = abs((long)numerator), divisor = abs((long)denominator);
           fraction += to_string(dividend / divisor);
           long remainder = dividend % divisor;
            if (remainder == 0)
            {
                return fraction;
            }
            fraction += ".";
            unordered_map<long ,int> hm;
            while (remainder != 0)
            {
                if (hm.count(remainder) > 0)
                {
                    fraction.insert(hm[remainder], "(");
                    fraction += ")";
                    break;
                }
                hm[remainder] = fraction.size();
                remainder *= 10;
                fraction += to_string(remainder / divisor);
                remainder %= divisor;
            }
            return fraction;
    }
};