难度: Medium
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 104 。
示例 1：
输入：numerator = 1, denominator = 2 输出："0.5"
示例 2：
输入：numerator = 2, denominator = 1 输出："2"
示例 3：
输入：numerator = 4, denominator = 333 输出："0.(012)"
提示：
-231 <= numerator, denominator <= 231 - 1denominator != 0运行时间: 24 ms
内存: 0.0 MB
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
s = '-' if numerator and numerator ^ denominator < 0 else ''
numerator = abs(numerator)
denominator = abs(denominator)
d = numerator // denominator
numerator %= denominator
if numerator == 0:
return s+str(d)
past_res = {}
digits = [s, str(d), '.']
th = 2
while numerator and numerator not in past_res:
th += 1
past_res[numerator] = th
numerator *= 10
d = numerator // denominator
digits.append(str(d))
numerator %= denominator
# print(d, numerator)
return ''.join(digits) if not numerator else ''.join(digits[:past_res[numerator]]) + '(' + ''.join(digits[past_res[numerator]:]) +')'
这个题解使用哈希表来判断小数部分是否存在循环。首先计算整数部分，然后对余数进行逐位计算，同时用哈希表记录每个余数出现的位置。如果某个余数再次出现，说明从上次出现的位置到当前位置构成循环节。最后根据是否存在循环节，构造出最终的结果字符串。
时间复杂度: O(denominator)
空间复杂度: O(denominator)
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
# 处理符号
s = '-' if numerator and numerator ^ denominator < 0 else ''
numerator = abs(numerator)
denominator = abs(denominator)
# 计算整数部分
d = numerator // denominator
numerator %= denominator
# 如果没有余数，直接返回结果
if numerator == 0:
return s+str(d)
# 哈希表记录每个余数出现的位置
past_res = {}
digits = [s, str(d), '.']
th = 2
# 对余数进行逐位计算
while numerator and numerator not in past_res:
th += 1
past_res[numerator] = th
numerator *= 10
d = numerator // denominator
digits.append(str(d))
numerator %= denominator
# 构造最终结果字符串
return ''.join(digits) if not numerator else ''.join(digits[:past_res[numerator]]) + '(' + ''.join(digits[past_res[numerator]:]) +')'
在现代编程语言中，如Python，整数类型通常具有自动扩展的特性，这意味着当整数运算超出固定大小时，整数可以自动扩展以防止溢出。在处理大整数问题时，这一点尤其重要。Python的整数类型是不固定长度的，可以处理任意大的整数，只要内存足够。因此，在将余数乘以10后进行除法运算，不会因为整数溢出而导致错误。
在这个算法中，哈希表中存储的键是余数，而对应的值是该余数在小数部分的具体索引位置。这个索引代表了余数在结果字符串中小数点后的位置。因此，如果同一个余数在哈希表中再次出现，我们可以根据原先记录的索引直接找到小数部分开始循环的位置，从而构造出循环小数的表示。
在长除法中，如果某个余数再次出现，意味着接下来的除法步骤将重复之前的步骤，导致生成相同的数字序列，形成循环。不存在没有循环但余数重复的情况，因为余数的重复直接导致了除法过程的重复。因此，一旦余数在哈希表中被再次发现，就可以确定小数部分开始循环。
异或运算符(^)在这里被用来确定两个数的符号是否相异。如果两个数一个为正一个为负，异或的结果将是负数；如果两个数符号相同（都是正数或都是负数），异或的结果将是正数。这种方法提供了一种简洁的方式来判断结果的符号，省去了复杂的if-else结构，使代码更简洁易读。此外，异或运算通常比比较和条件判断更快，有助于提升算法的执行效率。