Leetcode#166 Fraction to Recurring Decimal

原题地址

计算循环小数

先把负数转化成正数,然后计算,最后添加符号

当被除数重复出现的时候,说明开始循环了,所以用一个map保存所有遇到的被除数

需要考虑溢出问题,这也是本题最恶心的地方,看看通过率吧,比Hard难度的题还低。

最残暴的做法是直接转成64位长整型,比如下面的代码。好处是代码简洁了许多,不过这是投机取巧,因为如果题目把参数换成两个64为长整型,这个方法就不行了。

如果不用64长整型,就用32位普通整型怎么办?

由于我们要把除数和被除数转化成正数,所以当其中任意一个数等于INT_MIN时,就得考虑溢出问题。

对于被除数,情况还好。假如被除数是INT_MIN,大不了我先减一个除数,让商加1就可以避免这个问题。这个技术可以用在Divide Two Integers这道题中(参见这篇文章

对于除数,情况就复杂了。假如除数是INT_MIN,除数不能拆分,所以没法转换成正数去做。这怎么办?

有人可能会想,用无符号类型呗。的确,32位无符号数的最大表示范围是2^32 - 1 > 2^31,可以将除数转化成正数了。但是仍然会有溢出发生,因为在计算小数部分时,被除数如果小于除数就要不断乘以10,直到够除为止。这个不断乘以10的过程会溢出,因为无符号整型最多只能保存2倍大的除数(INT_MIN),而被除数很容易超过这个值。为了解决这个问题,需要将除法运算退化成减法去做,将乘法运算退化成加法。把乘以10改成加9次,把除以除数改成减若干次除数。显然,这样做太麻烦了。

也有人可能会想,干嘛要转成正数呢?直接在int上做呗,对不起,还会遇到上面所说的溢出的情况。

看来只使用32位数据类型没有办法了,如果非要坚持不用64位整型,也可以,大整数除法等待着你。

代码:

 string fractionToDecimal(int numerator, int denominator) {
if (numerator == )
return ""; long long num = numerator;
long long den = denominator;
map<long long, int> record;
string res = (numerator ^ denominator) < 0 ? "-" : "";
string rem;
int i = ; num = abs(num);
den = abs(den);
res += to_string(num / den);
num = (num % den) * ; while (num) {
if (record.find(num) == record.end())
record[num] = i;
else {
rem = rem.substr(, record[num]) + "(" + rem.substr(record[num]) + ")";
break;
}
rem += to_string(num / den);
num = (num % den) * ;
i++;
}
if (!rem.empty())
res += "." + rem; return res;
}
上一篇:《javascript高级程序设计》 第23章 离线应用与客户端存储


下一篇:SpringCloud微服务项目实战 - API网关Gateway详解实现