分数到小数
难度:
标签:
题目描述
给定两个整数,分别表示分数的分子 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后再进行除法运算中,如何确保不会因为整数溢出而导致错误?
▷🦆
哈希表中存储的键值对是余数和什么具体的索引?这个索引代表了什么?
▷🦆
为什么在确定了余数已存在于哈希表中后,可以立即断定出现了循环小数?存在没有循环但余数重复的情况吗?
▷🦆
在处理负数的情况时,为什么选择使用异或来判断最终结果的符号?使用异或有什么特别的优势吗?
▷