CONY的世界

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.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

 Success:

 42ms, beats 47.06 % of python submissions

 在寫出這題的過程當中發現Time Limit Exceeded應該是因為有無限迴圈在.......

所以之前的fail....應該不是因為太慢被擋掉，而是因為邏輯就錯了（No～～～～～)

後來這題邏輯改一改就出來了

依照hint 裡面提到的，只要餘數開始重複後，除數也會開始重複，所以我就用了dict （hash table) 來記載餘數的值和對應到除數的位置

一但之前有記載過，除術也從之前的位子開始repeat

然後這題要注意的是負數的處理，依照wiki提到的（https://zh.wikipedia.org/wiki/余数）

Python语言定义的除法中，不能整除的情况下，余数与除数同号，例如 (−42) / (−5) 表达为

−42 = 8×(−5) + (−2)

而 42 / (-5) 则表达为

42 = (−8)×(−5) + 2

所以有沒有負號會在一開始做判斷，之後都用abs（）後的正值去做計算

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        result = ''
        module = abs(numerator)/abs(denominator)
        if ((numerator> 0 and denominator < 0) or (numerator < 0 and denominator > 0)):
            result += "-"
        result += str(module)
        denominator,numerator = abs(denominator),abs(numerator)
        remainder = numerator%denominator
        if remainder != 0:
            result +='.'
            decimal = ''
            dict = {}
            while remainder != 0:
                if dict.has_key(remainder):
                    result+=decimal[:dict[remainder]] + '('+str(decimal[dict[remainder]:]) + ')' 
                    break
                else:
                    dict[remainder] = len(decimal) 
                    while 10*remainder < denominator:               
                        remainder*= 10
                        decimal+='0'
                        dict[remainder] = len(decimal) 
                    decimal+=str(10*remainder / denominator)
                    remainder = 10*remainder % denominator
            if remainder == 0:
                result += decimal
        return result

 不過我這種寫法太醜不夠簡潔，來改寫成官方分享裡思路跟我一樣的簡潔版

分別是 1.把decimal 拿掉  2.算好的先return，讓後面要處理的case變少 

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        res=''
        if ((numerator> 0 and denominator < 0) or (numerator < 0 and denominator > 0)):
            res='-'
        numerator, denominator = abs(numerator), abs(denominator)
        res += str(numerator/denominator)
        numerator %= denominator
        if numerator == 0:
            return res
        res+='.'
        index, dict = len(res),{}
        while numerator != 0:
            if numerator not in dict.keys():
                dict[numerator] = index 
            else:
                index = dict[numerator]
                res = res[:index]+"("+res[index:]+")"
                return res
            numerator*=10
            res += str(numerator/denominator)
            numerator %=denominator
            index+=1
        return res

 再貼另外一個大神的做法，不過因為跟我思路不太同，就先不實作了

class Solution:
# @return a string
def fractionToDecimal(self, numerator, denominator):
    n, remainder = divmod(abs(numerator), abs(denominator))
    sign = '-' if numerator*denominator < 0 else ''
    result = [sign+str(n), '.']
    stack = []
    while remainder not in stack:
        stack.append(remainder)
        n, remainder = divmod(remainder*10, abs(denominator))
        result.append(str(n))

    idx = stack.index(remainder)
    result.insert(idx+2, '(')
    result.append(')')
    return ''.join(result).replace('(0)', '').rstrip('.')

 3. Longest Substring Without Repeating Characters

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start= maxlength = 0
        Used = {}
        for i in range(len(s)):
            if Used.has_key(s[i]) and start <= Used[s[i]]:
                start = Used[s[i]]+1
            else:
                maxlength = max(maxlength, i-start+1)
                
            Used[s[i]]=i

        return maxlength