LeetCode 166. 分数到小数思路模拟竖式除法确定符号分子分母异号则为负。整数部分numerator / denominator。小数部分每次将余数乘 10再除以分母得到当前位同时更新余数。检测循环用 HashMap 记录每个余数第一次出现时对应的小数位下标。若某余数再次出现说明从该位置开始循环插入括号即可。注意-2^31 / -1 会溢出所以先转成 long 处理。Java 实现classSolution{publicStringfractionToDecimal(intnumerator,intdenominator){if(numerator0)return0;StringBuildersbnewStringBuilder();// 1. 处理符号if((numerator0)^(denominator0)){sb.append(-);}// 2. 转为 long 防止溢出并取绝对值longnumMath.abs((long)numerator);longdenMath.abs((long)denominator);// 3. 整数部分sb.append(num/den);longremaindernum%den;if(remainder0){returnsb.toString();}// 4. 小数部分sb.append(.);MapLong,IntegermapnewHashMap();// 余数 - 小数位起始下标while(remainder!0){// 若余数已出现过说明开始循环if(map.containsKey(remainder)){intindexmap.get(remainder);sb.insert(index,();sb.append());break;}// 记录当前余数对应的小数位下标在添加该位之前记录map.put(remainder,sb.length());remainder*10;sb.append(remainder/den);// 当前小数位remainder%den;// 更新余数}returnsb.toString();}}关键点符号处理使用 ^ 异或判断异号避免直接乘负数导致溢出。长整型转换Math.abs((long) numerator) 先转 long 再取绝对值防止 -2147483648 取反溢出。循环检测map 的 key 是余数value 是该余数对应的小数位在 StringBuilder 中的下标。当余数重复时从该下标处插入 (末尾补 )。下标记录时机在将当前余数乘 10 并添加小数位之前记录 sb.length()这样插入位置才准确。整数部分为 0例如 -1/2 会生成 -0.5逻辑依然正确。复杂度· 时间O(d)d 为分母大小余数最多有 d 种循环最多执行 d 次· 空间O(d)哈希表存储余数测试用例fractionToDecimal(1,2)// 0.5fractionToDecimal(2,1)// 2fractionToDecimal(4,333)// 0.(012)fractionToDecimal(1,6)// 0.1(6)fractionToDecimal(-1,2)// -0.5fractionToDecimal(-2147483648,-1)// 2147483648
DeepSeek LeetCode 166. 分数到小数 Java实现
LeetCode 166. 分数到小数思路模拟竖式除法确定符号分子分母异号则为负。整数部分numerator / denominator。小数部分每次将余数乘 10再除以分母得到当前位同时更新余数。检测循环用 HashMap 记录每个余数第一次出现时对应的小数位下标。若某余数再次出现说明从该位置开始循环插入括号即可。注意-2^31 / -1 会溢出所以先转成 long 处理。Java 实现classSolution{publicStringfractionToDecimal(intnumerator,intdenominator){if(numerator0)return0;StringBuildersbnewStringBuilder();// 1. 处理符号if((numerator0)^(denominator0)){sb.append(-);}// 2. 转为 long 防止溢出并取绝对值longnumMath.abs((long)numerator);longdenMath.abs((long)denominator);// 3. 整数部分sb.append(num/den);longremaindernum%den;if(remainder0){returnsb.toString();}// 4. 小数部分sb.append(.);MapLong,IntegermapnewHashMap();// 余数 - 小数位起始下标while(remainder!0){// 若余数已出现过说明开始循环if(map.containsKey(remainder)){intindexmap.get(remainder);sb.insert(index,();sb.append());break;}// 记录当前余数对应的小数位下标在添加该位之前记录map.put(remainder,sb.length());remainder*10;sb.append(remainder/den);// 当前小数位remainder%den;// 更新余数}returnsb.toString();}}关键点符号处理使用 ^ 异或判断异号避免直接乘负数导致溢出。长整型转换Math.abs((long) numerator) 先转 long 再取绝对值防止 -2147483648 取反溢出。循环检测map 的 key 是余数value 是该余数对应的小数位在 StringBuilder 中的下标。当余数重复时从该下标处插入 (末尾补 )。下标记录时机在将当前余数乘 10 并添加小数位之前记录 sb.length()这样插入位置才准确。整数部分为 0例如 -1/2 会生成 -0.5逻辑依然正确。复杂度· 时间O(d)d 为分母大小余数最多有 d 种循环最多执行 d 次· 空间O(d)哈希表存储余数测试用例fractionToDecimal(1,2)// 0.5fractionToDecimal(2,1)// 2fractionToDecimal(4,333)// 0.(012)fractionToDecimal(1,6)// 0.1(6)fractionToDecimal(-1,2)// -0.5fractionToDecimal(-2147483648,-1)// 2147483648
