Like San Mateo
Table of Content
Table of Content637. Average of Levels in Binary Tree 7
597. Friend Requests I: Overall Acceptance Rate 8
157. Read N Characters Given Read4 8
398. Random Pick Index 8
314. Binary Tree Vertical Order Traversal 9
209. Minimum Size Subarray Sum 10
283. Move Zeroes 11
311. Sparse Matrix Multiplication 11
17. Letter Combinations of a Phone Number 11
91. Decode Ways 12
56. Merge Intervals 12
49. Group Anagrams 13
43. Multiply Strings 14
128. Longest Consecutive Sequence 14
297. Serialize and Deserialize Binary Tree 15
23. Merge k Sorted Lists 16
325. Maximum Size Subarray Sum Equals k 17
252. Meeting Rooms 17
253. Meeting Rooms II 18
277. Find the Celebrity 18
161. One Edit Distance 19
377. Combination Sum IV 20
211. Add and Search Word - Data structure design 21
477. Total Hamming Distance 23
286. Walls and Gates 23
146. LRU Cache 23
285. Inorder Successor in BST 25
261. Graph Valid Tree 25
274. H-Index 27
117. Populating Next Right Pointers in Each Node II 27
275. H-Index II 28
208. Implement Trie (Prefix Tree) 28
554. Brick Wall 30
525. Contiguous Array 31
523. Continuous Subarray Sum 32
621. Task Scheduler 33
210. Course Schedule II 34
636. Exclusive Time of Functions 35
653. Two Sum IV - Input is a BST 36
15. 3Sum 36
121. Best Time to Buy and Sell Stock 37
75. Sort Colors 38
78. Subsets 38
79. Word Search 39
238. Product of Array Except Self 40
33. Search in Rotated Sorted Array 40
90. Subsets II 41
380. Insert Delete GetRandom O(1) 41
88. Merge Sorted Array 43
26. Remove Duplicates from Sorted Array 43
80. Remove Duplicates from Sorted Array II 44
69. Sqrt(x) 45
168. Excel Sheet Column Title 45
173. Binary Search Tree Iterator 45
572. Subtree of Another Tree 46
543. Diameter of Binary Tree 47
404. Sum of Left Leaves 47
200. Number of Islands 48
133. Clone Graph 49
278. First Bad Version 49
461. Hamming Distance 50
477. Total Hamming Distance 50
67. Add Binary 50
125. Valid Palindrome 51
49. Group Anagrams 52
25. Reverse Nodes in k-Group 52
301. Remove Invalid Parentheses 53
76. Minimum Window Substring 55
79. Word Search 55
Replace %20 56
62. Unique Paths 56
63. Unique Paths II 57
367. Valid Perfect Square 58
98. Validate Binary Search Tree 58
234. Palindrome Linked List 59
637. Average of Levels in Binary Tree
思路: BFS, 每層算 average
# self.right = None
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
q, res, path = [], [], []
q.append(root)
while q:
for i in range(len(q)):
temp = q[0]
del q[0]
path.append(temp.val)
if temp.left: q.append(temp.left)
if temp.right: q.append(temp.right)
res.append(sum(path)/(len(path)/1.0))
path = []
return res
597. Friend Requests I: Overall Acceptance Rate
思路: SQL 題
SELECT case when res.num_requests = 0 then 0.00 else ROUND(res.num_accepted*1.0/res.num_requests,2) end as accept_rate
FROM
(SELECT COUNT(DISTINCT f.sender_id, f.send_to_id) as num_requests, COUNT(DISTINCT r.requester_id, r.accepter_id) as num_accepted
FROM friend_request f, request_accepted r) res
157. Read N Characters Given Read4
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
read_bytes, buffers = 0 , [''] * 4
for i in range(n/4 + 1):
size = read4(buffers)
if size:
buf[read_bytes : read_bytes + size] = buffers
read_bytes += size
else:
break
return min(n, read_bytes)
398. Random Pick Index
思路: 設計題, 記得用 random.randint()
class Solution(object):
def __init__(self, nums):
"""
:type nums: List[int]
:type numsSize: int
"""
self.nums = nums
self.numsSize = len(nums)
self.r = []
def pick(self, target):
"""
:type target: int
:rtype: int
"""
for i in xrange(self.numsSize):
if self.nums[i] == target:
self.r.append(i)
x = self.r[random.randint(0,len(self.r)-1)]
self.r = []
return x
314. Binary Tree Vertical Order Traversal
思路: BFS 遞迴, 新增一個 index 每次往左加子數 就減 1 往右則加 1
最後根據 index 加到 res
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []
q, path, res, col = [], {}, [], 0
col_min, col_max = 0, 0
q.append([root,col])
while q:
for i in range(len(q)):
# pop left
temp = q[0]
del q[0]
# have the flag to remember the left / right bound
if temp[1] > col_max: col_max = temp[1]
if temp[1] < col_min: col_min = temp[1]
# save val base on column level
if temp[1] not in path:
path[temp[1]] = [temp[0].val]
else:
path[temp[1]].append(temp[0].val)
# add child node into queue
if temp[0].left: q.append( [temp[0].left, temp[1]-1] )
if temp[0].right: q.append( [temp[0].right, temp[1]+1] )
# format the result
for j in range( col_min, col_max+1 ):
res.append( path[j] )
return res
Second try:
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
m = {}
res = []
q = []
q.append((root, 0))
while q:
temp = q[0]
del q[0]
if temp[1] not in m:
m[temp[1]] = [temp[0].val]
else:
m[temp[1]].append(temp[0].val)
if temp.left: q.append(temp[0].left, temp[1]-1)
if temp.right: q.append(temp[0].right, temp[1]+1)
l, r = 0, 0
while l in m:
l -= 1
l += 1
while r in m:
r += 1
r -= 1
for i in range(l,r+1):
res.append(m[i])
return res
209. Minimum Size Subarray Sum
思路: 最短子數組和, 要求兩種寫法 O(N), O(n log n)
O(n) : 雙指針
O(n log n) : 二分搜索
值得特別注意的是 題目要求的是 大於等於 target 這裡就是 s. 而不是僅僅等於 target就好
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
size = len(nums)
start, end, ans, tot = 0, 0, size + 1, 0
while True:
if tot < s:
if end == size: break
tot += nums[end]
end += 1
else:
if start > end: break
ans = min((end - start), ans)
tot -= nums[start]
start += 1
return ans if ans <= size else 0
283. Move Zeroes
思路: 經典題, 雙指針 一定要多練習
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
y = 0
for i in range(len(nums)):
if nums[i]:
nums[i], nums[y] = nums[y], nums[i]
y += 1
Second Try: 用count 和 deep copy
numberOfZero = nums.count(0)
nonZero = [x for x in nums if x != 0]
nums[:] = nonZero + [0] * numberOfZero
311. Sparse Matrix Multiplication
class Solution(object):
def multiply(self, A, B):
mA,nA,nB = len(A),len(A[0]),len(B[0])
res = [[0]*len(B[0]) for _ in xrange(mA)]
for i in xrange(mA):
for j in xrange(nA):
if A[i][j]:
for k in xrange(nB):
res[i][k] += A[i][j]*B[j][k]
return res
def multiply(self, A, B):
mA,nA,nB = len(A),len(A[0]),len(B[0])
res = [[0]*len(B[0]) for _ in xrange(mA)]
for i in xrange(mA):
for j in xrange(nA):
if A[i][j]:
for k in xrange(nB):
res[i][k] += A[i][j]*B[j][k]
return res
我们知道一个 i x k 的矩阵A乘以一个 k x j 的矩阵B会得到一个 i x j 大小的矩阵C，那么我们来看结果矩阵中的某个元素C[i][j]是怎么来的，起始是A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][k]*B[k][j]
17. Letter Combinations of a Phone Number
思路: DFS, 對每個數字代表的字母 DFS
class Solution(object):
def letterCombinations(self, digits):
def dfs(index, path):
if index == size:
res.append(path)
Return
#防止input 不 [2-9]
if digits[index] not in dict:
dfs(index+1, path+'*')
else:
for i in dict[digits[index]]:
dfs(index+1, path+i)
dict = {'2': ['a','b','c'],'3': ['d','e','f'],'4': ['g','h','i'],
'5': ['j','k','l'],'6': ['m','n','o'],'7': ['p','q','r','s'],
'8': ['t','u','v'],'9': ['w','x','y','z']
}
res, size = [], len(digits)
if not size: return res
dfs(0, '')
return res
91. Decode Ways
思路: 求有幾種方法的題目, 通常用DP
这道题要求解码方法，跟之前那道 Climbing Stairs 爬梯子问题 非常的相似，但是还有一些其他的限制条件，比如说一位数时不能为0，两位数不能大于26，其十位上的数也不能为0，出去这些限制条件，根爬梯子基本没啥区别，也勉强算特殊的斐波那契数列，当然需要用动态规划Dynamci Programming来解。建立一位dp数组，长度比输入数组长多多2，全部初始化为1，因为斐波那契数列的前两项也为1，然后从第三个数开始更新，对应数组的第一个数。对每个数组首先判断其是否为0，若是将改为dp赋0，若不是，赋上一个dp值，此时相当如加上了dp[i - 1], 然后看数组前一位是否存在，如果存在且满足前一位不是0，且和当前为一起组成的两位数不大于26，则当前dp值加上dp[i - 2], 至此可以看出来跟斐波那契数组的递推式一样
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s=="" or s[0]=='0': return 0
dp=[1,1]
for i in range(2,len(s)+1):
if 10 <=int(s[i-2:i]) <=26 and s[i-1]!='0':
dp.append(dp[i-1]+dp[i-2])
elif int(s[i-2:i])==10 or int(s[i-2:i])==20:
dp.append(dp[i-2])
elif s[i-1]!='0':
dp.append(dp[i-1])
else:
return 0
return dp[len(s)]
Second Try:
class Solution(object):
def numDecodings(self, s):
if not s: return 0
dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(1,len(s)+1):
if s[i-1] != '0':
dp[i] = dp[i-1]
if i > 1 and 10 <= int(s[i-2:i]) <= 26:
dp[i] += dp[i-2]
print dp
return dp[-1]
56. Merge Intervals
思路: 區間合併, 這題跟 meeting room II 很像 就是檢查當前的interval 可不可以和別人合併
我們可以先排序 這樣就只要掃一遍 intervals, 邊掃邊合併就ok!
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
intervals = sorted(intervals, key=lambda x: x.start)
result = []
for interval in intervals:
if len(result) == 0 or result[-1].end < interval.start:
result.append(interval)
else:
result[-1].end = max(result[-1].end, interval.end)
return result
二刷:
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
res = []
intervals = sorted(intervals, key=lambda x: x.start)
for i in range(len(intervals)):
# Do merge
if len(res) == 0 or res[-1].end < intervals[i].start:
temp = Interval()
temp.start = intervals[i].start
temp.end = intervals[i].end
res.append(temp)
else:
res[-1].end = max(res[-1].end, intervals[i].end)
return res
三刷:
res = []
intervals = sorted(intervals, key = lambda x: x.start)
for i in range(len(intervals)):
if len(res) == 0 or res[-1].end < intervals[i].start:
res.append(intervals[i])
else:
res[-1].end = max(res[-1].end, intervals[i].end)
return res
49. Group Anagrams
思路: 錯位詞, 指的是 長度一樣但是 element 位置不同 比方說 abc和cba
掃一遍題目給的 list 對 每個詞排序 之後丟進字典
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
res, dic = [], {}
for i in strs:
temp = "".join(sorted(list(i)))
if temp in dic:
dic[temp].append(i)
else:
dic[temp] = [i]
for j in dic:
res.append(dic[j])
return res
43. Multiply Strings
思路: 大數相乘, 分三個步驟
- 數字兩兩相乘 像 直式乘法
- 計算進位
- 去掉所有開頭的 0
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
size_1 = len(num1)
size_2 = len(num2)
size_total = size_1 + size_2
res = [ 0 for _ in range(size_total) ]
num1, num2 = num1[::-1], num2[::-1]
for i in range(size_1):
for j in range(size_2):
res[ i+j ] += int(num1[i]) * int(num2[j])
for k in range(len(res)):
if k < len(res)-1:
res[k+1] += res[k] / 10
res[k] %= 10
res[k] = str(res[k])
for _ in range(len(res)):
res[_] = str(res[_])
res = res[::-1]
while res:
if res[0] == '0':
del res[0]
else:
break
return ''.join(res) if len(res) >= 1 else '0'
128. Longest Consecutive Sequence
思路: 雙指針包夾的window, 找出最長的window size. 這裡因為題目是問 連續的序列所以我們找window的時候是對 nums的值一個一個做搜索 往上跟往下找出window的大小 一旦找到了上界 則 flag = 1 同樣的找到了下界 flag2 = 1
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
dict = collections.Counter(nums)
# corner case
if len(nums) <= 1: return len(nums)
# algr
for i in range(len(nums)):
start = 0
end = 0
j = 1
flag, flag2 = 0, 0
while True:
if flag == 0 and nums[i]+j in dict: end += 1
else: flag += 1
if flag2 == 0 and nums[i]-j in dict: start -= 1
else: flag2 += 1
if flag > 0 and flag2 > 0:
break
j += 1
res = max((end-start)+1, res)
# bracktrack, if we already found the best case
if res == len(nums): return res
return res
297. Serialize and Deserialize Binary Tree
思路: 對BST 拆分 再組合回來. 都用 DFS 進行前序遍歷, 組合回來的時候用,
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def dfs(node):
if not node: return
res.append(str(node.val))
if node.left: dfs(node.left)
else: res.append('null')
if node.right: dfs(node.right)
else: res.append('null')
res = []
dfs(root)
return res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def dfs():
val = vals.next()
if val == 'null': return
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
if not data: return []
vals = iter(data)
return dfs()
23. Merge k Sorted Lists
思路: 先寫一個 merge two list 的 function. 之後對 k 倆倆合併
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
def mergeTwoLists(l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 and not l2: return
if l1 and not l2: return l1
if l2 and not l1: return l2
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
dummy.next = l1
dummy = dummy.next
l1 = l1.next
else:
dummy.next = l2
dummy = dummy.next
l2 = l2.next
if l1: dummy.next = l1
if l2: dummy.next = l2
return curr.next
while lists:
if len(lists) <= 1:
return lists[0]
else:
temp = mergeTwoLists(lists[0], lists[1])
lists[1] = temp
del lists[0]
325. Maximum Size Subarray Sum Equals k
思路: 使用字典数据结构，然后累加之后对index进行比较。
Tip：累加为0需要先填写，否则中间段出现的0的话，就会值计算从中间段开始的index，而出现0的话应该从头计算，因为之前的所有加起来刚好是0，需要补充到最大的subarray里。
class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
res , acc = 0, 0
dic = {0: -1}
for i in range(len(nums)):
acc += nums[i]
if acc not in dic:
dic[acc] = i
if acc - k in dic:
res = max(res, i - dic[acc-k])
return res
252. Meeting Rooms
思路: 對room的schedule 做個排序
假設 schedule [1,3] 給request [2,4] 則 返回 False. 所以我們要判斷schedule.end < request.start 則返回 False
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def canAttendMeetings(self, intervals):
"""
:type intervals: List[Interval]
:rtype: bool
"""
intervals = sorted(intervals, key = lambda intervals : intervals.start)
if len(intervals) <= 1: return True
for i in range( 1,len(intervals) ):
before = intervals[i-1].end
end = intervals[i].start
if end < before :
return False
return True
253. Meeting Rooms II
思路:
掃所有房間的 schedule
關鍵在如果 meeting.start >= root. end 則不用增加新房間 只要把 room.end 延伸至 meeting.start
否則新增
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
room = 0
meetings = []
for i in sorted(intervals, key = lambda intervals : intervals.start):
found = False
for meeting in meetings:
# continue push end boundary
if i.start >= meeting.end:
meeting.end = i.end
found = True
break
if not found:
meetings.append(i)
room += 1
return room
277. Find the Celebrity
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):
思路:
兩個邏輯:
如果 a 知道 b 則 a 不是名人
如果 a 不知道 b 則 b 不是名人
題目說只有0個或1個名人在 party 我們先掃一遍pool 如果a 知道b 則a 自己本身一定不是名人 candidate = b
之後分成前後兩半 做判斷~
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):
class Solution(object):
def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
for i in xrange(n):
if knows(res, i): res = i
for i in xrange(res):
if knows(res, i) or not knows(i, res): return -1
for i in xrange(res + 1, n):
if knows(res, i) or not knows(i, res): return -1
return res
思路:
兩個邏輯:
如果 a 知道 b 則 a 不是名人
如果 a 不知道 b 則 b 不是名人
題目說只有0個或1個名人在 party 我們先掃一遍pool 如果a 知道b 則a 自己本身一定不是名人 candidate = b
分成兩半可以合併 成一個 for loop 用 if res == i 判斷並跳過
時間複雜度 O(n)
空間複雜度 O(1)
class Solution(object):
def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
for i in range(n):
if knows(res, i): res = i
for i in range(n):
if i == res: continue
if knows(res, i) or not knows(i, res): return -1
return res
161. One Edit Distance
思路: 掃一遍字串 如果兩字串的某個element 不相等 則分為三種情況
- 字串s 比 字串 t 長
- 兩字串等長
- 字串s 比字串t 短
分別比較 element 之後的字串是否相等, 如果都沒有某個element 不相等
則最後檢查一下 兩字串長是否相差 1
import collections
class Solution(object):
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
sl = len(s)
tl = len(t)
flag = 0
if abs(sl - tl) > 1 : return False
for i in range(min(sl, tl)):
if s[i] != t[i]:
if sl > tl: return s[i+1:] == t[i:]
elif sl == tl: return s[i+1:] == t[i+1:]
else: return s[i:] == t[i+1:]
return abs(sl - tl) == 1
377. Combination Sum IV
思路: 傳統dfs 遞迴花的時間太久, 用DP 來做 if i + x <= target: dp[i + x] += dp[i]
DP:
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [1] + [0] * target
for i in xrange(target + 1):
for x in nums:
if i + x <= target:
dp[i + x] += dp[i]
return dp[target]
DFS: LTE
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nl = len(nums)
if nl == 0: return 0
res = []
def dfs(node, path):
path.append(node)
if sum(path) > target: return
elif sum(path) == target:
if path not in res:
res.append(path)
else:
for j in range(nl):
dfs(nums[j], path[:])
for i in range(nl):
dfs(nums[i], [])
return len(res)
211. Add and Search Word - Data structure design
思路: 設計題, 在 add的時候 設計 pool 為一個字典 增加搜索速度
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.pool = {}
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
if len(word) not in self.pool:
self.pool[len(word)] = [word]
if word not in self.pool[len(word)]:
self.pool[len(word)].append(word)
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
Ndot = []
wl = len(word)
for i in range(len(word)):
if word[i] != '.':
Ndot.append(i)
if wl in self.pool:
for j in self.pool[wl]:
flag = 0
if len(j) == len(word):
for k in Ndot:
if word[k] != j[k]:
flag = 1
break
if flag == 0 : return True
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
Second Try:
複雜度 O(n^2)
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.pool = {}
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
if len(word) not in self.pool:
self.pool[len(word)] = [word]
elif word not in self.pool[len(word)]:
self.pool[len(word)].append(word)
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
if len(word) in self.pool:
if word in self.pool[len(word)]:
#print "h1"
return True
else:
for i in range(len(self.pool[len(word)])):
for j in range(len(word)):
if word[j] == '.' or word[j] == self.pool[len(word)][i][j]:
if j == len(word)-1:
return True
continue
else:
break
return False
477. Total Hamming Distance
思路: 計算所有 0 和 1 的個數 然後相乘
class Solution(object):
def totalHammingDistance(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
for x in range(32):
mask = 1 << x
zero = one = 0
for num in nums:
if num & mask:
one += 1
else:
zero += 1
ans += zero * one
return ans
286. Walls and Gates
思路: 大神的解答, 先找出0 也就是門的位置 然後對門的四周做BFS 超出矩陣就不算
每到一格矩陣內的值 加一 並把他丟進 queue
class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
q = [(i, j) for i, row in enumerate(rooms) for j, r in enumerate(row) if not r]
for i, j in q:
for I, J in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if 0 <= I < len(rooms) and 0 <= J < len(rooms[0]) and rooms[I][J] > 2**30:
rooms[I][J] = rooms[i][j] + 1
q += (I, J),
146. LRU Cache
思路: 這裡用orderedDict 做 會很直觀
Get: 相對簡單的 function. 如果值存在 就把這值拉到最新更新 沒有就返回 -1
Put: 如果值存在 拉出來並且更新放回去 或者 catch 值已滿 就先丟掉最少用的 在放新值 進去
另一種做法是 dict + double link list
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.cache = collections.OrderedDict()
def get(self, key):
"""
:type key: int
:rtype: int
"""
if not key in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Second try:
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.cache = collections.OrderedDict()
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.cache:
return -1
else:
self.cache[key] = self.cache.pop(key)
return self.cache[key]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
285. Inorder Successor in BST
思路:
这种方法充分地利用到了BST的性质，我们首先看根节点值和p节点值的大小，如果根节点值大，说明p节点肯定在左子树中，那么此时我们先将res赋为root，然后root移到其左子节点，循环的条件是root存在，我们再比较此时root值和p节点值的大小，如果还是root值大，我们重复上面的操作，如果p节点值，那么我们将root移到其右子节点，这样当root为空时，res指向的就是p的后继节点
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
res = None
while root:
if root.val > p.val:
res = root.val
root = root.left
else:
root = root.right
return res
261. Graph Valid Tree
思路: 題目問給的edges可不可以畫出一棵樹, 樹的本值是連通並且無環.
構造圖的時候 記得兩點互聯 也就是這段
graph = defaultdict(list)
for edge in edges:
u,v = edge[0], edge[1]
graph[u].append(v)
graph[v].append(u)
from collections import defaultdict
class Solution(object):
def dfs(self, node, parent, graph, visited):
visited.add(node)
for nbr in graph[node]:
if nbr not in visited:
if self.dfs(nbr, node, graph, visited):
return True
elif nbr in visited and nbr != parent:
return True
return False
def validTree(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: bool
"""
graph = defaultdict(list)
for edge in edges:
u,v = edge[0], edge[1]
graph[u].append(v)
graph[v].append(u)
visited = set([])
if self.dfs(0, -1, graph, visited): # check if there is a loop
return False
if len(visited) != n: # check if 連通
return False
return True
大神版解答:
思路: 樹的本值是連通並且無環 大神厲害就在這 用dict.pop() 判斷. 如果有環 就會出現有element 還在 neighbors裏頭 根據最後一行 and not neighbors 結果一定是 False.
判斷連通也是同樣的道理 如果全連通 則 neighbors 裡不會有任何的 elemen. 這裡可以說是一石二鳥.
def validTree(self, n, edges):
# 建立鄰接表
neighbors = {i: [] for i in range(n)}
for v, w in edges:
neighbors[v] += w,
neighbors[w] += v,
def visit(v):
map(visit, neighbors.pop(v, []))
visit(0)
return len(edges) == n-1 and not neighbors
neighbors = {i: [] for i in range(n)}
for v, w in edges:
neighbors[v] += w,
neighbors[w] += v,
def visit(v):
map(visit, neighbors.pop(v, []))
visit(0)
return len(edges) == n-1 and not neighbors
274. H-Index
思路: 引用次數 先由大到小排序 然後i >= cutations[i] 則返回 i
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
citations.sort(reverse = True)
for i in range(len(citations)):
if i >= citations[i]:
return i
return len(citations)
117. Populating Next Right Pointers in Each Node II
思路: BFS 每層的treeNode 放入 list. 等掃完整層 就串接list裏頭的treeNode
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
q, path = [], []
if not root: return root
q.append(root)
while q:
path = []
for i in range(len(q)):
temp = q[0]
del q[0]
path.append(temp)
if temp.left: q.append(temp.left)
if temp.right: q.append(temp.right)
for j in range(len(path)):
if j != len(path)-1:
path[j].next = path[j+1]
path[-1].next = None
275. H-Index II
思路: 二分搜索
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
N = len(citations)
low, high = 0, N - 1
while low <= high:
mid = (low + high) / 2
if N - mid > citations[mid]:
low = mid + 1
else:
high = mid - 1
return N - low
208. Implement Trie (Prefix Tree)
思路: Trie 用在字串搜索很快, root 的健值為 空. TrieNode 的孩子用字典存取 增加速度
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.children = dict()
self.isWord = False
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
node = self.root
for i in range(len(word)):
if word[i] not in node.children:
temp = TrieNode()
node.children[word[i]] = temp
node = node.children[word[i]]
node.isWord = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.root
for i in range(len(word)):
if word[i] not in node.children:
return False
node = node.children[word[i]]
return node.isWord
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.root
for i in range(len(prefix)):
if prefix[i] not in node.children:
return False
node = node.children[prefix[i]]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
554. Brick Wall
思路: 找出最少磚塊的一條線, 用字典來做. 要注意線不在左右兩邊
class Solution(object):
def leastBricks(self, wall):
"""
:type wall: List[List[int]]
:rtype: int
"""
res = {}
for i in range(len(wall)):
cnt = 0
for j in range(len(wall[i])):
res.setdefault(cnt,0)
if cnt : res[cnt] += 1
cnt += wall[i][j]
return len(wall) - max(res.values()) or 0
Second try:
class Solution(object):
def leastBricks(self, wall):
"""
:type wall: List[List[int]]
:rtype: int
"""
hashmap = {}
li = []
for i in range(len(wall)):
end = 0
for j in range(len(wall[i])):
end += wall[i][j]
hashmap[end] = hashmap.get(end, 0) + 1
for j in hashmap:
li.append(hashmap[j])
li.sort()
if len(hashmap) <= 1:
return len(wall)
return li[-1] - li[-2]
525. Contiguous Array
思路: 用字典 並且起始值 {0 : -1}
我们需要用到一个trick，遇到1就加1，遇到0，就减1，这样如果某个子数组和为0，就说明0和1的个数相等，这个想法真是太叼了，不过博主木有想出来。知道了这一点，我们用一个哈希表建立子数组之和跟结尾位置的坐标之间的映射。如果某个子数组之和在哈希表里存在了，说明当前子数组减去哈希表中存的那个子数字，得到的结果是中间一段子数组之和，必然为0，说明0和1的个数相等，我们更新结果res，参见代码如下：
class Solution(object):
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res, dic, total = 0, {0: -1}, 0
for i in range(len(nums)):
total += 1 if nums[i] == 1 else -1
if total in dic:
res = max(res, i - dic[total])
else:
dic[total] = i
return res
Second try:
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def doit(node):
if node:
vals.append(str(node.val))
doit(node.left)
doit(node.right)
else:
vals.append('#')
vals = []
doit(root)
print vals
return ' '.join(vals)
def deserialize(self, data):
def doit():
i[0] += 1
if vals[i[0]] == '#':
return
node = TreeNode(int(vals[i[0]]))
node.left = doit()
node.right = doit()
return node
vals = data.split()
i = [-1]
return doit()
523. Continuous Subarray Sum
思路: 這題要求不少 要注意條件.
- Sub-array 至少有兩個 element
- Sub-array 總和% k == 0
有好幾種做法, for, hash map, set
class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
for i in range(len(nums)):
sum = nums[i]
for j in range(i+1, len(nums)):
sum += nums[j]
if sum == k and j - i >= 1: return True
if j - i >= 1 and k != 0 and sum % k == 0 : return True
return False
DP:
O(n)就是一维DP.
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，
Max[i+1] = Max[i] + A[i+1], if (Max[i] + A[i+1] >0)
= 0, if(Max[i]+A[i+1] <0)，如果和小于零，A[i+1]必为负数，没必要保留，舍弃掉
然后从左往右扫描，求取Max数字的最大值即为所求。
[Code]
1: int maxSubArray(int A[], int n) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: int sum = 0;
5: int max = INT_MIN;
6: for(int i =0; i < n ; i ++)
7: {
8: sum +=A[i];
9: if(sum>max)
10: max = sum;
11: if(sum < 0)
12: sum = 0;
13: }
14: return max;
15: }
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: int sum = 0;
5: int max = INT_MIN;
6: for(int i =0; i < n ; i ++)
7: {
8: sum +=A[i];
9: if(sum>max)
10: max = sum;
11: if(sum < 0)
12: sum = 0;
13: }
14: return max;
15: }
621. Task Scheduler
思路: 只要求數字 而不是完整的結果
Let's say the most frequent tasks occur M times, and there are Mct of them.
When N > Mct, let's make our scheduling constraint strictly stronger by choosing N = Mct. So from now on, let's suppose Mct <= N, and the most frequent tasks are denoted #A, #B, #C, ... #K.
Then we could schedule say, ABC...K__...ABC...K_...ABC...K_....., where A...K occurs Mct times, _ denotes idle time, and there is Nspace between A's. This partial schedule would have length L = (M-1) * (N+1) + Mct. Clearly, we need at least L intervals of time in our schedule to fit our given tasks.
class Solution(object):
def leastInterval(self, tasks, n):
"""
:type tasks: List[str]
:type n: int
:rtype: int
"""
task_counts = collections.Counter(tasks).values()
M = max(task_counts)
Mct = task_counts.count(M)
return max(len(tasks), (M - 1) * (n + 1) + Mct)
210. Course Schedule II
思路: 拓譜排序, 先找出沒有入度的點 然後開始做dfs. 如果可以完成拓譜排序則 return res
# BFS
def findOrder1(self, numCourses, prerequisites):
dic = {i: set() for i in xrange(numCourses)}
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
# queue stores the courses which have no prerequisites
queue = collections.deque([i for i in dic if not dic[i]])
count, res = 0, []
while queue:
node = queue.popleft()
res.append(node)
count += 1
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
queue.append(i)
return res if count == numCourses else []
# DFS
def findOrder(self, numCourses, prerequisites):
dic = collections.defaultdict(set)
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
stack = [i for i in xrange(numCourses) if not dic[i]]
res = []
while stack:
node = stack.pop()
res.append(node)
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
stack.append(i)
dic.pop(node)
return res if not dic else []
def findOrder1(self, numCourses, prerequisites):
dic = {i: set() for i in xrange(numCourses)}
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
# queue stores the courses which have no prerequisites
queue = collections.deque([i for i in dic if not dic[i]])
count, res = 0, []
while queue:
node = queue.popleft()
res.append(node)
count += 1
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
queue.append(i)
return res if count == numCourses else []
# DFS
def findOrder(self, numCourses, prerequisites):
dic = collections.defaultdict(set)
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
stack = [i for i in xrange(numCourses) if not dic[i]]
res = []
while stack:
node = stack.pop()
res.append(node)
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
stack.append(i)
dic.pop(node)
return res if not dic else []
636. Exclusive Time of Functions
class Solution(object):
def exclusiveTime(self, n, logs):
"""
:type n: int
:type logs: List[str]
:rtype: List[int]
"""
ans = [0] * n
stack = []
prev_time = 0
for log in logs:
fn, typ, time = log.split(':')
fn, time = int(fn), int(time)
if typ == 'start':
if stack:
ans[stack[-1]] += time - prev_time
stack.append(fn)
prev_time = time
else:
ans[stack.pop()] += time - prev_time + 1
prev_time = time + 1
return ans
653. Two Sum IV - Input is a BST
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
def dfs(node):
if not node: return
if node.val not in dist : dist.append(node.val)
if node.left: dfs(node.left)
if node.right: dfs(node.right)
dist = []
dfs(root)
for i in dist:
if k - i != i and k - i in dist: return True
return False
15. 3Sum
思路: sort過後 雙指針
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
temp = []
nums.sort()
nl = len(nums)
for i in range(nl):
if i > 0 and nums[i] == nums[i-1]: continue
#print i
l, r = i +1 , nl - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
121. Best Time to Buy and Sell Stock
思路: buy = min(buy, i), res = max(res, i - buy)
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
res, buy = 0, sys.maxint
for i in prices:
buy = min(buy, i)
res = max(res, i - buy)
return res
75. Sort Colors
思路: one approach, 雙指針交換, 如果nums[i] ==2 記得 i -= 1
Two approach, 統計0,1,2個數 然後返回 list
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
red, white, blue = 0, 0, 0
for i in nums:
if i == 0: red += 1
elif i == 1: white += 1
else: blue += 1
for _ in range( red ):
nums[_] = 0
for _ in range( red, red+white ):
nums[_] = 1
for _ in range( red+white, red+white+blue ):
nums[_] = 2
Second try:
class Solution(object):
def sortColors(self, nums):
i = 0
for _ in range(len(nums)):
if nums[i] == 0:
nums.insert(nums.pop(i), 0)
i += 1
elif nums[i] == 2:
nums.append(nums.pop(i))
else:
i += 1
def sortColors(self, nums):
i = 0
for _ in range(len(nums)):
if nums[i] == 0:
nums.insert(nums.pop(i), 0)
i += 1
elif nums[i] == 2:
nums.append(nums.pop(i))
else:
i += 1
78. Subsets
思路: dfs, path 持續加nums[j]
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def dfs(i, path):
res.append(path)
for j in range(i,len(nums)):
dfs(j+1, path+[nums[j]])
res, path = [], []
dfs( 0, path)
return res
Second try: 更精煉一點的dfs
def dfs(index, path):
res.append(path)
for i in range(index, len(nums)):
dfs( i+1, path+[nums[i]] )
res = []
dfs(0, [])
return res
79. Word Search
思路: dfs 向上下左右 四個方向搜索
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board: return False
m = len(board)
n = len(board[0])
path = []
def dfs(i, j , w):
# all the characters are checked
if len(w) == 0: return True
# check i, j not overboard
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or w[0]!=board[i][j]:
return False
tmp = board[i][j] # first character is found, check the remaining part
board[i][j] = "#" # avoid visit agian
# check whether can find "word" along one direction
res = dfs( i+1, j, w[1:]) or dfs( i-1, j, w[1:]) \
or dfs( i, j+1, w[1:]) or dfs( i, j-1, w[1:])
board[i][j] = tmp
return res
for i in range(m):
for j in range(n):
if dfs(i, j, word):
return True
return False
238. Product of Array Except Self
思路:
Input example = [1,2,3,4]
left = [1,1,2,6]
Result = result * left
左右兩個list 相乘
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n = len(nums)
res = [1] * n
left, right = 1, 1
for i in range(1,n):
left = left * nums[i-1]
res[i] = left
for j in range(n-2, -1, -1):
right = right * nums[j+1]
res[j] *= right
return res
33. Search in Rotated Sorted Array
思路: 二分搜索. 作弊的方法是先 sort 之後再做二分搜索 但是這樣複雜度 從O(log n) 變成O(n log n) . 好的做法是直接在二分搜索裡判斷, 問題來了. 我們不知道 Array 是在哪裡 rotated的, 觀察一下 發現 如果 nums[mid] < nums[right] 則表示右半段是升續的, 相反的, 如果nums[mid] > nums[left] 就表示左半段是升續的.
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r) / 2
if nums[mid] == target:
return mid
elif nums[mid] < nums[r]:
if nums[mid] < target and nums[r] >= target: l = mid + 1
else: r = mid -1
else:
if nums[mid] > target and nums[l] <= target: r = mid - 1
else: l = mid + 1
return -1
90. Subsets II
思路: 從combination 題的dfs裡得到靈感 要注意一定要 先sort
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
def dfs(i, path):
if path not in res:
res.append(path[:])
for _ in range(i,len(nums)):
path.append(nums[_])
dfs(_+1, path)
path.pop()
res, path = [], []
if len(nums) == 0: return res
elif len(nums) == 1: return [[],[nums[0]]]
dfs(0, path)
return res
380. Insert Delete GetRandom O(1)
思路: 設計題 用list.pop and index 來處理 remove
class RandomizedSet(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.temp = []
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val not in self.temp:
self.temp.append(val)
return True
else:
return False
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val not in self.temp: return False
else:
self.temp.pop(self.temp.index(val))
return True
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
if len(self.temp) == 1: return self.temp[0]
if len(self.temp) == 0: return self.temp
return self.temp[random.randint(0,len(self.temp)-1)]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
88. Merge Sorted Array
思路: 但是还有更简洁的方法，而且不用申请新变量。算法思想是：由于合并后nums1数组的大小必定是m+n，所以从最后面开始往前赋值，先比较nums1和nums2中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果nums1中所有的元素都比nums2小，那么前m个还是A原来的内容，没有改变。如果nums1中的数组比nums2大的，当nums1循环完了，nums2中还有元素没加入nums1，直接用个循环把nums2中所有的元素覆盖到nums1剩下的位置
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
total = m + n - 1
m -= 1
n -= 1
while m >= 0 and n >= 0:
if nums1[m] > nums2[n]:
nums1[total] = nums1[m]
m -= 1
total -= 1
else:
nums1[total] = nums2[n]
n -= 1
total -= 1
while n >= 0:
nums1[total] = nums2[n]
n -= 1
total -= 1
26. Remove Duplicates from Sorted Array
思路: 跟moving zero那題很像 都是宣告一個變數 如果當前的 i 不等於前一個 i 像則 交換 nums[count] = nums[i] 然後 count += 1
最後別忘了 return count += 1
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
n = len(nums)
if len(nums) <= 1: return len(nums)
for i in range(1,len(nums)):
if nums[i] != nums[i-1]:
count += 1
nums[count] = nums[i]
return count+1
80. Remove Duplicates from Sorted Array II
思路: 用list 來額外存結果, 可以出現兩次表示只有幾種情況可以append
- 當前 i 跟前一項不一樣 , 直接append
- 當前 i 跟前一項一樣 但不超過兩次, 直接append
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp = []
before = None
con = 1
for i in nums:
if i != before:
temp.append(i)
before = i
con = 1
elif con < 2:
temp.append(i)
con += 1
nums[:len(temp)] = temp
return len(temp)
69. Sqrt(x)
left, right = 0, x/2 + 1
while left <= right:
mid = (left + right) / 2
if mid * mid == x : return mid
elif mid * mid < x : left = mid + 1
elif mid * mid > x: right = mid - 1
return right
168. Excel Sheet Column Title
ref, res = [], []
for i in range(65, 91):
ref.append( str(unichr(i)) )
while n:
res.insert( 0, ref[(n-1)%26] )
n = (n-1) // 26
return "".join(res)
173. Binary Search Tree Iterator
# Definition for a binary tree node
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator(object):
def __init__(self, root):
self.stack = []
self.pushLeft(root)
# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.stack
# @return an integer, the next smallest number
def next(self):
top = self.stack.pop()
self.pushLeft(top.right)
return top.val
def pushLeft(self, node):
while node:
self.stack.append(node)
node = node.left
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
572. Subtree of Another Tree
思路: same tree 進階版, 如果s, t 的root 一樣 直接call same tree function
如果s, t 的root 不一樣 遞迴check s的左子樹或右子樹 是不是跟t 一樣
class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def dfs(p, q):
if not p and not q: return True
elif (p and not q) or (not p and q): return False
elif (p.val != q.val): return False
else:
return dfs(q.left, p.left) and dfs(q.right, p.right)
if not s: return False
if (dfs(s, t)): return True
return True if self.isSubtree(s.left, t) or self.isSubtree(s.right, t) else False
Second Try:
思路: dfs 遍歷 s 的左右子樹 如果s的某一節點 和t 是同樣的 return True else False
class Solution(object):
def dfs(self, s, t):
if not s : return False
if self.isSameTree(s, t): self.ans = True
self.dfs(s.left, t)
self.dfs(s.right, t)
def isSubtree(self, s, t):
self.ans = False
if not s: return False
self.dfs(s, t)
return self.ans
def isSameTree(self, p, q):
if p and not q: return False
if q and not p: return False
if not p and not q: return True
if p.val != q.val: return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
543. Diameter of Binary Tree
思路: 左右子樹深度和 + 1. 我们只要对每一个结点求出其左右子树深度之和，再加上1就可以更新结果res了。
class Solution(object):
def traverse(self, root):
if not root: return 0
left = self.traverse(root.left)
right = self.traverse(root.right)
self.ans = max(self.ans, left + right)
return max(left, right) + 1
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
self.traverse(root)
return self.ans
404. Sum of Left Leaves
思路: 遞迴尋找左葉節. 這裡的寫法很有趣
if l and (l.left or l.right) is None: 也等於 if l and l.left is None and r.right is None
class Solution(object):
def sumOfLeftLeaves(self, root):
ans = 0
if root:
l, r = root.left, root.right
if l and (l.left or l.right) is None:
ans += l.val
lv = self.sumOfLeftLeaves(l)
rv = self.sumOfLeftLeaves(r)
ans += lv + rv
return ans
200. Number of Islands
if not grid : return 0
m, n , res = len(grid), len(grid[0]), 0
def dfs(i, j):
grid[i][j] = 'P'
if i > 0 and grid[i-1][j] == '1': dfs(i-1, j)
if i < m - 1 and grid[i+1][j] == '1': dfs(i+1, j)
if j > 0 and grid[i][j-1] == '1': dfs(i, j-1)
if j < n - 1 and grid[i][j+1] == '1': dfs(i, j+1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i,j)
res += 1
return res
Second try:
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(x, y):
grid[x][y] = 'P'
dic = ((1,0), (-1,0),(0,1),(0,-1))
for _ in dic:
if 0 <= x + _[0] < len(grid) and 0 <= y + _[1] < len(grid[0]) and grid[x+_[0]][y+_[1]] == '1' :
dfs(x + _[0], y + _[1])
if not grid: return 0
m = len(grid)
n = len(grid[0])
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
res += 1
return res
133. Clone Graph
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
def dfs(node, mapp):
# check if node exist in the map
if node in mapp: return mapp[node]
# if node not in the map, copy it into the map
output = UndirectedGraphNode(node.label)
mapp[node] = output
# handle the neighbor
for i in node.neighbors:
mapp[node].neighbors.append( dfs(i, mapp) )
# don't forget to return
return output
if not node: return node
return dfs(node, {})
278. First Bad Version
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: return 1
start, end = 1, n
while start < end:
mid = (start + end) / 2
if isBadVersion(mid) == True:
end = mid
else:
start = mid + 1
return end
Second Try:
l, r = 1 , n
while l < r:
mid = (l+r) / 2
if isBadVersion(mid): r = mid
else: l = mid + 1
return r
461. Hamming Distance
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x ^ y).count('1')
477. Total Hamming Distance
class Solution(object):
def totalHammingDistance(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
mask = 1
for i in range(32):
zero, one = 0, 0
for j in nums:
if j & mask:
one += 1
else:
zero += 1
ans += zero * one
mask = mask << 1
return ans
67. Add Binary
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
al, bl = len(a), len(b)
flag = 0
res = []
i = 0
a = a[::-1]
b = b[::-1]
while True:
if i < al and i < bl :
res.insert(0, str(int(a[i]) + int(b[i])) )
elif i < al and i >= bl :
res.insert(0, a[i] )
elif i >= al and i < bl :
print b[i]
res.insert(0, b[i] )
else:
break
i += 1
print res
# one shot handle overbit
for i in range(len(res)-1, -1, -1):
if int(res[i]) + flag > 1:
res[i] = str((int(res[i]) + flag) % 2)
flag = 1
else:
res[i] = str((int(res[i]) + flag))
flag = 0
if flag: res.insert(0,'1')
return "".join(res)
Second try: 寫一個轉換成10進位的函數 把數字都換成10進位相加後 再換成2進位
def strBintoint(s):
res = 0
index = 0
for i in range(len(s)-1,-1,-1):
#print int(s[i]) * (2 ** index)
res += int(s[i]) * (2 ** index)
index += 1
return res
ab = strBintoint(a)
bb = strBintoint(b)
res = bin(ab + bb)
return res[2:]
125. Valid Palindrome
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
# handle corner case
if len(s) <= 1 : return True
# put s to lower
s = s.lower()
# create dictory
dic = {}
for i in range(65, 91):
temp = str(unichr(i)).lower()
dic[temp] = temp
for i in range(0, 10):
dic[str(i)] = str(i)
# filter out non-char
filt = []
for j in s:
if j in dic: filt.append(j)
s = "".join(filt)
# check if s is palindrome
start, end = 0, len(s)-1
while start <= end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
49. Group Anagrams
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
res, dic = [], {}
for i in strs:
temp = "".join(sorted(i))
if temp in dic:
dic[temp].append(i)
else:
dic[temp] = [i]
for j in dic:
res.append(dic[j])
return res
25. Reverse Nodes in k-Group
dummy = p = ListNode(0)
dummy.next = head
n = 0
while p.next: # find how many nodes we have in total
p = p.next
n += 1
pre, p = dummy, dummy.next
for j in range(n//k): # we need n//k times reverse processes
for i in range(k-1):
print pre.val
print p.val
pre.next, p.next, pre.next.next = p.next, p.next.next, pre.next
print
pre, p = p, p.next # set new "pre" and "p" node
return dummy.next
301. Remove Invalid Parentheses
思路: BFS
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def isvalid(s):
ans = 0
for c in s:
ans += {'(': 1, ')': -1}.get(c, 0)
if ans < 0: return False
return ans == 0
res, visited, q, done = [], set([s]), [], False
#visited[s] = True
q.append(s)
while q:
t = q[0]
del q[0]
if isvalid(t):
res.append(t)
done = True
if done: continue
for i in range(len(t)):
if t[i] not in {'(', ')'}: continue
ne = t[:i] + t[i+1:]
if ne not in visited:
visited.add(ne)
q.append(ne)
return res
DFS:
class Solution(object):
def check(self, s):
c = 0
for ch in s:
if ch == '(': c += 1
if ch == ')': c -= 1
if c < 0: return False
return c == 0
def dfs(self, s, d_l, d_r, res, hist):
if d_l == 0 and d_r == 0 :
if not s in res and self.check(s):
res[s] = True
elif s == "":
return
else:
for i in range(len(s)):
if not s[0:i] + s[i+1:] in hist:
hist[s[0:i] + s[i+1:]] = True
if s[i] == '(' and d_l > 0:
self.dfs(s[0:i] + s[i+1:], d_l-1, d_r, res, hist)
if s[i] == ')' and d_r > 0:
self.dfs(s[0:i] + s[i+1:], d_l, d_r-1, res, hist)
def removeInvalidParentheses(self, s):
res = {}
hist = {}
d_r = 0 # number of '(' to be deleted
d_l = 0 # number of ')' to be deleted
for ch in s:
if ch == '(':
d_l += 1
if ch == ')':
if d_l > 0:
d_l -= 1
else:
d_r += 1
self.dfs(s, d_l, d_r, res, hist)
return res.keys()
76. Minimum Window Substring
思路: 雙指針 一開始不斷往後移動尾指針
直到window 條件符合, 接者開始收縮頭指針
如果當前的window小於原來的window 就把他記起來
class Solution(object):
def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
if need[c] > 0:
missing -= 1
need[c] -= 1
# find the windows
if not missing:
# shrink the window, keep move head
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
# find the small window, save it
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
79. Word Search
思路: 對board裡的每個字母 做dfs
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
def find(i, j, word, idx):
if idx==len(word): return True
if 0<=i<len(board) and 0<=j<len(board[0]) and board[i][j]==word[idx]:
temp, board[i][j] = board[i][j], '0'
direction = ((1,0),(-1,0),(0,1),(0,-1))
for x, y in direction:
if find(i+x,j+y,word,idx+1): return True
board[i][j]=temp
return False
for i in range(len(board)):
for j in range(len(board[0])):
if find(i,j,word,0):
return True
return False
Replace %20
in-place replace all "%20" in a string to a space, ex:
abc%20def -> abc def-google 1point3acres
abc%20%20%2 -> abc %2.
思路: O(n), n = len(s)
class Solution(object):
def replace(self, s):
y, write = 0, []
for i in range(0, len(s)-3):
if s[i:i+3] == "%20":
write.append(i)
write = write[::-1]
for j in write:
s = s[:j] + " " + s[j+3:]
return s
ob = Solution()
print ob.replace("abc%20%20%2")
62. Unique Paths
思路: dp, 想法跟爬樓梯很像. 一個是一次只能走一格或兩格 另一個是 一次可以只能往右 或 往下
維護一個dp 一層一層掃
Your input
3
4
4
Your stdout
[1, 2, 1, 1]
[1, 2, 3, 1]
[1, 2, 3, 4]
[1, 3, 3, 4]
[1, 3, 6, 4]
[1, 3, 6, 10]
Your answer
10
Expected answer
10
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [1] * n
for i in range(1,m):
for j in range(1,n):
dp[j] += dp[j-1]
print dp
return dp[n-1]
63. Unique Paths II
思路: 也是用一維array 去掃, 遇到 grid[i][j] 等於 1 的時候就把 dp[j] 設為 0
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not obstacleGrid or not obstacleGrid[0]: return 0
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [0] * n
dp[0] = 1
if obstacleGrid[0][0] == 1: return 0
for i in range(m):
for j in range(n):
if (obstacleGrid[i][j] == 1): dp[j] = 0
elif j > 0: dp[j] += dp[j-1]
return dp[n-1]
367. Valid Perfect Square
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
x = 1
while x * x <= num:
if x * x == num: return True
x += 1
return False
98. Validate Binary Search Tree
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# do inorder
def dfs(node):
if not node: return
dfs(node.left)
res.append(node.val)
dfs(node.right)
res = []
dfs(root)
# cheak result
if len(res) == 0 or len(res) == 1: return True
for i in range(1,len(res)):
if res[i-1] >= res[i]: return False
return True
234. Palindrome Linked List
思路: 雙指針 後半段反轉 之後比較前後 兩段
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head: return True
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# reverse
node = slow.next
while node and node.next:
ne = node.next
node.next = ne.next
ne.next = slow.next
slow.next = ne
# print second half
while slow.next:
slow = slow.next
if slow.val != head.val: return False
head = head.next
return True
20. Valid Parentheses
思路: stack
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
left, right = ['(','{','['], [')','}',']']
stack = []
for i in s:
if i in left:
stack.append(i)
if i in right:
if stack and stack[-1] == left[right.index(i)]: stack.pop()
else: return False
return len(stack) == 0
1. Two Sum
if not nums: return []
res, dic = [], {}
for i in range(len(nums)):
if target - nums[i] in dic:
res.append(dic[target - nums[i]])
res.append(i)
else:
dic[nums[i]] = i
return res
13. Roman to Integer
思路: 關鍵規則很簡單 判斷 s[i] 和 s[i-1].
如果s[i] <= s[i-1] : sum += s[i-1]
否則 sum -= s[i-1]
最後要記得sum要加上 s[-1]
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
ROMAN = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
if s == "":
return 0
index = len(s) - 2
sum = ROMAN[s[-1]]
while index >= 0:
if ROMAN[s[index]] < ROMAN[s[index + 1]]:
sum -= ROMAN[s[index]]
else:
sum += ROMAN[s[index]]
index -= 1
return sum
273. Integer to English Words
思路: 遞迴 一層一層撥皮剝下去, 小於一千的都算好處理.
class Solution(object):
def numberToWords(self, num):
"""
:type num: int
:rtype: str
"""
to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
def words(n):
if n < 20:
return to19[n-1:n]
if n < 100:
return [tens[n/10-2]] + words(n%10)
if n < 1000:
return [to19[n/100-1]] + ['Hundred'] + words(n%100)
for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
if n < 1000**(p+1):
return words(n/1000**p) + [w] + words(n%1000**p)
return ' '.join(words(num)) or 'Zero'
Flatten nested array
a = [[1]], [[[5]]]
def flatten(arr):
res = []
for i in range(len(arr)):
if not isinstance(arr[i], list) :
res.append(arr[i])
else:
res.extend(flatten(arr[i]))
return res
print flatten(a)
309. Best Time to Buy and Sell Stock with Cooldown
思路:
这题比Best Time to Buy and Sell Stock II多了一个cooldown的条件，就变得麻烦多了。这题是一个多阶段优化问题，首先范围缩小到广搜，贪心或者动规。因为每步之间互相牵连，贪心显然不行。广搜固然可以，不过是O(2^n)复杂度，所以我们先考虑用动规。
对于每一天，有三种动作，buy, sell, cooldown, sell 和 cooldown 可以合并成一种状态，因为手里最终没有股票。最终需要的结果是 sell，即手里股票卖了获得最大利润。我们可以用两个数组来记录当前持股和未持股的状态，令sell[i] 表示第i天未持股时，获得的最大利润，buy[i]表示第i天持有股票时，获得的最大利润。
对于sell[i]，最大利润有两种可能，一是今天没动作跟昨天未持股状态一样，二是今天卖了股票，所以状态转移方程如下：
sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}
对于buy[i]，最大利润有两种可能，一是今天没动作跟昨天持股状态一样，二是前天卖了股票，今天买了股票，因为 cooldown 只能隔天交易，所以今天买股票要追溯到前天的状态。状态转移方程如下：
buy[i] = max{buy[i-1], sell[i-2] - prices[i]}
最终我们要求的结果是sell[n - 1]，表示最后一天结束时，手里没有股票时的最大利润。
这个算法的空间复杂度是O(n)，不过由于sell[i]仅仅依赖前一项，buy[i]仅仅依赖前两项，所以可以优化到O(1)
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
sell = [0] * len(prices)
buy = [0] * len(prices)
buy[0] = -prices[0]
for i in range(1,len(prices)):
sell[i] = max( sell[i-1], buy[i-1] + prices[i] )
buy[i] = max( buy[i-1], sell[i-2] - prices[i] )
return sell[-1]
173. Binary Search Tree Iterator
思路:
题目大意：
实现一个二叉搜索树（BST）的迭代器。你的迭代器会使用BST的根节点初始化。
调用next()会返回BST中下一个最小的数字。
注意：next()和hasNext()应该满足平均O(1)时间复杂度和O(h)空间复杂度，其中h是树的高度。
解题思路：
维护一个栈，从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。
调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。
class BSTIterator(object):
def __init__(self, root):
self.q = []
self.pushLeft(root)
def hasNext(self):
return self.q
def next(self):
temp = self.q.pop()
self.pushLeft(temp.right)
return temp.val
def pushLeft(self, node):
while node:
self.q.append(node)
node = node.left
334. Increasing Triplet Subsequence
思路: 紀錄 最小點 a , 之後 b 如果match 就是True, else False
class Solution(object):
def increasingTriplet(self, nums):
a, b = sys.maxint, sys.maxint
if len(nums) < 2: return False
for i in range(len(nums)):
if nums[i] <= a:
a = nums[i]
elif nums[i] <= b:
b = nums[i]
else:
return True
return False
留言
張貼留言