首页 > 代码库 > Leetcode: Fraction to Recurring Decimal
Leetcode: 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.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)".
这道题与Divide Two Integer那道题很像，但是却不一样。不一样的原因在于
1. divide two integer要求的返回的是int值。所以那道题Integer.MIN_VALUE / -1要特殊讨论，返回Integer.MAX_VALUE. （直接除还是会是Integer.MIN_VALUE, 因为b = -a 在计算机内部是 b = ~a + 1 这样处理的）而这道题要求返回的是String, 不用考虑Integer的范围
2. 虽然divide two Integer和这道题一样，都需要把numerator和denominator转化为long先，但是原因是不一样的。Divide Two Integer是怕移位溢出，因为其中有一步是 while(num >= (den<<i)) { i ++; }。而这道题转换成long是为了Math.abs的时候，不溢出。因为结果是String, 不考虑Integer范围，所以abs(-128)应该return string形式的128。但是如果用Integer, 因为-128~127. Math.abs(-128)会变成128,但是int范围是127.所以会溢出。转换成long这样Math.abs会防止溢出。
反正注意这两个题目的区别。divide two integer是要求返回的int，有范围要求，这个题目没有，只要求返回结果的string。不需要转换成int范围内的值。
然后谈谈怎么除得小数的问题，我的想法是double division, 就是像double d = ((double) num) / denom; 这样。可行的方法有：
double b = ((double)317)/219;System.out.println(b);double b = 317.0/219;System.out.println(b);
double b = 317d/219d;但是这样子是不行的：
double b = 317/219;System.out.println(b);这样除完之后，再用Double.toString()把它转化为String再处理无限循环的问题。但是好像那个时候再找是从哪里开始循环的，不太容易。
于是参考了网上的思路：
核心思想就是：模仿除法的过程，然后用hashmap存储numerator的值，如果出现了相同的numerator那么就出现了cycle，
利用stringbuilder来append string，hashmap里面 key是numerator，value是stringbuilder.length，这样出现了cycle，知道如何去插入"("，再append")".
还要记得在第一次除法完成之后，加上小数点，因为第一次除法就可以把整个整数部分全算出来了，接下来小数部分才是一位一位地算
1 public class Solution { 2 public String fractionToDecimal(int numerator, int denominator) { 3 long num = (long)numerator; 4 long den = (long)denominator; 5 boolean isNeg = false; 6 if (num < 0) isNeg = !isNeg; 7 if (den < 0) isNeg = !isNeg; 8 num = Math.abs(num); 9 den = Math.abs(den);10 HashMap<Long, Integer> dict = new HashMap<Long, Integer>();11 StringBuffer res = new StringBuffer();12 if (num == 0) return "0";13 int count = 1;14 while (num != 0 && !dict.containsKey(num)) {15 if (count == 2) res.append(‘.‘);16 dict.put(num, res.length());17 long digit = num / den;18 res.append(digit);19 num = (num % den) * 10;20 count++;21 }22 if (dict.containsKey(num)) {23 res.insert(dict.get(num).intValue(), ‘(‘);24 res.append(‘)‘);25 }26 if (isNeg) res.insert(0, ‘-‘);27 return res.toString();28 }29 }
注意第23行Integer要先转换成int。其实我的code有一个问题，那就是没有处理这种情况： 20 / 3 = 6.66666, 因为我不知道这样子是写成(6).呢还是6.(6)，不过test case里面没有这种，所以暂不考虑
Leetcode: Fraction to Recurring Decimal