166. 分数到小数

Medium

题目描述

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

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

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

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

注意：如果分数可以表示为有限长度的字符串，则必须返回有限长度的表示。

示例 1：

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

示例 2：

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

示例 3：

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

约束条件：

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

提示：

不要被数学吓到，只需应用基础数学知识。还记得如何进行长除法吗？
对 4/9 进行长除法试试，循环部分很明显。现在试试 4/333，你看到模式了吗？
注意一旦余数开始循环，除法结果也会循环。
小心边界情况！列出尽可能多的测试用例来彻底测试你的代码。

解题思路

这道题要求将分数转换为小数字符串，关键是处理循环小数的情况。

核心思路：

处理符号：先判断结果的正负性，统一转为正数计算
整数部分：直接除法得到整数部分
小数部分：使用长除法模拟，关键是检测循环

循环检测原理：

在长除法中，如果某个余数之前出现过，说明开始循环了
使用哈希表记录每个余数第一次出现的位置
当余数重复时，从该位置开始就是循环部分

边界情况处理：

整除情况（余数为0）：直接返回，无循环部分
负数：只有一个操作数为负时结果为负
溢出：使用long避免INT_MIN取绝对值溢出
整数结果：分子能被分母整除时无小数部分

算法步骤：

处理符号和特殊情况
计算整数部分
模拟长除法计算小数部分
使用哈希表检测循环，在循环位置插入括号

时间复杂度主要取决于循环检测，最坏情况下需要遍历所有可能的余数。

代码实现

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        
        string result;
        
        // 处理符号
        if ((numerator > 0) ^ (denominator > 0)) {
            result += "-";
        }
        
        // 转为正数，防止溢出
        long num = abs((long)numerator);
        long den = abs((long)denominator);
        
        // 整数部分
        result += to_string(num / den);
        num %= den;
        
        if (num == 0) return result;
        
        // 小数部分
        result += ".";
        unordered_map<long, int> remainderMap;
        
        while (num != 0) {
            if (remainderMap.count(num)) {
                int index = remainderMap[num];
                result.insert(index, "(");
                result += ")";
                break;
            }
            
            remainderMap[num] = result.length();
            num *= 10;
            result += to_string(num / den);
            num %= den;
        }
        
        return result;
    }
};

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))
        num %= den
        
        if num == 0:
            return "".join(result)
        
        # 小数部分
        result.append(".")
        remainder_map = {}
        
        while num != 0:
            if num in remainder_map:
                index = remainder_map[num]
                result.insert(index, "(")
                result.append(")")
                break
            
            remainder_map[num] = len(result)
            num *= 10
            result.append(str(num // den))
            num %= den
        
        return "".join(result)

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 num = Math.Abs((long)numerator);
        long den = Math.Abs((long)denominator);
        
        // 整数部分
        result.Append(num / den);
        num %= den;
        
        if (num == 0) return result.ToString();
        
        // 小数部分
        result.Append(".");
        Dictionary<long, int> remainderMap = new Dictionary<long, int>();
        
        while (num != 0) {
            if (remainderMap.ContainsKey(num)) {
                int index = remainderMap[num];
                result.Insert(index, "(");
                result.Append(")");
                break;
            }
            
            remainderMap[num] = result.Length;
            num *= 10;
            result.Append(num / den);
            num %= den;
        }
        
        return result.ToString();
    }
}

var fractionToDecimal = function(numerator, denominator) {
    if (numerator === 0) return "0";
    
    let result = "";
    
    // Handle sign
    if ((numerator > 0) !== (denominator > 0)) {
        result += "-";
    }
    
    // Convert to positive
    let num = Math.abs(numerator);
    let den = Math.abs(denominator);
    
    // Integer part
    result += Math.floor(num / den);
    num %= den;
    
    if (num === 0) return result;
    
    // Fractional part
    result += ".";
    let remainderMap = new Map();
    
    while (num !== 0) {
        if (remainderMap.has(num)) {
            let index = remainderMap.get(num);
            result = result.substring(0, index) + "(" + result.substring(index) + ")";
            break;
        }
        
        remainderMap.set(num, result.length);
        num *= 10;
        result += Math.floor(num / den);
        num %= den;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析	说明
时间复杂度	O(denominator)	最坏情况下需要遍历所有可能的余数，余数范围是[0, denominator-1]
空间复杂度	O(denominator)	哈希表存储余数位置，最多存储denominator个不同余数

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析