solution.md

# 分数到小数

<p>给定两个整数，分别表示分数的分子 <code>numerator</code> 和分母 <code>denominator</code>，以 <strong>字符串形式返回小数</strong> 。</p>

<p>如果小数部分为循环小数，则将循环的部分括在括号内。</p>

<p class="MachineTrans-lang-zh-CN">如果存在多个答案，只需返回 <strong>任意一个</strong> 。</p>

<p class="MachineTrans-lang-zh-CN">对于所有给定的输入，<strong>保证</strong> 答案字符串的长度小于 <code>10<sup>4</sup></code> 。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>numerator = 1, denominator = 2
<strong>输出：</strong>"0.5"
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>numerator = 2, denominator = 1
<strong>输出：</strong>"2"
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>numerator = 2, denominator = 3
<strong>输出：</strong>"0.(6)"
</pre>

<p><strong>示例 4：</strong></p>

<pre>
<strong>输入：</strong>numerator = 4, denominator = 333
<strong>输出：</strong>"0.(012)"
</pre>

<p><strong>示例 5：</strong></p>

<pre>
<strong>输入：</strong>numerator = 1, denominator = 5
<strong>输出：</strong>"0.2"
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>-2<sup>31</sup> <= numerator, denominator <= 2<sup>31</sup> - 1</code></li>
	<li><code>denominator != 0</code></li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    string res;
    int numerator = 1, denominator = 2;
    res = sol.fractionToDecimal(numerator, denominator);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    const static int CACHE_SIZE = 1000;
    string fractionToDecimal(int numerator, int denominator)
    {
        if (numerator == 0)
            return "0";

        bool isNegative = numerator < 0 ^ denominator < 0;
        double doubleNumerator = fabs(numerator);
        double doubleDenominator = fabs(denominator);
        double integral = floor(doubleNumerator / doubleDenominator);
        doubleNumerator -= doubleDenominator * integral;
        int len = 0;
        string cache;
        vector<double> dividendCache;
        bool isRecurring = false;
        int recurringStart = 0;
        int i = 0;
        while (doubleNumerator)
        {
            doubleNumerator *= 10;
            len = dividendCache.size();
            for (i = 0; i < len; ++i)
                if (dividendCache[i] == doubleNumerator)
                {
                    isRecurring = true;
                    recurringStart = i;
                    break;
                }
            if (isRecurring)
                break;
            i = (int)(floor(doubleNumerator / doubleDenominator));
            cache += i;
            dividendCache.push_back(doubleNumerator);
            doubleNumerator -= doubleDenominator * i;
        }

        string ret = isNegative ? "-" : "";
        string tmp;
        char c;
        if (integral == 0)
            ret += "0";
        else
        {
            while (integral)
            {
                c = (int)(integral - 10 * floor(integral / 10)) + '0';
                tmp = c + tmp;
                integral = floor(integral / 10);
            }
            ret += tmp;
        }
        if (dividendCache.size() > 0)
            ret += '.';
        i = 0;
        if (isRecurring)
        {
            ret += cache.substr(0, recurringStart);
            ret += '(';
            ret += cache.substr(recurringStart);
            ret += ')';
        }
        else
            ret += cache;

        return ret;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        typedef long long LL;
        LL x = numerator, y = denominator;
        if (x % y == 0)
            return to_string(x / y);
        string res;
        if ((x < 0) ^ (y < 0))
            res += '-';
        x = abs(x), y = abs(y);
        res += to_string(x / y) + '.';
        x %= y;
        unordered_map<LL, int> hash;
        while (x)
        {
            hash[x] = res.size();
            x *= 10;
            res += to_string(x / y);
            x %= y;
            if (hash.count(x))
            {
                res = res.substr(0, hash[x]) + '(' + res.substr(hash[x]) + ')';
                break;
            }
        }
        return res;
    }
};
```

### B
```cpp
class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        string ans;
        unordered_map<long, int> use;
        if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0)
            ans = '-';
        long numerat = fabs(numerator);
        long denominat = fabs(denominator);
        ans += to_string(numerat / denominat);
        numerat = numerat % denominat;
        int point, x;
        if (numerat)
        {
            ans += ".";
            point = ans.length() - 1;
        }
        else
            return ans;
        while (numerat && use.count(numerat) == 0)
        {
            use[numerat] = ++point;
            numerat *= 10;
            x = numerat / denominat;
            numerat = numerat % denominat;
            ans.push_back(x + '0');
        }
        if (numerat)
        {
            ans.insert(ans.begin() + use[numerat], '(');
            ans.push_back(')');
        }
        return ans;
    }
};
```

### C
```cpp
class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        int m1 = numerator > 0 ? 1 : -1;
        int m2 = denominator > 0 ? 1 : -1;
        long long num = abs((long long)numerator);
        long long den = abs((long long)denominator);
        long long t = num / den;
        long long res = num % den;
        string ans = to_string(t);
        if (m1 * m2 == -1 && (t > 0 || res > 0))
            ans = '-' + ans;
        if (res == 0)
            return ans;
        ans += '.';
        unordered_map<long long, int> m;
        string s = "";
        int pos = 0;
        while (res != 0)
        {
            if (m.find(res) != m.end())
            {
                s.insert(m[res], "(");
                s += ')';
                return ans + s;
            }
            m[res] = pos;
            s += to_string((res * 10) / den);
            res = (res * 10) % den;
            pos++;
        }
        return ans + s;
    }
};
```