`

Leetcode - Fraction to Recurring Decimal

 
阅读更多
[分析]
处理int型整数运算时,为避免溢出,省事的做法就是内部转为long类型处理,不然极可能在极值case上栽跟头,比如int a = Integer.MIN_VALUE, int b = -1 和 long a = Integer.MIN_VALUE, long b = -1, 两者a / b的结果是不一样的,前者会发生溢出,
在比如Math.abs(Integer.MIN_VALUE) 结果竟然是Integer_MIN_VALUE,这都是各种Wrong Answer耐心地告诉我的。
实现2参考https://leetcode.com/discuss/23079/my-clean-java-solution, 有条理的一步步构造出答案,觉得这种方式实现更不容易出错些,自己的实现1就犯过在判断符号后忘记讲intPart取绝对值导致的错误。

public class Solution {
    // especially take care of case like -2147483648 / -1
    // Method 2
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0)
            return "Error: divide zero.";
        if (numerator == 0)
            return "0";
        StringBuilder res = new StringBuilder();
        res.append((numerator > 0 ^ denominator > 0) ? "-" : "");
        long a = Math.abs((long)numerator);
        long b = Math.abs((long)denominator);
        //integer part
        res.append(a / b);
        long mod = a % b;
        if (mod == 0)
            return res.toString();
        //fraction part
        res.append(".");
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        map.put(mod, res.length());
        while (mod != 0) {
            mod *= 10;
            res.append(mod / b);
            mod %= b;
            if (map.containsKey(mod)) {
                res.insert(map.get(mod), "(");
                res.append(")");
                break;
            } else {
                map.put(mod, res.length());
            }
        } 
        return res.toString();
    }
    // Method 1
    public String fractionToDecimal1(int numerator, int denominator) {
        long a = numerator, b = denominator; // Attention! 
        if (b == 0) return "Divide zero exception.";
        long intPart = a / b;
        long mod = a % b;
        if (mod == 0) 
            return String.valueOf(intPart);
            
        boolean isNeg = (a > 0 ^ b > 0) ? true : false;
        intPart = Math.abs(intPart);
        mod = Math.abs(mod);
        b = Math.abs(b);
        
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        StringBuilder fractionPart = new StringBuilder();
        int i = 0;
        while (mod != 0 && !map.containsKey(mod)) {
            map.put(mod, i++);
            mod *= 10;
            fractionPart.append(mod / b);
            mod = mod % b;
        }
        if (mod == 0) {
            return (isNeg ? "-" : "") + intPart + "." + fractionPart.toString();
        } else { 
            int startRepeat = map.get(mod);
            return (isNeg ? "-" : "") + intPart + "."
                + fractionPart.substring(0, startRepeat)  
                + "(" + fractionPart.substring(startRepeat, fractionPart.length()) + ")";
        }
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics