企业官网建设流程全解析

LeetCode 166. 分数到小数

思路

模拟竖式除法：

1. 确定符号：分子分母异号则为负。
2. 整数部分：numerator / denominator。
3. 小数部分：每次将余数乘 10，再除以分母得到当前位，同时更新余数。
4. 检测循环：用 HashMap 记录每个余数第一次出现时对应的小数位下标。若某余数再次出现，说明从该位置开始循环，插入括号即可。

注意：-2^31 / -1 会溢出，所以先转成 long 处理。

Java 实现

classSolution{publicStringfractionToDecimal(intnumerator,intdenominator){if(numerator==0)return"0";StringBuildersb=newStringBuilder();// 1. 处理符号if((numerator<0)^(denominator<0)){sb.append('-');}// 2. 转为 long 防止溢出，并取绝对值longnum=Math.abs((long)numerator);longden=Math.abs((long)denominator);// 3. 整数部分sb.append(num/den);longremainder=num%den;if(remainder==0){returnsb.toString();}// 4. 小数部分sb.append('.');Map<Long,Integer>map=newHashMap<>();// 余数 -> 小数位起始下标while(remainder!=0){// 若余数已出现过，说明开始循环if(map.containsKey(remainder)){intindex=map.get(remainder);sb.insert(index,'(');sb.append(')');break;}// 记录当前余数对应的小数位下标（在添加该位之前记录）map.put(remainder,sb.length());remainder*=10;sb.append(remainder/den);// 当前小数位remainder%=den;// 更新余数}returnsb.toString();}}

关键点

1. 符号处理：使用 ^ 异或判断异号，避免直接乘负数导致溢出。
2. 长整型转换：Math.abs((long) numerator) 先转 long 再取绝对值，防止 -2147483648 取反溢出。
3. 循环检测：map 的 key 是余数，value 是该余数对应的小数位在 StringBuilder 中的下标。当余数重复时，从该下标处插入 (，末尾补 )。
4. 下标记录时机：在将当前余数乘 10 并添加小数位之前记录 sb.length()，这样插入位置才准确。
5. 整数部分为 0：例如 -1/2 会生成 -0.5，逻辑依然正确。

复杂度

· 时间：O(d)，d 为分母大小（余数最多有 d 种，循环最多执行 d 次）
· 空间：O(d)，哈希表存储余数

测试用例

fractionToDecimal(1,2)// "0.5"fractionToDecimal(2,1)// "2"fractionToDecimal(4,333)// "0.(012)"fractionToDecimal(1,6)// "0.1(6)"fractionToDecimal(-1,2)// "-0.5"fractionToDecimal(-2147483648,-1)// "2147483648"