难度: Medium
原题连接
内容描述
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.
Example 1:
Input: numerator = 1, denominator = 2
Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1
Output: "2"
Example 3:
Input: numerator = 2, denominator = 3
Output: "0.(6)"
思路 1 - 时间复杂度: hard to say - 空间复杂度: O(1)******
- 先处理正负号
- 再处理整数部分
- 最后处理小数部分，利用字典来判断是否循环
note：对于小数处理部分，必须先进行将没有处理过的r加入到m中去
这是因为：
例如输入为4, 333
如果我们将已经处理过的r加入到m中去的话，重复数字当次就被加入m中了，下一次循环判断的时候r肯定已经在里面了
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
if numerator == 0: # zero numerator
return '0'
res = ''
if numerator * denominator < 0: # determine the sign
res += '-'
numerator, denominator = abs(numerator), abs(denominator) # remove sign of operands
res += str(numerator / denominator) # append integer part
if numerator % denominator == 0: # in case no fractional part
return res
res += '.'
r = numerator % denominator
m = {}
while r: # simulate the division process
if r in m: # meet a known remainder
res = res[:m[r]] + '(' + res[m[r]:] + ')' # so we reach the end of the repeating part
break
m[r] = len(res) # if the remainder is first seen, remember next r/denominator index in res
r *= 10
res += str(r/denominator) # append the quotient digit
r %= denominator
return res