166. Fraction to Recurring Decimal
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
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.
Success:
92ms, beats 77.14 % of python submissions
這題也是看官方解，用loop 和 start 來尋找不重複的sunstring
一但遇到重複的char（已存在dic裡面)就要把start reset 到重複字元的下一個位置算起（因為一個字元至多只能出現一次）
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
