LeetCode (Math) Fraction to Recuring Decimal

2018-07-11

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.

Example 1:

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

Example 2:

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

Example 3:

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

思路：一开始采用了字符串判断循环的算法，发现可能出现的情况太多了，没有办法求解。后来看到了一个非常巧妙的算法，我们每次都作除，然后取整数部分，然后余数*10，继续下去。直到我们发现之前出现过的被除数出现了就说明这中间的就是循环体，然后取出来即可。这道题还需要考虑正负的不同情况，以及int型的边界溢出情况。代码如下：

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        
        if (denominator == 0) {
            return "";
        }
        
        String ans = "";
        //如果是负数加负号
        if ((numerator > 0) ^ (denominator > 0)) {
            ans += "-";
        }
        //为避免溢出
        long num = numerator;
        long den = denominator;
        
        num = Math.abs(num);
        den = Math.abs(den);
        
        long res = num / den; 
        ans += String.valueOf(res);
        
        //这个地方给余数乘10是为了接下来的小数部分的判断
        long rem = (num % den) * 10;
        if (rem == 0) {
            return ans;
        }
        //开始小数部分的计算
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        ans += ".";
        //当余数不为0时始终判断当前的余数是否已经在之前的map中出现过，如果出现过，就说明有循环体。
        while (rem != 0) {
            if (map.containsKey(rem)) {
                int begin = map.get(rem);
                String ps1 = ans.substring(0, begin);
                String ps2 = ans.substring(begin, ans.length());
                ans = ps1 + "(" + ps2 + ")";
                return ans;
            }
            
            map.put(rem, ans.length());
            res = rem / den;
            ans += String.valueOf(res);
            rem = (rem % den) * 10;
            
        }
        
        return ans;
        
    }
}