166. Fraction to Recurring Decimal 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long a = numerator, b = denominator;
        if (a % b == 0) {
            return String.valueOf(a / b);
        }

        StringBuilder sb = new StringBuilder();

        if (a * b < 0) {
            sb.append("-");
            a = Math.abs(a);
            b = Math.abs(b);
        }

        // 小数点前的部分单独计算以便于添加小数点，计算后 a 需要更新为余数
        sb.append(a / b).append(".");
        a = a % b; // 此时 a 小于 b, 即准备计算小数点后面的部分

        Map<Long, Integer> numToNextIndexMap = new HashMap<>();
        while (a != 0) {
            // 记录当前余数对应的下一个索引（不含）
            numToNextIndexMap.put(a, sb.length());
            a *= 10; // 余数补 0, 此时还未生成新的余数
            sb.append(a / b);
            a %= b; // 此时计算出了新的余数

            if (numToNextIndexMap.containsKey(a)) {
                int index = numToNextIndexMap.get(a);
                String rotate = sb.substring(index);
                sb.delete(index, sb.length()); // [index, sb.length())
                sb.append("(").append(rotate).append(")");
                return sb.toString();
            }
        }

        return sb.toString();
    }
}

References

166. Fraction to Recurring Decimal