算法数学算法

分数转小数, 数字运算的 Corner Case

字数统计: 690字   |   阅读时长: 3分
, ,

摘要: 力扣166：分数转小数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们通过力扣 166 来看一下在数学算法中常见的分数转小数的问题。算法比较简单，类似于竖式除法的过程，称为长除法，但是 Corner Case 比较多，实现时容易出错。对于无限循环小数的情况，需要寻找循环节，通过哈希表记录余数及其对应位置即可。

题目

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

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

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

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

提示：

1
2
-2^31 <= numerator, denominator <= 2^31 - 1
denominator != 0

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

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

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

题解

算法：长除法

长除法的过程类似于我们小学时候做的那种竖式除法，如下图所示是一个例子：

长除法

在长除法的过程中，每一步在得到余数后，如果该余数此前出现过，则出现循环节，结果为无限循环小数。

数字运算的 corner case

长除法本身的实现不难，但 Corner Case 非常多，需要注意细节。以下是数字运算的一些 Corner Case 总结：

数字运算 Corner Case

代码 C++ (模板)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0) return "0";
        if(numerator < 0 && denominator < 0)
        {
            if(denominator == INT_MIN || numerator == INT_MIN)
                return fractionToDecimal(-(long long)numerator, -(long long)denominator);
            return fractionToDecimal(-numerator, -denominator);
        }
        if(numerator < 0)
        {
            if(numerator == INT_MIN)
                return '-' + fractionToDecimal(-(long long)numerator, (long long)denominator);
            return '-' + fractionToDecimal(-numerator, denominator);
        }
        if(denominator < 0)
        {
            if(denominator == INT_MIN)
                return '-' + fractionToDecimal((long long)numerator, -(long long)denominator);
            return '-' + fractionToDecimal(numerator, -denominator);
        }
        string result;
        int p = numerator / denominator;
        int q = numerator % denominator;
        result += to_string(p);
        if(q == 0) return result;
        result += '.';
        unordered_map<int, int> mapping;
        while(q != 0)
        {
            int n = q * 10;
            if(mapping[n] != 0)
            {
                result.insert(mapping[n], 1, '(');
                result += ')';
                break;
            }
            mapping[n] = (int)result.size();
            p = n / denominator;
            q = n % denominator;
            result += to_string(p);
        }
        return result;
    }

    string fractionToDecimal(long long numerator, long long denominator) {
        string result;
        long long p = numerator / denominator;
        long long q = numerator % denominator;
        result += to_string(p);
        if(q == 0) return result;
        result += '.';
        unordered_map<long long, int> mapping;
        while(q != 0)
        {
            long long n = (long long)q * 10;
            if(mapping[n] != 0)
            {
                result.insert(mapping[n], 1, '(');
                result += ')';
                break;
            }
            mapping[n] = (int)result.size();
            p = n / denominator;
            q = n % denominator;
            result += to_string(p);
        }
        return result;
    }
};
Share