Massive Algorithms: leetcode 166: Fraction to Recurring Decimal

leetcode 166: Fraction to Recurring Decimal

leetcode 166: Fraction to Recurring Decimal - 西施豆腐渣 - 博客频道 - CSDN.NET
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)".

Input : Numerator = 50, Denominator = 22
Output : Recurring sequence is 27
Explanation : 50/22 = 2.272727272.....

[分析]
1、负数的处理2、INT_MIN的处理，将INT_MIN转化为正数会溢出
我们可以设置一个哈希表，存储每一次的余数，以及该余数在返回结果result中的下标。每一次得到新的余数，就查询该余数是否已经在哈希表中，是的话说明开始循环了，那么直接在result中该余数对应的位置后面插入‘（’，result末尾加上‘）’，结束运算。如果在哈希表中没找到，则继续正常运运算。
关键是确定发生循环的位置, 使用map存所有余数, 当余数已经出现过时, 即发生了循环.
[注意]
Overflow, 符号的处理, 分开两个函数, 使代码更容易读

public String fractionToDecimal(int numerator, int denominator) {
long num = numerator;
long den = denominator;
boolean neg = num * den < 0;
num = Math.abs(num);
den = Math.abs(den);
String res = neg ? "-" + Long.toString(num/den) : Long.toString(num/den);
long remainder = num%den;
return (remainder==0) ? res : (res + "." + getDec(remainder, den));
}
private StringBuilder getDec(long remainder, long den) {
Map<Long, Integer> map = new HashMap<Long, Integer>();
int i=0;
StringBuilder sb = new StringBuilder();
while(remainder!=0 && !map.containsKey(remainder)) {
map.put(remainder, i);
++i;
remainder *= 10;
sb.append(Long.toString(remainder/den));
remainder %= den;
}
if(remainder!=0){
sb.insert((int)map.get(remainder), '(');
sb.append(')');
}
return sb;
}

https://leetcode.com/discuss/31521/short-java-solution
https://leetcode.com/discuss/77994/simple-and-short-solution-in-java
public String fractionToDecimal(int numerator, int denominator) { if (denominator == 0) return ""; StringBuilder str = new StringBuilder(); HashMap<Long, Integer> map = new HashMap<Long, Integer>(); if (numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0) { str.append('-'); } long num = Math.abs((long)numerator); long den = Math.abs((long)denominator); long n = num/den; long reminder = num % den; str.append(n); if (reminder == 0) return str.toString(); else str.append('.'); while(!map.containsKey(reminder)) { map.put(reminder,str.length()); n = reminder*10/den; reminder = reminder*10%den; if (reminder != 0 || reminder == 0 && !map.containsKey(reminder)) { str.append(n); } } if (reminder != 0) { str.insert(map.get(reminder),"("); str.append(')'); } return str.toString(); }
https://leetcode.com/discuss/23079/my-clean-java-solution
public String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) { return "0"; } StringBuilder res = new StringBuilder(); // "+" or "-" res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : ""); long num = Math.abs((long)numerator); long den = Math.abs((long)denominator); // integral part res.append(num / den); num %= den; if (num == 0) { return res.toString(); } // fractional part res.append("."); HashMap<Long, Integer> map = new HashMap<Long, Integer>(); map.put(num, res.length()); while (num != 0) { num *= 10; res.append(num / den); num %= den; if (map.containsKey(num)) { int index = map.get(num); res.insert(index, "("); res.append(")"); break; } else { map.put(num, res.length()); } } return res.toString(); }
http://blog.csdn.net/ljiabin/article/details/42025037

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       4      <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).

The key insight here is to notice that once the remainder starts repeating, so does the divided result.

You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.

The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.

Just like the question Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as -2147483648 / -1.

难点：如何识别循环体？

解决方法：用一个HashMap记录每一个余数，当出现重复的余数时，那么将会进入循环，两个重复余数之间的部分就是循环体。

