166. Fraction to Recurring Decimal

Leetcode Hash Table Math

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

分析

这道题目涉及基本的数学，难点在于如何判断数字重复以及细节的处理。首先要注意正负号、0这样的细节，然后考虑到整数可能越界，所以统一转换为长整型long。判断数字重复关键在于判断余数的重复，所以我们可以将余数和余数的位置放在哈希表中，当余数重复时，确定重复区间，加上括号

public String fractionToDecimal(int numerator, int denominator) {
    // 处理0
    if (numerator == 0) return "0";

    StringBuilder sb = new StringBuilder();
    HashMap<Long, Integer> map = new HashMap<>();        


    // 处理负数
    boolean isPositive = numerator < 0 == denominator < 0;
    if (!isPositive)  sb.append("-");
    long numeratorLong = Math.abs((long) numerator);
    long denominatorLong = Math.abs((long) denominator);

    // 整数部分
    sb.append(numeratorLong / denominatorLong);
    long reminder = numeratorLong % denominatorLong;
    if (reminder == 0) return sb.toString();


    // 小数部分
    sb.append(".");
    int index = sb.length();
    while (reminder != 0) {
        if (!map.containsKey(reminder)) { // 放入分子和分子所在的位置
            map.put(reminder, index++);
        } else {
            // 发现重复，在合适的位置加入括号, 并结束
            sb.insert(map.get(reminder), "(");
            sb.append(')');
            break;
        }

        // 添加商
        reminder *= 10;
        sb.append(reminder / denominatorLong);

        // 更新余数
        reminder %= denominatorLong;
    } // end while


    return sb.toString();    
}