0166._Fraction_to_Recurring_Decimal.md

166. Fraction to Recurring Decimal

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/fraction-to-recurring-decimal/

内容描述

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"
Example 2:

Input: numerator = 2, denominator = 1
Output: "2"
Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

思路 - 时间复杂度: O(nlgn)- 空间复杂度: O(n)******

对于这道题考虑的点比较多，首先我们用map储存每次的余数，以及得到的答案在字符串中的位置，只要余数在map中出现过了，则表示接下来开始循环。要注意得到的答案有可能是负数，因此要注意添加负号。应为int的最小值乘上-1大于int的最大值，所以用long long储存除数和被除数。

class Solution {
public:
    void join_str(string& str,long long num,int t)
    {
        if(!num)
        {
            if(t < 0)
                str.push_back('-');
            str.push_back('0');
            return;
        }
        while(num)
        {
            str.push_back(num % 10 + '0');
            num /= 10;
        }
        if(t < 0)
            str.push_back('-');
        reverse(str.begin(),str.end());
    }
    string fractionToDecimal(int numerator, int denominator) {
        map<long long,int> m;
        if(!numerator)
            return "0";
        int t = 1;
        long long n1 = numerator,d1 = denominator;
        if(numerator < 0)
        {
            t *= -1;
            n1 *= -1;
        }
        if(denominator < 0)
        {
            t *= -1;
            d1 *= -1;
        }
        long long num = n1 / d1;
        string ans;
        join_str(ans,num,t);
        long long quotient = n1 % d1;
        if(quotient)
            ans.push_back('.');
        string temp;
        int count1 = 0;
        while(quotient)
        {
            long long new_num = quotient * 10;
            if(m[new_num])
            {
                temp.push_back(')');
                count1 = m[new_num];
                break;
            }
            m[new_num] = temp.length() + 1;
            temp.push_back(new_num / d1 + '0');
            quotient = new_num % d1;
        }
        if(count1)
        {
            ans.append(temp.begin(),temp.begin() + count1 - 1);
            ans.push_back('(');
            ans.append(temp.begin() + count1 - 1,temp.end());
        }
        else
            ans.append(temp.begin(),temp.end());
        return ans;
    }
};