Fraction to Recurring Decimal(Medium)

分数转为循环小数

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

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

public String fractionToDecimal(int n, int d) {
    StringBuilder sb = new StringBuilder();
    long numerator = n, denominator = d;

    if(numerator == 0 || denominator == 0){
        return "0";
    }

    //把除数和被除数都转化为正数
    boolean isNegative = false;
    if (numerator < 0) {
        numerator = -numerator;
        isNegative = !isNegative;
    }
    if (denominator < 0) {
        denominator = -denominator;
        isNegative = !isNegative;
    }

    long quotient = numerator / denominator;
    //long remainder = numerator - denominator * quotient;
    long remainder = numerator % denominator;

    if (isNegative && numerator !=0)
        sb.append('-');
    sb.append(quotient);

    if (remainder != 0) {
        sb.append('.');
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();

        while (remainder != 0 ) {
            if (!map.containsKey(remainder)) {
                map.put(remainder, sb.length());
                numerator = remainder * 10;
                quotient = numerator / denominator;
                sb.append(quotient);
                remainder = numerator % denominator;
            } else {
                //如果该余数之前出现过，说明有循环，上次出现的位置到当前位置就是循环的部分
                sb.insert((int) map.get(remainder), '(');
                sb.append(')');
                break;
            }
        }//while
    }

    return sb.toString();
}