这一章主要想要总结几个经典的算法或者数据结构，以及他们对应的leetcode题目。通过题目来理解算法能解决什么样的问题才是最稳妥的。
1 Topo Sort: 代表题型course schedul II
import collections
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
if not numCourses:
return []
pre = collections.defaultdict(set)
nex = collections.defaultdict(set)
for a, b in prerequisites:
pre[a].add(b)
nex[b].add(a)
stack = [key for key in range(numCourses) if key not in pre]
order = []
while stack:
cur = stack.pop()
order.append(cur)
if cur in nex:
for child in nex[cur]:
pre[child].remove(cur)
if not pre[child]:
stack.append(child)
return order if len(order)==numCourses else []
s = Solution()
print s.findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
import collections
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
if not tickets:
return []
fro = collections.defaultdict(list)
nex = collections.defaultdict(list)
for i, j in tickets:
fro[j].append(i)
nex[i].append(j)
for key in nex:
nex[key].sort()
path = ['JFK']
self.helper('JFK', nex, path, len(tickets)+1)
return path
def helper(self, cur, nex, path, length):
if len(path) == length:
return True
for i in range(len(nex[cur])):
tmp = nex[cur].pop(i)
path.append(tmp)
if self.helper(tmp, nex, path, length):
return True
path.pop()
nex[cur].insert(i, tmp)
return False
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
s = Solution()
print s.findItinerary(tickets)
2 Union find 305 Number of Islands II
class UF():
def __init__(self):
self.cnt = 0
self.dic = {}
def add(self, i, j):
if (i, j) not in self.dic:
self.dic[(i, j)] = (i, j)
self.cnt += 1
def find(self, p):
anc = self.dic[p]
while anc != self.dic[anc]:
anc = self.dic[self.dic[anc]]
return anc
def unite(self, p, q):
p_anc, q_anc = self.find(p), self.find(q)
if p_anc==q_anc:
return
else:
self.cnt -= 1
self.dic[p_anc] = self.dic[q_anc]
class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
uf = UF()
res = []
for i, j in positions:
uf.add(i, j)
for d, p in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
x, y = i+d, j+p
if (x, y) in uf.dic:
uf.unite((i, j), (x, y))
res.append(uf.cnt)
return res
p = [[0,1],[1,2],[2,1],[1,0],[0,2],[0,0],[1,1]]
s = Solution()
print s.numIslands2(3, 3, p)
3 Trie + DFS Word search II
class Node():
def __init__(self):
self.isWord = False
self.children = {}
def __repr__(self):
return repr(self.children)
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
if not board or not board[0]:
return []
root = Node()
for w in words:
cur = root
for c in w:
if c not in cur.children:
cur.children[c] = Node()
cur = cur.children[c]
cur.isWord = True
res = []
for i in range(len(board)):
for j in range(len(board[0])):
c = board[i][j]
if c in root.children:
visited = set()
visited.add((i, j))
self.search(i, j, board, root.children[c], [c], res, visited)
return res
def search(self, i, j, board, cur, path, res, visited):
if cur.isWord:
res.append(''.join(path))
cur.isWord = False
for d, p in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
x, y = i+d, j+p
if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] in cur.children:
if (x, y) not in visited:
visited.add((x, y))
self.search(x, y, board, cur.children[board[x][y]], path + [board[x][y]], res, visited)
visited.remove((x, y))
words = ["aba","baa","bab","aaab","aaa","aaaa","aaba"]
board = [["a","b"],["a","a"]]
s = Solution()
print s.findWords(board, words)
4 DFS + DP Word break II
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
res = []
wordDict = set(wordDict)
self.dfs(s, [], res, wordDict)
return res
def dfs(self, s, path, res, wordDict):
if not s:
res.append(path)
return
for i in range(1, len(s)+1):
if s[:i] in wordDict:
self.dfs(s[i:], path + [s[:i]], res, wordDict)
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
so = Solution()
print so.wordBreak(s, wordDict)
再用dp来写一遍。
import collections
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
self.memo = collections.defaultdict(list)
self.dfs(s, 0, len(s), set(wordDict))
return self.memo[(0, len(s))]
def dfs(self, s, i, j, wordDict):
if (i, j) not in self.memo:
if s[i:j] in wordDict:
self.memo[(i, j)] += [s[i:j]]
for end in range(i+1, j):
if s[i: end] in wordDict:
tails = self.dfs(s, end, j, wordDict)
self.memo[(i, j)] += [s[i: end] + ' '+ tail for tail in tails]
return self.memo[(i, j)]
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
so = Solution()
for i in range(1):
print so.wordBreak(s, wordDict)
Priority queue Skyline Problem
import heapq
START = 0
END = 1
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
events = []
dic = {}
for s, e, h in buildings:
events.append((s, START, h))
events.append((e, END, h))
dic[(e, END, h)] = (s, START, h)
events.sort()
pq = [(0, 0)]
res = []
cur = 0
for e in events:
if e[1] == START:
heapq.heappush(pq, (-e[2], e[0]))
if pq[0][0]!=-cur:
cur = -pq[0][0]
res.append((e[0], cur))
else:
tuple_to_remove = (-dic[e][2], dic[e][0])
index = pq.index(tuple_to_remove)
pq.remove(pq[index])
heapq.heapify(pq)
if pq[0][0]!=-cur:
cur = -pq[0][0]
res.append((e[0], cur))
return res
s = Solution()
print s.getSkyline([ [2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8] ])
# [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].