LeetCode 166. 分数到小数

Categories:

题目描述
思路分析
1. 解法一：哈希表记录循环节（推荐）
相似题目

题目描述

✅ 166. 分数到小数

思路分析

解法一：哈希表记录循环节（推荐）

核心思路：

先处理符号与整数部分，余数用于生成小数部分。

小数部分每一步用 余数 * 10 / 分母 产生一位。

若某个余数重复，说明进入循环，将循环部分用括号包裹。

用哈希表记录余数首次出现的位置，便于插入括号。

复杂度分析：

时间复杂度：O(n)，其中 n 表示小数部分长度（循环节长度）。

空间复杂度：O(n)，其中 n 表示哈希表与结果长度。

import java.util.*;

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        long num = numerator;
        long den = denominator;

        if ((num < 0) ^ (den < 0)) {
            sb.append('-');
        }

        num = Math.abs(num);
        den = Math.abs(den);

        sb.append(num / den);
        long rem = num % den;
        if (rem == 0) {
            return sb.toString();
        }

        sb.append('.');
        Map<Long, Integer> pos = new HashMap<>();

        while (rem != 0) {
            if (pos.containsKey(rem)) {
                int idx = pos.get(rem);
                sb.insert(idx, '(');
                sb.append(')');
                break;
            }

            pos.put(rem, sb.length());
            rem *= 10;
            sb.append(rem / den);
            rem %= den;
        }

        return sb.toString();
    }
}

func fractionToDecimal(numerator int, denominator int) string {
	if numerator == 0 {
		return "0"
	}

	num := int64(numerator)
	den := int64(denominator)
	res := make([]byte, 0)

	if (num < 0) != (den < 0) {
		res = append(res, '-')
	}

	if num < 0 {
		num = -num
	}
	if den < 0 {
		den = -den
	}

	intPart := num / den
	res = append(res, []byte(intToString(intPart))...)

	rem := num % den
	if rem == 0 {
		return string(res)
	}

	res = append(res, '.')
	pos := make(map[int64]int)

	for rem != 0 {
		if idx, ok := pos[rem]; ok {
			res = append(res, ')')
			copy(res[idx+1:], res[idx:])
			res[idx] = '('
			return string(res)
		}

		pos[rem] = len(res)
		rem *= 10
		digit := rem / den
		res = append(res, byte(digit)+'0')
		rem %= den
	}

	return string(res)
}

func intToString(x int64) string {
	if x == 0 {
		return "0"
	}

	buf := make([]byte, 0)
	for x > 0 {
		buf = append(buf, byte(x%10)+'0')
		x /= 10
	}
	for l, r := 0, len(buf)-1; l < r; l, r = l+1, r-1 {
		buf[l], buf[r] = buf[r], buf[l]
	}
	return string(buf)
}

相似题目

题目	难度	考察点
29. 两数相除	中等	位运算、模拟
415. 字符串相加	简单	大数模拟
2. 两数相加	中等	链表、模拟进位
273. 整数转换英文表示	困难	字符串处理
8. 字符串转换整数 (atoi)	中等	字符串解析

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/22146309