166. Fraction to Recurring Decimal.md

166. Fraction to Recurring Decimal

思路

求两个整数的除法, 并以字符串的形式精确返回其结果, 难点在于无限小数的处理.

根据小学知识我们知道, 有理数化成小数形式一定是有限小数或者无限循环小数, 不可能是无限不循环小数.

首先考虑结果的正负, 我们可以先判断正负再将除数和被除数取绝对值, 由于int型的取值范围是-2147483648～2147483647所以取绝对值前应该先转成long long型.

然后就是整数部分, 这个很简单直接分子整除分母即可, 此时得到余数r;

最后就是对余数r的处理, 如果不考虑无限循环小数那么也很简单: 每次循环先对r乘10, 再分别求其对denominator的商和余数, 得到的商就可以接在结果字符串的最后面, 而余数赋值给r, 循环直到r为0;

考虑无限循环小数该怎么办呢? 前面说到, 在循环里r是会不断更新的, 所以我们需记录每次循环r的值, 这样当r重复时, 就可以将两次循环之间得到的结果用括号括起来.

注意整数转字符串可以很方便地用to_string(), 另外insert对字符串进行插入.

C++

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long long num = abs((long long)numerator), den = abs((long long)denominator);
        long long r, tmp;
        string res = "";
        if((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0)) res += "-";
        
        res += to_string(num / den);
        r = num % den;
        if(!r) return res;
        
        res += ".";
        unordered_map<long long, int>mp; // r值到循环次数的映射
        int pos = res.size();
        while(r){
            if(mp.count(r)){ // 遇到了重复r值
                res.insert(mp[r], "(");
                res += ")";
                return res;
            }
            
            mp[r] = pos++;
            r *= 10;
            res += to_string(r / den);
            r = r % den;
        }
        return res;
    }
};