示例：1/13=0.076923076923076923...，当小数部分第二次出现0时，就意味着开始了循环，那么需要把076923用括号括起来，结果为0.(076923)。

涉及技巧：1）在不断相除的过程中，把余数乘以10再进行下一次相除，保证一直是整数相除；2）HashMap的key和value分别是<当前余数, 对应结果下标>，这样获取076923时就可根据value值来找。

注意点1：考虑正负数，先判断符号，然后都转化为正数；

注意点2：考虑溢出，如果输入为Integer.MIN_VALUE，取绝对值后会溢出。

Java编程误区：一定要先把 int 转为 long，然后再取绝对值。如果写成 long num = Math.abs(numerator) 就会有问题，因为这句代码在 numerator=Integer.MIN_VALUE 时相当于 long num = Math.abs(-2147483648)，这样得到的 num还是 -2147483648。

https://segmentfault.com/a/1190000003794677

整数部分很好处理，只要注意正负号的区分就行了，但是如何处理小数部分呢。如果只是简单的除法，那我们每次把余数乘以10，再除以被除数就可以得到当前位的小数了，得到新的余数，直到余数为0。难点在于，对于无尽循环小数，我们一直这么做永远也不能让余数变为0。这里我们可以用一个哈希表记录每次的余数，如果余数出现重复的时候，说明就产生循环了。为了能找出小数中循环的部分，我们在用哈希表时，还要把每个余数对应的小数位记录下来，这样子我们一旦遇到重复，就知道是从哪里开始循环的。

如果输入的被除数很大，那么余数乘以10有可能溢出，所以我们用long来保存numerator和denominator。

    public String fractionToDecimal(int numerator, int denominator) {
        long num = numerator;
        long den = denominator;
        if(num == 0 || den == 0){
            return "0";
        }
        // 判断结果正负号
        boolean negative = (num > 0 && den < 0) || (num < 0 && den > 0);
        num = Math.abs(num);
        den = Math.abs(den);
        // 得到整数部分
        String integ = (negative ? "-" : "") + String.valueOf(num / den);
        // 如果存在小数部分
        if(num % den != 0){
            num = num % den;
            HashMap<Long, Integer> map = new HashMap<Long, Integer>();
            int pos = 0;
            map.put(num, pos);
            StringBuilder frac = new StringBuilder();
            // 计算小数部分
            while(num != 0){
                // 先把算出的小数加上，再判断余数是否重复，如果余数重复的话，小数会从下一个开始重复
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果该余数之前出现过，说明有循环，上次出现的位置到当前位置就是循环的部分
                if(map.containsKey(num)){
                    // 将非循环部分和循环部分分开
                    String pre = frac.substring(0, map.get(num));
                    String loop = frac.substring(map.get(num));
                    // 返回有循环的结果
                    return integ + "." + pre + "(" + loop + ")";
                }
                pos++;
                // 记录下当前余数和他对应小数的位置
                map.put(num, pos);
            }
            // 返回无循环有小数的结果
            return integ + "." + frac.toString();
        }
        // 返回无小数的结果
        return integ;
    }

http://yuanhsh.iteye.com/blog/2176178

public String fractionToDecimal(int numerator, int denominator) {
if(denominator == 0) return "NaN"; //特殊情况1
if(numerator == 0) return "0"; //特殊情况2
// 如果两个数符号不同，结果为负数
String sign = (denominator>>>31^numerator>>>31) == 1 ? "-" : "";
// 先把除数和被除数转为long，以免除法和绝对值运算的时候溢出
// 比如 -2147483648/-1 = -2147483648, abs(-2147483648) = -2147483648
long num = numerator, den = denominator;
num = Math.abs(num);
den = Math.abs(den);
long major = num / den;
long rem = num % den;
if(rem == 0) return sign+major;
StringBuilder ans = new StringBuilder(sign + major + '.');
Map<Long, Integer> map = new HashMap<Long, Integer>();
while(rem != 0) {
// 如果余数已经出现过一次，那么循环要开始了
if(map.containsKey(rem)) {
int index = map.get(rem);
ans.insert(index, '(').append(')');
break;
} else {
ans.append(rem * 10 / den);
map.put(rem, ans.length()-1);
}
rem = rem * 10 % den;
}
return ans.toString();
}

