鸿 网 互 联 www.68idc.cn

[LeetCode] Fraction to Recurring Decimal

来源:互联网 作者:佚名 时间:2014-12-30 21:27
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.If the fractional part is repeating,

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,


这题实现起来还是比较麻烦的,主要还要考虑负数的输入情况,特别是-2147483648这样的整数型的边界值。最简单的方法就是先把所有的输入全部转换为长整型的正数。

另外,由于要记录小数里循环的部分,所以还需要用到一个Map去记录小数点的每位和对应的余数值。如果碰到的同样的余数值,那么说明遇到了开始循环的部分了。

public String fractionToDecimal(int numerator, int denominator) { long longNumerator = Math.abs((long) numerator); long longDenominator = Math.abs((long) denominator); StringBuilder sb = new StringBuilder(); if ((long) numerator * denominator < 0) sb.append("-"); sb.append(longNumerator / longDenominator); long remainder = longNumerator % longDenominator; if (remainder == 0) return sb.toString(); sb.append("."); StringBuilder fracSb = new StringBuilder(); Map<Long, Integer> map = new HashMap<Long, Integer>(); int index = 0; while (remainder != 0) { remainder *= 10; long nextRemainder = remainder % longDenominator; // If repeated part occurs. if (map.containsKey(remainder)) { fracSb.insert(map.get(remainder), "("); fracSb.append(")"); break; } map.put(remainder, index++); fracSb.append(remainder / longDenominator); remainder = nextRemainder; } sb.append(fracSb); return sb.toString(); }

网友评论
<