一、题目描述
给定两个整数，分别表示分数的分子 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 - 1denominator != 0
二、解题思路
处理符号：首先，确定结果的符号。如果分子和分母有一个是负数，则结果为负。将分子和分母都转换为正数进行后续计算。
整数部分：计算整数部分，即
numerator / denominator，并将其添加到结果字符串中。小数部分：对于小数部分，可以通过模拟除法来获得。将分子乘以10，然后除以分母，得到的商是当前位的数字，余数是下一次计算的分子。重复此过程直到余数为0或出现重复的余数（这意味着小数部分开始循环）。
处理循环：使用一个哈希表（例如
HashMap）来记录每个余数第一次出现的位置。当再次遇到相同的余数时，说明小数部分开始循环。在循环部分前后加上括号。返回结果：将整数部分和小数部分结合起来，如果结果为负，则加上负号。
三、具体代码
import java.util.HashMap;
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.valueOf(numerator));
long den = Math.abs(Long.valueOf(denominator));
// 计算整数部分
result.append(num / den);
// 计算小数部分
long remainder = num % den;
if (remainder == 0) {
return result.toString();
}
result.append(".");
HashMap<Long, Integer> map = new HashMap<>();
while (remainder != 0) {
// 如果余数重复出现，则开始循环
if (map.containsKey(remainder)) {
result.insert(map.get(remainder), "(");
result.append(")");
break;
}
// 记录余数第一次出现的位置
map.put(remainder, result.length());
remainder *= 10;
result.append(remainder / den);
remainder %= den;
}
return result.toString();
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 符号处理和整数部分计算：O(1)。这些操作是常数时间的，因为它们只涉及到基本的数学运算和字符串拼接。
- 小数部分计算：O(n)，其中n是结果中小数部分的位数。在最坏的情况下，小数部分可能没有循环，并且达到10^4位，这将需要n次迭代来计算。
- 循环检测：O(1)。哈希表的插入和查找操作通常是O(1)的，因此即使在小数部分有循环的情况下，循环检测的时间复杂度也是常数时间。
综上所述，最坏情况下的时间复杂度是O(n)，其中n是小数部分的位数。
2. 空间复杂度
- 结果字符串：O(n)。结果字符串的长度取决于小数部分的位数，最坏情况下需要O(n)的空间。
- 哈希表：O(m)，其中m是不同余数的数量。在最坏的情况下，余数可能每次都不一样，这将导致哈希表的大小增长，但由于余数的范围是有限的（从0到分母-1），实际上哈希表的大小不会超过分母的大小。因此，哈希表的空间复杂度可以认为是O(1)，因为分母的大小是一个固定的常数。
综上所述，最坏情况下的空间复杂度是O(n)，其中n是小数部分的位数。
需要注意的是，这里的n和m都是指结果中的位数或不同余数的数量，而不是输入的整数大小。输入的整数大小是固定的，即32位整数的范围，所以它不会影响时间复杂度和空间复杂度的阶数。
五、总结知识点
1. 基本数据类型与包装类的转换：
int类型通过Long.valueOf()方法转换为long类型，以便处理可能超过int范围的值。
2. 数学运算：
- 使用取绝对值函数
Math.abs()来确保分子和分母为正数。 - 使用除法
num / den和取模运算num % den来计算整数部分和余数。
3. 字符串处理：
- 使用
StringBuilder类来构建结果字符串，因为它比字符串连接更加高效。 - 使用
append()方法添加字符和字符串。 - 使用
insert()方法在指定位置插入字符串。
4. 数据结构：
- 使用
HashMap来存储余数和它们在结果字符串中第一次出现的位置，以便检测循环。
5. 位运算：
- 使用异或运算符
^来确定结果的符号。如果分子和分母的符号不同，结果为负。
6. 循环与条件判断：
- 使用
while循环来计算小数部分，直到余数为0或发现循环。 - 使用
if语句来处理符号、判断余数是否为0以及检测循环。
7. 异常处理：
- 虽然代码中没有显式的异常处理，但是使用
Long.valueOf()避免了整数除以0时可能出现的ArithmeticException。
8. 类型转换：
int类型在计算过程中被提升为long类型，以避免可能的溢出问题。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
