LeetCode 166 Fraction to Recurring Decimal

LeetCode

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10<sup>4</sup> for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1
Output: “2”

Example 3:

Input: numerator = 4, denominator = 333
Output: “0.(012)”

Constraints:

-2<sup>31</sup> <= numerator, denominator <= 2<sup>31</sup> - 1 denominator != 0

题目大意：

N/A

解题思路：

小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体

解题步骤：

N/A

注意事项：

1. 小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体，并不是digit一样，而是余数。类似于L003 Longest Substring Without Repeating Characters，记录余数到商下标。循环中顺序很重要，与长除法一致(上图)。分子为remainder，查看remainder是否重复，若否，加入到map，乘以10，求商和新余数，进入下一轮迭代。
2. 输入均为负数或其一为负数的情况，计算结果符号，分子分母分别转成正数
3. 分子大于分母或分子小于分母的情况都归结为用分子除以分母，加入到结果，若有余数，再加小数点

Line 26 - 27与Line 16 - 17一致

Python代码：

def fractionToDecimal(self, numerator: int, denominator: int) -> str:
	res, remainder_to_pos = '', collections.defaultdict(int)
	is_negative, remainder = 1, 0
	if numerator / denominator < 0:
		is_negative = -1
	numerator = abs(numerator)
	denominator = abs(denominator)
	'''
	if numerator < denominator:
		res = '0.'
		remainder = numerator
	else:
		res = str(numerator // denominator)
		remainder = numerator % denominator
	'''
	res = str(numerator // denominator)
	remainder = numerator % denominator
	if remainder > 0:
		res += '.'
	while remainder > 0:
		if remainder in remainder_to_pos:
			res = res[:remainder_to_pos[remainder]] + '(' + res[remainder_to_pos[remainder]:] + ')'
			break
		remainder_to_pos[remainder] = len(res)  # remember
		remainder *= 10 # remember not numerator * 10 // denominator
		res += str(remainder // denominator)
		remainder %= denominator
	return res if is_negative == 1 else '-' + res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)