How do I handle repeating decimals in the 'Fraction to Recurring Decimal' problem?

You can use long division and a hash table to track remainders. When a remainder repeats, that means the decimal starts repeating from that point.

What is the time complexity of the 'Fraction to Recurring Decimal' problem?

The time complexity depends on the number of digits before the decimal repeats, which can be O(N), where N is the length of the repeating part.

Can the numerator and denominator be negative in this problem?

Yes, the fraction can be negative. The sign of the result should be negative if one of the numerator or denominator is negative, but not both.

What are the edge cases to consider for the 'Fraction to Recurring Decimal' problem?

Edge cases include handling negative numbers, zero denominators (which are invalid), and fractions that result in exact integers or repeating decimals.

What is the primary pattern to solve the 'Fraction to Recurring Decimal' problem?

The primary pattern is to use long division with a hash table to track remainders and identify repeating decimal cycles.

#166

Medium

auto_awesome哈希·数学

LeetCode 题解工作台

分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator ，以字符串形式返回小数。如果小数部分为循环小数，则将循环的部分括在括号内。如果存在多个答案，只需返回任意一个。对于所有给定的输入，保证答案字符串的长度小于 10 4 。注意，如果分数可以表示为…

哈希表数学字符串

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证答案字符串的长度小于 10⁴ 。

注意，如果分数可以表示为有限长度的字符串，则必须返回它。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"

提示：

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

lightbulb

解题思路

方法一：数学 + 哈希表

我们首先判断 $numerator$ 是否为 $0$ ，如果是，则直接返回 "0"。

接着我们判断 $numerator$ 和 $denominator$ 是否异号，如果是，则结果为负数，我们将结果的第一个字符设为 "-"。

然后我们将 $numerator$ 和 $denominator$ 取绝对值，分别记为 $a$ 和 $b$ 。由于分子和分母的范围为 $[-2^{31}, 2^{31} - 1]$ ，直接取绝对值可能会溢出，因此我们将 $a$ 和 $b$ 都转换为长整型。

接着我们计算整数部分，即 $a$ 除以 $b$ 的整数部分，将其转换为字符串并添加到结果中。然后我们将 $a$ 取余 $b$ ，记为 $a$ 。

如果 $a$ 为 $0$ ，说明结果为整数，直接返回结果。

接着我们计算小数部分，我们使用哈希表 $d$ 记录每个余数对应的结果的长度。我们不断将 $a$ 乘以 $10$ ，然后将 $a$ 除以 $b$ 的整数部分添加到结果中，然后将 $a$ 取余 $b$ ，记为 $a$ 。如果 $a$ 为 $0$ ，说明结果为有限小数，直接返回结果。如果 $a$ 在哈希表中出现过，说明结果为循环小数，我们找到循环的起始位置，将结果插入括号中，然后返回结果。

时间复杂度 $O(l)$ ，空间复杂度 $O(l)$ ，其中 $l$ 为结果的长度，本题中 $l < 10^4$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        ans = []
        neg = (numerator > 0) ^ (denominator > 0)
        if neg:
            ans.append("-")
        a, b = abs(numerator), abs(denominator)
        ans.append(str(a // b))
        a %= b
        if a == 0:
            return "".join(ans)
        ans.append(".")
        d = {}
        while a:
            d[a] = len(ans)
            a *= 10
            ans.append(str(a // b))
            a %= b
            if a in d:
                ans.insert(d[a], "(")
                ans.append(")")
                break
        return "".join(ans)

speed

复杂度分析

指标	值
时间	complexity depends on the number of digits in the decimal expansion before repeating, and space complexity depends on the number of remainders encountered. In the worst case, the time and space complexity are both O(N), where N is the number of digits before the decimal starts repeating.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for the candidate's understanding of long division.
question_mark
Evaluate their ability to track repeating decimals efficiently with hash tables.
question_mark
Assess if the candidate is careful with edge cases like negative numbers and zero denominators.

warning

常见陷阱

外企场景

error
Failing to correctly identify the repeating decimal pattern.
error
Not handling negative numbers properly, leading to incorrect results.
error
Not using a hash table efficiently, causing unnecessary recalculations of remainders.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle larger numbers in the numerator and denominator.
arrow_right_alt
Allow more than one repeating decimal cycle (e.g., 1/7 = '0.(142857)').
arrow_right_alt
Modify the problem to handle fractions where the result is an integer, avoiding decimals altogether.

help

常见问题

外企场景

继续练习

#13 罗马数字转整数 #12 整数转罗马数字 #770 基本计算器 IV