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的含义就是找到某个节点的最终的root
# 在这里，因为用index作为map的key
# 对于每一条边，每加入一个边，就检查两个点，e[0]为root，e[1]为child
# 看看这两个点的最终father是谁，然后再把这两个最终father联系起来
for e in edges:
self.union(m, e[0], e[1])
# 用一个set记录所有的最终father的数量
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构造一个图的表示形式。
for x, y in edges:
g[x].append(y)
g[y].append(x)
ret = 0
for i in xrange(n): # 对于每一个节点，如果没有被访问过，就对其进行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也类似，也要创造出图的表示方式
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过，则创建一个新的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)的复杂度，O(1)的space的话，需要用到quick select, 但是接下来怎么做实在是太复杂了，感觉意义不是很大
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一个#进去。循环这么做就可以了。体力耗尽就是心浮气躁。先休息一下再做。
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的已经满足了，解法2只能背下来，真正面试时候属于知道就知道，不知道就拉倒的解法。。。
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] 出发，用了第几张票
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题，推导公式如下: if i < 2**(k+1): dp[i] = dp[i-2**k] + 1 elif i == 2**(k+1): k += 1, dp[i] = 1
