leetcode
leetcode 151 ~ 200
分数到小数

分数到小数

难度:

标签:

题目描述

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

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

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

对于所有给定的输入,保证 答案字符串的长度小于 104

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示:

  • -231 <= numerator, denominator <= 231 - 1
  • denominator != 0

代码结果

运行时间: 24 ms, 内存: 0.0 MB


// This solution also uses basic division and a HashMap for detecting cycles but utilizes Java Streams for formatting.
// The stream API isn't directly used here because of the nature of the problem, but we demonstrate an example with Streams for any future use case.
 
import java.util.*;
import java.util.stream.Collectors;
 
public class FractionToDecimalStream {
    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 denom = Math.abs((long) denominator);
        result.append(num / denom);
        num %= denom;
        if (num == 0) return result.toString();
        result.append(".");
        Map<Long, Integer> map = new HashMap<>();
        List<Long> fractionalParts = new ArrayList<>();
        while (num != 0) {
            if (map.containsKey(num)) {
                result.insert(map.get(num), "(");
                result.append(")");
                break;
            }
            map.put(num, result.length());
            num *= 10;
            fractionalParts.add(num / denom);
            num %= denom;
        }
        result.append(fractionalParts.stream().map(String::valueOf).collect(Collectors.joining()));
        return result.toString();
    }
}
 

解释

方法:

这个题解使用哈希表来判断小数部分是否存在循环。首先计算整数部分,然后对余数进行逐位计算,同时用哈希表记录每个余数出现的位置。如果某个余数再次出现,说明从上次出现的位置到当前位置构成循环节。最后根据是否存在循环节,构造出最终的结果字符串。

时间复杂度:

O(denominator)

空间复杂度:

O(denominator)

代码细节讲解

🦆
在将余数乘以10后再进行除法运算中,如何确保不会因为整数溢出而导致错误?
在现代编程语言中,如Python,整数类型通常具有自动扩展的特性,这意味着当整数运算超出固定大小时,整数可以自动扩展以防止溢出。在处理大整数问题时,这一点尤其重要。Python的整数类型是不固定长度的,可以处理任意大的整数,只要内存足够。因此,在将余数乘以10后进行除法运算,不会因为整数溢出而导致错误。
🦆
哈希表中存储的键值对是余数和什么具体的索引?这个索引代表了什么?
在这个算法中,哈希表中存储的键是余数,而对应的值是该余数在小数部分的具体索引位置。这个索引代表了余数在结果字符串中小数点后的位置。因此,如果同一个余数在哈希表中再次出现,我们可以根据原先记录的索引直接找到小数部分开始循环的位置,从而构造出循环小数的表示。
🦆
为什么在确定了余数已存在于哈希表中后,可以立即断定出现了循环小数?存在没有循环但余数重复的情况吗?
在长除法中,如果某个余数再次出现,意味着接下来的除法步骤将重复之前的步骤,导致生成相同的数字序列,形成循环。不存在没有循环但余数重复的情况,因为余数的重复直接导致了除法过程的重复。因此,一旦余数在哈希表中被再次发现,就可以确定小数部分开始循环。
🦆
在处理负数的情况时,为什么选择使用异或来判断最终结果的符号?使用异或有什么特别的优势吗?
异或运算符(^)在这里被用来确定两个数的符号是否相异。如果两个数一个为正一个为负,异或的结果将是负数;如果两个数符号相同(都是正数或都是负数),异或的结果将是正数。这种方法提供了一种简洁的方式来判断结果的符号,省去了复杂的if-else结构,使代码更简洁易读。此外,异或运算通常比比较和条件判断更快,有助于提升算法的执行效率。

相关问题