LC.P166[分数到小数]

方法一：模拟

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
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long a = numerator, b = denominator;
        if (a % b == 0) return String.valueOf(a / b);
        StringBuilder builder = new StringBuilder();
        // 其中一个数为负数，先加负号
        if (a * b < 0) {
            builder.append('-');
            a = Math.abs(a);
            b = Math.abs(b);
        }
        // 计算小数点前的部分，并将余数赋值给 a
        builder.append(a / b).append(".");
        a %= b;
        Map<Long, Integer> map = new HashMap<>();
        while (a != 0) {
            map.put(a, builder.length());
            a *= 10;
            builder.append(a / b);
            a %= b;
            // 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分）
            if (map.containsKey(a)) {
                int length = map.get(a);
                return String.format("%s(%s)" , builder.substring(0, length), builder.substring(length));
            }
        }
        return builder.toString();
    }
}
  • 时间复杂度：复杂度取决于最终答案的长度，题目规定了最大长度不会超过 $10^4$，整体复杂度为$O(M)$
  • 空间复杂度：复杂度取决于最终答案的长度，题目规定了最大长度不会超过 $10^4$，整体复杂度为$O(M)$