LeetCode: 166. 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)"

解题思路

用 map 记录下计算过程中的的余数。当重复出现某个余数时，计算结果就是循环小数，循环部分就是余数相同的两次结果之间的内容。

AC 代码

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        map<long long int, long long int> remainder2Idx; // 保存出现过的余数
        long long int numeratorLL = llabs(numerator), denominatorLL = llabs(denominator);
        string ans;

        ans += to_string(numeratorLL/denominatorLL);
        if(numeratorLL%denominatorLL != 0) 
        {
            ans += ".";
        }

        while(numeratorLL%denominatorLL != 0)
        {
            numeratorLL %= denominatorLL;
            numeratorLL *= 10;

            // 判断当前余数是否出现过，若出现过，则是循环小数
            if(remainder2Idx.find(numeratorLL) == remainder2Idx.end())
            {
                remainder2Idx[numeratorLL] = ans.size();
                ans += to_string(abs(numeratorLL/denominatorLL));
            }
            else 
            {
                ans = ans.substr(0, remainder2Idx[numeratorLL]) + "(" + 
                    ans.substr(remainder2Idx[numeratorLL], 
                    ans.size()-remainder2Idx[numeratorLL]) + ")";

                break;
            }
        }
        if((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0))
        {
            ans = "-" + ans;
        }
        return ans;
    }
};