LeetCode/solutions/166. Fraction to Recurring Decimal.md

# [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/)
# 思路
求两个整数的除法, 并以字符串的形式精确返回其结果, 难点在于无限小数的处理. 

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

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

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

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

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

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


# C++
``` 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;
    }
};
```