首页 > 代码库 > Leetcode#166 Fraction to Recurring Decimal
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位整型，也可以，大整数除法等待着你。
代码：
1 string fractionToDecimal(int numerator, int denominator) { 2 if (numerator == 0) 3 return "0"; 4 5 long long num = numerator; 6 long long den = denominator; 7 map<long long, int> record; 8 string res = (numerator ^ denominator) < 0 ? "-" : ""; 9 string rem;10 int i = 0;11 12 num = abs(num);13 den = abs(den);14 res += to_string(num / den);15 num = (num % den) * 10;16 17 while (num) {18 if (record.find(num) == record.end())19 record[num] = i;20 else {21 rem = rem.substr(0, record[num]) + "(" + rem.substr(record[num]) + ")";22 break;23 }24 rem += to_string(num / den);25 num = (num % den) * 10;26 i++;27 }28 if (!rem.empty())29 res += "." + rem;30 31 return res;32 }
Leetcode#166 Fraction to Recurring Decimal