323. Number of Connected Components in an Undirected Graph: 這題算是比較典型的圖的問題圈盔，有三種解法最筒，bfs笤喳，dfs弯予，union-find：
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
m = range(n)
res = set()
# union-find的含義就是找到某個節(jié)點的最終的root
# 在這里肛跌，因為用index作為map的key
# 對于每一條邊，每加入一個邊钢猛，就檢查兩個點，e[0]為root轩缤，e[1]為child
# 看看這兩個點的最終father是誰命迈，然后再把這兩個最終father聯(lián)系起來
for e in edges:
self.union(m, e[0], e[1])
# 用一個set記錄所有的最終father的數(shù)量
for i in m:
res.add(self.find(m, i))
return len(res)
def find(self, m, node):
if node == m[node]:
return node
return self.find(m, m[node])
def union(self, m, node1, node2):
father1 = self.find(m, node1)
father2 = self.find(m, node2)
if father1 != father2:
m[father2] = father1
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
visited = [0] * n
g = {x:[] for x in xrange(n)} # g[n] 表示n 和哪些值相連接, 其實就是用list和map構(gòu)造一個圖的表示形式。
for x, y in edges:
g[x].append(y)
g[y].append(x)
ret = 0
for i in xrange(n): # 對于每一個節(jié)點火的，如果沒有被訪問過壶愤，就對其進行dfs
if visited[i] == 0:
self.dfs(i, g, visited) # 每遍歷一次連接，就在ret上加一
ret += 1
return ret
def dfs(self, n, g, visited):
if visited[n]:
return
visited[n] = 1
for x in g[n]:
self.dfs(x, g, visited)
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
# bfs也類似馏鹤，也要創(chuàng)造出圖的表示方式
g = {x:[] for x in xrange(n)}
visited = [0 for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
ret = 0
for i in xrange(n):
if visited[i] == 0:
# 如果沒有被visited過征椒，則創(chuàng)建一個新的queue
queue = [i]
ret += 1
while queue:
j = queue.pop(0)
visited[j] = 1
for k in g[j]:
if visited[k] == 0:
queue += [k]
return ret
324. Wiggle Sort II: sort一下再排序就好了，但是如果要O(N)的復(fù)雜度湃累，O(1)的space的話勃救，需要用到quick select, 但是接下來怎么做實在是太復(fù)雜了碍讨，感覺意義不是很大
325. Maximum Size Subarray Sum Equals k: 利用前綴和，雖然自己的解法AC了蒙秒，但是有比較好的解法勃黍，在loop過程中直接計算前綴和，然后利用hash來記錄
328. Odd Even Linked List： 用一個even和一個odd來分別記錄晕讲，然后拼起來就行了
331. Verify Preorder Serialization of a Binary Tree：沒做出來覆获，感覺體力被那道wiggle sort耗盡了，這題的思路其實也不難瓢省，就是碰到兩個#就把它們從stack pop出來弄息，再pop出來它們的parent并且push一個#進去。循環(huán)這么做就可以了勤婚。體力耗盡就是心浮氣躁疑枯。先休息一下再做。
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
stack = []
top = -1
preorder = preorder.split(',')
for s in preorder:
stack.append(s)
top += 1
while(self.endsWithTwoHashes(stack,top)):
h = stack.pop()
top -= 1
h = stack.pop()
top -= 1
if top < 0:
return False
h = stack.pop()
stack.append('#')
if len(stack) == 1:
if stack[0] == '#':
return True
return False
def endsWithTwoHashes(self,stack,top):
if top<1:
return False
if stack[top]=='#' and stack[top-1]=='#':
return True
return False
332. Reconstruct Itinerary: 休息了一下蛔六，沉下心來荆永，用backtracking作出一個TLE版本，還可以接受国章。不過DFS的正確打開方式如解法2具钥，詳細解釋：https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c， 我覺得我能做出TLE的已經(jīng)滿足了液兽，解法2只能背下來骂删，真正面試時候?qū)儆谥谰椭溃恢谰屠沟慕夥ㄋ膯Ｄ怠！?/p>
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
m = {}
for i in range(len(tickets)):
m[tickets[i][0]] = m.get(tickets[i][0], [])+ [i] # 從這個t[0] 出發(fā)柑晒，用了第幾張票
used = [False for _ in range(len(tickets))]
self.res = []
self.dfs(m, ["JFK"], used, tickets)
return self.res
def dfs(self, m, cur, used, tickets):
if len(cur) == len(tickets)+1:
if not self.res or self.res > cur:
self.res = cur[:]
return
for c in m.get(cur[-1], []):
if used[c]:
continue
used[c] = True
cur.append(tickets[c][1])
self.dfs(m, cur, used, tickets)
cur.pop()
used[c] = False
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
# build graph
graph = {}
for t in tickets:
graph[t[0]] = graph.get(t[0], []) + [t[1]]
for k, v in graph.iteritems():
graph[k] = sorted(v)
departure = "JFK"
path = []
self.dfs(graph, departure, path)
return path
def dfs(self, graph, departure, path):
arrivals = graph.get(departure)
while arrivals:
self.dfs(graph, arrivals.pop(0), path)
path.insert(0, departure)
333. Largest BST Subtree: 還算是簡單的divide and conquer
334. Increasing Triplet Subsequence：可以記錄前兩個最小值欧瘪，或者記錄一下兩位上升序列中的后一個值。
337. House Robber III：divide and conquer匙赞，返回值分成with root和without root兩種情況就可以了
338. Counting Bits：一道dp題佛掖，推導(dǎo)公式如下: if i < 2**(k+1): dp[i] = dp[i-2**k] + 1 elif i == 2**(k+1): k += 1, dp[i] = 1
