166_分数到小数

难度：中等

题目

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

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

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

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

示例

示例一：

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

示例二：

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

示例三：

输入：numerator = 2, denominator = 3
输出：”0.(6)”

示例四：

输入：numerator = 4, denominator = 333
输出：”0.(012)”

示例五：

输入：numerator = 1, denominator = 5
输出：”0.2”

提示

  • $-2^{31} <= numerator, denominator <= 2^{31} - 1$
  • denominator != 0

解题

  • 如果本身两数能够整除，直接返回即可
  • 如果两个数有一个为“负数”，则最终答案为“负数”
  • 两者范围为 int，但计算结果可以会超过 int 范围,所以先用 long 对两个参数进行格式转换

从人工模拟除法运算的过程，就可以知道「为什么不会出现“无限不循环小数”」，因为始终是对余数进行补零操作，再往下进行运算，而余数个数具有明确的上限（有限集）。所以根据抽屉原理，一直接着往下计算，最终结果要么是「出现相同余数」，要么是「余数为 0，运算结束」。

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
public String fractionToDecimal(int numerator, int denominator){
    // 转 long 计算，防止溢出
    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);
    // 添加小数点前的部分
    sb.append(String.valueOf(a/b)+".");
    a %=b;
    Map<Long, Integer> map = new HashMap<>();
    while (a!=0){
        // 记录当前余数所在位置
        map.put(a,sb.length());
        a*=10;
        sb.append(a/b);
        a%=b;
        // 如果余数出现过，则将出现位置到当前位置提取出来
        if (map.containsKey(a)){
            int u = map.get(a);
            return String.format("%s(%s)",sb.substring(0,u),sb.substring(u));
        }
    }
    return sb.toString();
}