聖地亞歌

Leetcode P0166"Fraction to Recurring Decimal" 题解

2020/09/22 Leetcode

博文中会简要介绍Leetcode P0166题目分析及解题思路。

“Fraction to Recurring Decimal”是一道考验耐心和细心的题目，同时也考察数学功底。由于题目中要求如果存在循环小数，则只需要用小括号将一个循环节包裹起来即可，所以我们需要找到循环节或者是代表出现循环节的特征。这里会运用到HashTable来帮助我们找到循环节。

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.

If multiple answers are possible, return any of them.

核心思路是运用数学上的特征。如果一个数除以另一个数的余数在不断循环，那么其商也会出现循环节。所以我们只需要用一个HashTable记录每一个余数对应的小数结果，一旦出现相同的余数则可以知道出现了循环节，此时就可以退出循环。

为了避免过多的字符串拼接操作，我们可以用一个整型数组或者链表存储每个小数位上出现的余数。由于我们用HashTable记录了每个余数对应的小数结果，我们可以通过遍历这个数组得到每个小数位上应该出现的小数结果。

以下是Java的题解代码实现。

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0)
            return "0";
        
        StringBuilder decimal = new StringBuilder();
        // Set the sign
        if ((numerator > 0 && denominator < 0) 
            || (numerator < 0 && denominator > 0)) {
            decimal.append("-");
        }
        
        // Avoid overflow
        long longn = Math.abs((long) numerator);
        long longd = Math.abs((long) denominator);
        // Calculate the integer part first
        if (longn < longd) {
            decimal.append("0.");
        }
        else {
            decimal.append(longn/longd);
            longn = longn%longd;
            if (longn == 0)
                return decimal.toString();
            else 
                decimal.append(".");
        }
            
        long remainder = longn;
        Map<Long, Long> remainder2QuotientMap = new HashMap<>();
        List<Long> remainders = new ArrayList<>();
        while (longn != 0 && !remainder2QuotientMap.containsKey(remainder)) {
            
            longn *= 10;
            long quotient = longn/longd;
            
            // Record the mapping from remainder to quotient
            remainder2QuotientMap.put(remainder, quotient);
            remainders.add(remainder);
            
            remainder = longn%longd;
            longn = remainder;
        }
        
        
        for (long r: remainders) {
            if (r == remainder)
                decimal.append("(");
            
            decimal.append(remainder2QuotientMap.get(r));
        }
        
        if (longn == 0)
            return decimal.toString();
        else {
            decimal.append(")");
            return decimal.toString();
        }
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0)
            return "0";
        
        string decimal = "";
        // Set the sign
        if ((numerator > 0 && denominator < 0) 
            || (numerator < 0 && denominator > 0)) {
            decimal += "-";
        }
        
        // Avoid the overflow
        long longn = numerator;
        long longd = denominator;
        longn = abs(longn);
        longd = abs(longd);
        
        // Calculate the integer part first
        if (longn < longd) {
            decimal += "0.";
        }
        else {
            decimal += to_string(longn/longd);
            longn = longn%longd;
            if (longn == 0)
                return decimal;
            else 
                decimal += ".";
        }
        
        long remainder = longn;
        unordered_map<long, long> remainder2quotient;
        vector<int> remainders;
        while (longn != 0 && remainder2quotient.count(remainder) <= 0) {
            longn *= 10;
            long quotient = longn/longd;
            
            // Record
            remainder2quotient[remainder] = quotient;
            remainders.push_back(remainder);
            
            remainder = longn%longd;
            longn = remainder;
        }
        
        for (long r: remainders) {
            if (r == remainder)
                decimal += "(";
            
            decimal += to_string(remainder2quotient[r]);
        }
        
        if (longn == 0)
            return decimal;
        else {
            decimal += ")";
            return decimal;
        }
    }
};

Search

    Table of Contents