0166. 分数到小数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 长除法 + 哈希表

1. 📝 题目描述

• leetcode

给定两个整数，分别表示分数的分子 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 - 1
• denominator != 0

2. 🎯 s.1 - 长除法 + 哈希表

c

char* fractionToDecimal(int numerator, int denominator) {
    char* res = (char*)calloc(10001, sizeof(char));
    int pos = 0;
    if (numerator == 0) { res[0] = '0'; return res; }
    // 处理符号
    if ((numerator < 0) ^ (denominator < 0)) res[pos++] = '-';
    long long num = llabs((long long)numerator);
    long long den = llabs((long long)denominator);
    // 整数部分
    pos += sprintf(res + pos, "%lld", num / den);
    long long remainder = num % den;
    if (remainder == 0) return res;
    res[pos++] = '.';
    // 用数组记录余数对应的位置
    long long* rems = (long long*)calloc(10001, sizeof(long long));
    int* remPos = (int*)calloc(10001, sizeof(int));
    int remCount = 0;
    while (remainder != 0) {
        // 检查余数是否出现过
        for (int i = 0; i < remCount; i++) {
            if (rems[i] == remainder) {
                // 插入括号
                int insertPos = remPos[i];
                memmove(res + insertPos + 1, res + insertPos, pos - insertPos);
                res[insertPos] = '(';
                pos++;
                res[pos++] = ')';
                res[pos] = '\0';
                free(rems); free(remPos);
                return res;
            }
        }
        rems[remCount] = remainder;
        remPos[remCount] = pos;
        remCount++;
        remainder *= 10;
        res[pos++] = '0' + (int)(remainder / den);
        remainder %= den;
    }
    res[pos] = '\0';
    free(rems); free(remPos);
    return res;
}

js

/**
 * @param {number} numerator
 * @param {number} denominator
 * @return {string}
 */
var fractionToDecimal = function (numerator, denominator) {
  if (numerator === 0) return '0'
  let res = ''
  // 处理符号
  if (numerator < 0 !== denominator < 0) res += '-'
  let num = Math.abs(numerator)
  let den = Math.abs(denominator)
  // 整数部分
  res += Math.floor(num / den).toString()
  let remainder = num % den
  if (remainder === 0) return res
  res += '.'
  const map = new Map()
  while (remainder !== 0) {
    if (map.has(remainder)) {
      const idx = map.get(remainder)
      return res.slice(0, idx) + '(' + res.slice(idx) + ')'
    }
    map.set(remainder, res.length)
    remainder *= 10
    res += Math.floor(remainder / den).toString()
    remainder %= den
  }
  return res
}

py

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return '0'
        res = []
        if (numerator < 0) != (denominator < 0):
            res.append('-')
        num, den = abs(numerator), abs(denominator)
        res.append(str(num // den))
        remainder = num % den
        if remainder == 0:
            return ''.join(res)
        res.append('.')
        rem_map = {}
        while remainder != 0:
            if remainder in rem_map:
                idx = rem_map[remainder]
                res.insert(idx, '(')
                res.append(')')
                return ''.join(res)
            rem_map[remainder] = len(res)
            remainder *= 10
            res.append(str(remainder // den))
            remainder %= den
        return ''.join(res)

• 时间复杂度：$O(d)$，其中 $d$ 是小数部分的长度
• 空间复杂度：$O(d)$，哈希表存储余数位置

算法思路：

• 先处理符号和整数部分
• 对小数部分模拟长除法，用哈希表记录每个余数首次出现的位置
• 当余数重复出现时，说明开始循环，在对应位置插入括号