我们还可以通过LinkedHashSet来做。

public String fractionToDecimal(int numerator, int denominator) {
if(denominator == 0) return "NaN";
if(numerator == 0) return "0";
String sign = (numerator>>>31^denominator>>>31) == 1 ? "-" : "";
long a = numerator, b = denominator;
a = Math.abs(a);
b = Math.abs(b);
String part1 = a / b + "";
long mod = a % b;
if(mod == 0) return sign+part1;
long remain = mod;
Set<Long> s = new LinkedHashSet<>();
while (!s.contains(mod) && mod != 0) {
s.add(mod);
mod = (mod * 10) % b;
}
String part2 = "";
boolean repeated = false;
for (long i : s) {
if (i == mod) {
part2 += "(";
repeated = true;
}
part2 += (remain * 10) / b;
remain = (remain * 10) % b;
}
// if (mod == 0)
// part2 += "(0";
if(repeated) {
part2 += ")";
}
return sign + part1 + "." + part2;
}

http://buttercola.blogspot.com/2015/08/leetcode-fraction-to-recurring-decimal.html

        if (denominator == 0) {

            return "inf";

}

        if (numerator == 0) {

            return "0";

}

        String result = "";

        boolean neg = false;

        // Chceck if any negative number

        if ((numerator < 0) ^ (denominator < 0)) {

            neg = true;

}

 6         if (numerator<0 ^ denominator<0)
 7             res = "-";

http://zwzbill8.blogspot.com/2015/05/leetcode-fraction-to-recurring-decimal.html

        int n = numerator;
        int d = denominator;
        if (n == Integer.MIN_VALUE) {
            String s = n + "";
            if (d == 1) return s;
            if (d == -1) return s.substring(1);
        }
        if (1.0 * n / d < 0) {
            return "-" + fractionToDecimal(-n, d);
        }

https://leetcode.com/discuss/20515/my-java-solution
public static String fractionToDecimal(int numerator, int denominator) { String res = ""; long a = Math.abs((long) numerator); long b = Math.abs((long) denominator); if ((denominator < 0 && numerator > 0) || (denominator > 0 && numerator < 0)) { res += "-"; } long intPart= a / b; res += intPart; if (a % b == 0) { return res; } res += "."; long remainder = a % b; HashMap<Long, Integer> map = new HashMap<Long, Integer>(); int i = 1; map.put(remainder, 1); Queue<Long> queue = new LinkedList<Long>(); int begin = -1; while (remainder != 0) { i++; long tmp = remainder * 10 / b; remainder = remainder * 10 % b; if (map.containsKey(remainder)) { begin = map.get(remainder); queue.offer(tmp); break; } else { map.put(remainder, i); queue.offer(tmp); } } if (remainder == 0) { while (!queue.isEmpty()) { res += queue.poll(); } } else { int j = 1; while (!queue.isEmpty()) { long cur = queue.poll(); if (j != begin) { res += cur; } else { res = res + "(" + cur; } j++; } res += ")"; } return res; }
http://bookshadow.com/weblog/2014/12/17/leetcode-fraction-recurring-decimal/
C++ version: http://www.cnblogs.com/higerzhang/p/4177355.html
http://blog.csdn.net/u012162613/article/details/41998617

Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5.
Read full article from leetcode 166: Fraction to Recurring Decimal - 西施豆腐渣 - 博客频道 - CSDN.NET

leetcode 166: Fraction to Recurring Decimal

Labels

Popular Posts