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)".

分析

这道题不需要特别的算法。只是在算小数的时候，用个hashmap存余值，从而方便发现循环点。

这种除法的问题，写的时候想一遍过还是得注意很多情况。比如结果正负号，越界，输入为零等情况。我们可以在开始就判断结果的正负，然后直接算绝对值的除法。为避免越界，我们全部变量用Long代替，输入为零的情况也可以开始就先拿出考虑。

复杂度

time: O(n), space: O(n)

代码

public class Solution {    public String fractionToDecimal(int numerator, int denominator) {        // 先考虑输入为零的情况        if (numerator == 0)return "0";        if (denominator == 0)return "";    StringBuilder sb = new StringBuilder();        if ((numerator ^ denominator) >>> 31 == 1) { // 确定结果正负sb.append('-');        }    // 避免越界，变量类型全为Long        long a = Math.abs((long)numerator);        long b = Math.abs((long)denominator);        long intVal = a / b;        long remainder = a % b;        sb.append(intVal); // 添加整数部分    // 开始考虑小数部分        if (remainder > 0) {sb.append('.');int i = sb.length();Map<Long, Integer>  map = new HashMap<>();while (remainder > 0) {    if (map.containsKey(remainder)) { // 发现小数循环        int start = map.get(remainder);        sb.insert(start, "(");        sb.append(")");        break;    }    map.put(remainder, i++);    a = remainder * 10;    long val = a / b;    sb.append(val);    remainder = a % b;}        }        return sb.toString();    }}