jinhuang1102

166. Fraction to Recurring Decimal

Feb 26th, 2019
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.63 KB | None | 0 0
  1. class Solution(object):
  2.     def fractionToDecimal(self, n, d):
  3.         """
  4.        :type numerator: int
  5.        :type denominator: int
  6.        :rtype: str
  7.        """
  8.         #排除分子是0 或者 分子与分母相等的情况
  9.         if n == 0:
  10.             return "0"
  11.         if n == d:
  12.             return "1"
  13.  
  14.         # 确定符号
  15.         sign = ""
  16.         if (n > 0) ^ (d > 0):
  17.             sign = "-"
  18.  
  19.         n = abs(n)
  20.         d = abs(d)
  21.  
  22.         #开始计算
  23.         if d == 1:
  24.             res = str(n)
  25.         else:
  26.             q, r, idx = 0, 0, 0
  27.             remainder = {} # <key, value> => <余数, 余数所对应的商在decimal中的index>
  28.             decimal = []
  29.  
  30.             if n > d:
  31.                 q = n // d
  32.                 r = n % d
  33.             else:
  34.                 r = n % d
  35.            
  36.             # 当余数重复以后商也开始重复
  37.             while not r in remainder and r != 0:
  38.                 remainder[r] = idx
  39.                 idx += 1
  40.                
  41.                 tmp = r * 10
  42.                 tmp_q = tmp // d
  43.                 decimal.append(str(tmp_q))
  44.                 r = tmp % d
  45.  
  46.             # 当有小数的时候
  47.             if decimal:
  48.                 if r == 0:
  49.                     res = str(q) + "." + "".join(decimal)
  50.                 else:
  51.                     # r != 0 说明是循环小数
  52.                     pos = remainder[r]
  53.                     decimal.insert(pos, "(")
  54.                     decimal.append(")")
  55.                     res = str(q) + "." + "".join(decimal)
  56.  
  57.             else:
  58.                 res = str(q)
  59.  
  60.         return sign + res
Advertisement
Add Comment
Please, Sign In to add comment