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

  |  

摘要: 力扣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