166. 分数到小数

https://leetcode-cn.com/problems/fraction-to-recurring-decimal/

解法一：用hashmap找循环节

主要难点就是找出循环小数的循环节，观察：

5/4=1.25

1/3=0.333333...

4/333=0.0120120120...

1/7=0.14285714285714...

1/70=0.014285714285714285...

可知 循环节（用粗体标出）就是第一个重复的部分。在小学学过的竖式除法中可知，若遇到出现过的被除数，之后就是无限的循环。

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        res = ""
        #同号为正，异号位负，用异或实现
        res += '-' if (numerator > 0) ^ (denominator > 0) else ''
        num = abs(numerator)
        den = abs(denominator)
        
        #整数部分
        res += str(num // den)
        num %= den
        if num == 0:
            return res
        
        #小数部分
        res += '.'
        #将小数循环节存入map中
        #num作为键，值为当前串的长度
        hashMap = {}
        #初始化
        hashMap[num] = len(res)
        #就像竖式除法一样，每次*10（添0）再除
        while num != 0:
            num *= 10
            res += str(num // den)
            num %= den
            #若遇到出现过的被除数，即出现循环节
            if num in hashMap:
                #查map得到循环节出现的第一个位置，插入括号
                idx = hashMap[num]
                res = res[:idx] + '(' + res[idx:]
                res += ')'
                break
            else:  #否则记录map
                hashMap[num] = len(res)                
        return res