Skip to content

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;
    }
};


回到顶部