LeetCode 第166题：分数到小数

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个。

对于所有给定的输入，保证答案字符串的长度小于 10^4。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 2, denominator = 3
输出："0.(6)"

示例 4：

输入：numerator = 4, denominator = 333
输出："0.(012)"

示例 5：

输入：numerator = 1, denominator = 5
输出："0.2"

提示

-2^31 <= numerator, denominator <= 2^31 - 1
denominator != 0

解题思路

方法：模拟长除法

模拟长除法的计算过程，找出循环小数的部分。关键是要记录每次除法的余数及其对应的位置，当出现重复的余数时，就找到了循环节的起始位置。关键点：

处理正负号
处理整数部分
使用哈希表记录每个余数及其在小数点后的位置
当余数为0时，表示除尽，不是循环小数
当出现重复的余数时，找到循环节的起始位置，用括号括起循环部分

时间复杂度：O(l)，其中l是结果字符串的长度。空间复杂度：O(l)，需要存储中间余数及其位置。

代码实现

C# 实现

public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        
        StringBuilder result = new StringBuilder();
        
        // 处理正负号
        if ((numerator < 0) ^ (denominator < 0)) {
            result.Append("-");
        }
        
        // 转换为long防止溢出
        long num = Math.Abs((long)numerator);
        long den = Math.Abs((long)denominator);
        
        // 整数部分
        result.Append(num / den);
        
        // 小数部分
        long remainder = num % den;
        if (remainder == 0) {
            return result.ToString();
        }
        
        result.Append(".");
        
        // 记录每个余数出现的位置
        Dictionary<long, int> map = new Dictionary<long, int>();
        
        while (remainder != 0) {
            if (map.ContainsKey(remainder)) {
                // 找到循环节，插入左括号
                result.Insert(map[remainder], "(");
                result.Append(")");
                break;
            }
            
            // 记录当前余数的位置
            map[remainder] = result.Length;
            
            remainder *= 10;
            result.Append(remainder / den);
            remainder %= den;
        }
        
        return result.ToString();
    }
}

Python 实现

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        
        result = []
        
        # 处理正负号
        if (numerator < 0) ^ (denominator < 0):
            result.append("-")
        
        # 转换为绝对值
        num = abs(numerator)
        den = abs(denominator)
        
        # 整数部分
        result.append(str(num // den))
        
        # 小数部分
        remainder = num % den
        if remainder == 0:
            return "".join(result)
        
        result.append(".")
        
        # 记录每个余数出现的位置
        remainder_map = {}
        
        while remainder != 0:
            if remainder in remainder_map:
                # 找到循环节，插入左括号
                result.insert(remainder_map[remainder], "(")
                result.append(")")
                break
            
            # 记录当前余数的位置
            remainder_map[remainder] = len(result)
            
            remainder *= 10
            result.append(str(remainder // den))
            remainder %= den
        
        return "".join(result)

C++ 实现

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        
        string result;
        
        // 处理正负号
        if ((numerator < 0) ^ (denominator < 0)) {
            result += "-";
        }
        
        // 转换为long防止溢出
        long long num = abs((long long)numerator);
        long long den = abs((long long)denominator);
        
        // 整数部分
        result += to_string(num / den);
        
        // 小数部分
        long long remainder = num % den;
        if (remainder == 0) {
            return result;
        }
        
        result += ".";
        
        // 记录每个余数出现的位置
        unordered_map<long long, int> remainderMap;
        
        while (remainder != 0) {
            if (remainderMap.find(remainder) != remainderMap.end()) {
                // 找到循环节，插入左括号
                result.insert(remainderMap[remainder], "(");
                result += ")";
                break;
            }
            
            // 记录当前余数的位置
            remainderMap[remainder] = result.size();
            
            remainder *= 10;
            result += to_string(remainder / den);
            remainder %= den;
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	84 ms	36.4 MB	实现简洁，性能适中
Python	36 ms	15.1 MB	代码最简洁
C++	4 ms	6.4 MB	性能最优