166.分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 104 。

示例 1：

1
2
输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

1
2
输入：numerator = 2, denominator = 1
输出："2"

示例 3：

1
2
输入：numerator = 4, denominator = 333
输出："0.(012)"

难点在于如何返回循环小数，解决办法是用哈希表

Solution

模拟竖式运算
QQ图片20211003090709.jpg

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
class Solution {
    // 将分数转换为小数的方法，输入为分子 numerator 和分母 denominator。
    public String fractionToDecimal(int numerator, int denominator) {
        // 使用 StringBuilder 来构建结果字符串。
        StringBuilder sb = new StringBuilder();
        // 使用一个 HashMap 来存储之前出现过的余数和对应在结果字符串中的位置，用于检测循环小数。
        Map<Long, Integer> map = new HashMap<>();
        // 将 numerator 和 denominator 转换为 long 类型，避免溢出。
        long a = numerator, b = denominator;
        // 如果分子和分母的乘积为负，结果为负数，添加负号。
        if (a * b < 0) sb.append('-');
        // 取绝对值，保证后续计算时无需考虑正负。
        a = Math.abs(a);
        b = Math.abs(b);
        // 计算整数部分并添加到结果字符串。
        sb.append(a / b);
        // 如果能够整除，直接返回结果。
        if (a % b == 0) return sb.toString();
        // 添加小数点。
        sb.append('.');
        // 开始处理小数部分。
        while ((a = (a % b) * 10) > 0 && !map.containsKey(a)) {
            // 将当前余数和它在字符串中的位置存入 map。
            map.put(a, sb.length());
            // 计算当前小数位，并添加到结果字符串。
            sb.append(a / b);
        }
        // 如果余数为 0，说明小数部分不循环，直接返回结果。
        if (a == 0) return sb.toString();
        // 如果余数非零，说明发现了循环，从 map 中获取循环开始的位置，并在该位置插入左括号。
        return sb.insert(map.get(a).intValue(), '(').append(')').toString();
    }
}