Leetcode: Fraction to Recurring Decimal

待我称王封你为后i 2022-08-07 09:42 134阅读 0赞

题目：  
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.

For example,

Given numerator = 1, denominator = 2, return "0.5".
    Given numerator = 2, denominator = 1, return "2".
    Given numerator = 2, denominator = 3, return "0.(6)".

思路：  
用一个map记录每一个余数，当出现重复的余数时，那么将会进入循环，两个重复余数之间的部分就是循环体。

C++代码：

class Solution
    {
    public:
        string fractionToDecimal(int numerator, int denominator)
        {
            if (numerator == 0) return "0";
            if (denominator == 0) return "";
    
            string result = "";
            //如果其中有一个数为负，反正结果添加负号
            if ((numerator < 0) ^ (denominator < 0)) result += "-";
    
            //给分子和分母取绝对值
            long long lnumerator= numerator;
            long long ldenominator = denominator;
            lnumerator = abs(lnumerator);
            ldenominator = abs(ldenominator);
    
            long long quotient = lnumerator / ldenominator;
            result += to_string(quotient);
            //给余数乘以10是为了后续计算余数的结果为整数
            long long remainder = lnumerator % ldenominator * 10;
            //如果余数为0，直接返回结果
            if (remainder == 0) return result;
    
            result += ".";
            unordered_map<long long, int> dictionary;//用于存储余数及其余数的下标
            while (remainder != 0)
            {
                //如果dictionary中存在这个余数
                if (dictionary.find(remainder) != dictionary.end())
                {
                    int position = dictionary[remainder];
                    string front = result.substr(0, position);
                    string back = result.substr(position, result.length());
                    return front + "(" + back + ")";
                }
                dictionary.insert({remainder, result.length()});
                quotient = remainder / ldenominator;//用短除法计算商
                result += to_string(quotient);
                remainder = remainder % ldenominator * 10;//得到余数并乘以10
            }
            return result;
        }
    };

Java代码（因为这道题没有提供C\#代码的测试，所以这里使用Java，两个语言的语法差异不是太大）：

public class Solution {
        public String fractionToDecimal(int numerator, int denominator) {
            if (numerator == 0) return "0";
            if (denominator == 0) return "";
    
            StringBuilder result = new StringBuilder();
            //如果numerator和denominator中有一个为负数，则结果添加负号
            if ((numerator > 0) ^ (denominator > 0)) result.append("-");
    
            //给numerator和denominator取绝对值
            long lnumberator = numerator;
            long ldenominator = denominator;
            lnumberator = Math.abs(lnumberator);
            ldenominator = Math.abs(ldenominator);
    
            //计算整数部分
            long quotient = lnumberator /ldenominator;
            result.append(quotient);
            //余数乘以10是为了让后面余数部分的计算
            long remainder = lnumberator % ldenominator * 10;
            //如果余数为0直接返回result结果
            if (remainder == 0) return result.toString();
    
            result.append('.');
            Map<Long, Integer> dictionary = new HashMap<Long, Integer>();
            while (remainder != 0) {
                //如果dictionary中存在remainder的值，则说明小数部分出现循环
                if (dictionary.containsKey(remainder)) {
                    int position = dictionary.get(remainder);
                    String front = result.substring(0, position);
                    String back = result.substring(position, result.length());
                    return front + '(' + back + ')';
                }
    
                //将remainder添加到dictionary中(key为remainder，value为对应的在result中的位置)，继续计算余数
                dictionary.put(remainder, result.length());
                quotient = remainder / ldenominator;
                result.append(quotient);
                remainder = remainder % ldenominator * 10;
            }
    
            return result.toString();
        }
    }

Python代码：

class Solution:
        # @return a string
        def fractionToDecimal(self, numerator, denominator):
            if numerator == 0:
                return '0'
            if denominator == 0:
                return ''
    
            result = ''
            if (numerator > 0) ^ (denominator > 0):
                result = result + '-'
    
            pnumerator = abs(numerator)
            pdenominator = abs(denominator)
    
            quotient = pnumerator / pdenominator
            result = result + str(quotient)
            remainder = pnumerator % pdenominator * 10
    
            if remainder == 0:
                return result
    
            result = result + '.'
            map = {}
            while remainder != 0:
                if map.has_key(remainder):
                    position = map[remainder]
                    front = result[0: position]
                    back = result[position: len(result)]
                    return front + '(' + back + ')'
    
                map[remainder] = len(result)
                quotient = remainder / pdenominator
                result = result + str(quotient)
                remainder = remainder % pdenominator * 10
            return result