CONY的世界

211. Add and Search Word - Data structure design

 
Design a data structure that supports the following two operations:
 

523. Continuous Subarray Sum

 
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

50. Pow(x, n)
Implement pow(x, n).

Success:
56 ms, beats 14.53 % of python submissions
先用最簡單的方式做

151. Reverse Words in a String
Given an input string, reverse the string word by word.
 For example,
Given s = "the sky is blue",
return "blue is sky the".

18. 4Sum
 

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

 
Success:
我一開始想到的方法比較慢，先固定two sum 然後再用left, right 找到剩餘符合 target value 的值
當然two sum 還是要考慮到不能重複，所以才會在for loop 一開始有個醜醜的判斷式來決定到底要不要做
1008 ms, beats 36.12 % of python submissions

8. String to Integer (atoi)
 
Implement atoi to convert a string to an integer.

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

 

 

 

 

442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
 
Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

 Success: 本來的做法update在github裡面，採用先sort在比對的方式，不過performance不好，所以跑去看論壇裡的解法
這題最快的人是用set寫，但是我覺得多開一個seen set這種做法應該不行，因為多用了extra space啊
自己實作論壇裡我認為可行的方法，發現一個有趣的現象，我理解後重寫成的版本(399 ms)，發現沒有原版本快，明明只差在< 和 >= ，不知道是不是跟access nums的行數有關係
class Solution(object):
def findDuplicates(self, nums):
"""
        :type nums: List[int]
        :rtype: List[int]
        """
result = [];
for x in nums:
if nums[abs(x)-1] < 0:
result.append(abs(x))
else:
nums[abs(x)-1] *= -1
return result

原版本(309 ms)
class Solution(object):
def findDuplicates(self, nums):
"""
        :type nums: List[int]
        :rtype: List[int]
        """
ret = []
for n in nums:
if nums[abs(n) - 1] >= 0:
nums[abs(n) - 1] *= -1
else:
ret.append(abs(n))
return ret
Fail:
1. Time Limit Exceeded ，list.count() complexity O( nlogn )

同樣是看code學習，把同班同學好的code拿出來看，不懂的筆記在這裡
 
1. 如何有效率free vector memory
因為用clear() 本身只是把element 清掉，但是空間並不會減少，有人主張用resize，不過更好的是用 temporary vector swap