1/20, BFS, Search
BFS is good at finding the Shortest path and topological sort
BFS用Queue来实现对有向或无向图的访问，
General template using queue
1)add initial node to the queue.
2)pop a node, and for each neighbor of it, check whether the neighbor/out node can be visited later.
3)if true, append to the queue, continue.
Word Ladder
- 无向图
因为要找的是最短路线，所以用BFS而不是DFS。
时间复杂度O(L^2 * 25), L is the length of each word and the size of the dict。
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(); // mark the unvisited string
for (String s : wordList) {
set.add(s);
}
Deque<String> queue = new LinkedList<>();
queue.offer(beginWord);
set.remove(beginWord);
int len = 0;
while (!queue.isEmpty()) {
int size = queue.size();
len++;
for (int k = 0; k < size; ++k) {
String s = queue.poll();
char[] ch = s.toCharArray();
for (int i = 0; i < s.length(); ++i) {
char cur = s.charAt(i);
for (char c = 'a'; c <= 'z'; ++c) {
ch[i] = c;
String newStr = String.valueOf(ch);
if (newStr.equals(s)) continue; // skip itself
if (newStr.equals(endWord) && set.contains(newStr)) return len + 1; // found the target word, return len;
if (!set.contains(newStr)) continue; // cannot find the next word
set.remove(newStr);
queue.offer(newStr);
}
ch[i] = cur;
}
}
}
return 0;
}
}
在queue里存入tuple，每个tuple包含当前的word和到这个word所用的step。每次循环中，queue只pop一个word，但可能被push进去若干个next words。使用queue的好处是，每次pop出的word都会是step最少的。
找到一个单词的下一个单词，加入queue后，要从dict里删除，因为不删除的话，会造成死循环。删除对最短路径没有影响，因为就算之后有其他单词能转化得到它，也不会比当前得到的路径短。
1/5刷又没remove，一定要做到bug free啊。
Shortest Path (HeartFlow OA Question)
Given a directed graph G, two nodes S and E, write a program that finds the shortest path between S and E(starting on S and ending on E). Assume there is a unique shortest path for each case.
- 有向图
#edges = {"A":["B"], "B":[]}
#start = "A"
#end = "B"
#output = ["A", "B"]
#edges = {"A":["B", "C"], "B":["D"], "C":["E"], "D":["E"], "E":["F"]}
#start = "A"
#end = "F"
#output = ['A', 'C', 'E', 'F']
#edges = {"A":["B"], "M":[]}
#start = "A"
#end = "M"
def shortestPath(start, end, edges):
from collections import deque
q = deque([(start, [])])
while q:
top, path = q.popleft()
if top == end:
path += [top]
return path
try:
for node in edges[top]:
q.append((node, path+[top]))
except KeyError:
return None
Perfect Square
The least number of perfect square numbers which sum to n can be regarded as the Shortest-path problem.
class Solution {
public int numSquares(int n) {
Deque<Integer> queue = new LinkedList<>();
queue.offer(0);
int count = 0;
Set<Integer> visited = new HashSet<>();
visited.add(0);
while (!queue.isEmpty()) {
int size = queue.size();
for (int sz = 0; sz < size; ++sz) {
int cur = queue.poll();
if (cur > n) {
continue;
}
if (cur == n) {
return count;
}
for (int i = 1; cur + i * i <= n; ++i) {
if (visited.contains(cur + i * i)) {
continue;
}
queue.offer(cur + i * i);
visited.add(cur + i * i);
}
}
count++;
}
return -1;
}
}
or we can solve the problem using DP
state definition
- perfect square numbers sum
state function
- state[i], min number of perfect square numbers sum to i
goal state
- state[n]
base case
- state[0] = 0
state transition
- min(state[i - j * j] + 1) = state[i]
filling direction
- i, j increasing
class Solution {
public int numSquares(int n) {
int[] state = new int[n + 1];
for (int i = 1; i <= n; ++i) {
state[i] = i; // initalize to all 1...
for (int j = 1; j <= i; j++) {
if (j * j > i) {
break;
}
state[i] = Math.min(state[i - j*j] + 1, state[i]);
}
}
return state[n];
}
}
12/07复习补充
Clone Graph
- 无向图的复制
BFS，搜索当前node的所有neighbors。
用个hashtable存访问过的node，{node:copied_node}。
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def __init__(self):
self.dict = {}
def cloneGraph(self, node):
if not node:
return None
from collections import deque
queue = deque([node])
copied_node = UndirectedGraphNode(node.label)
self.dict[node] = copied_node
while queue:
cur = queue.popleft()
copied_cur = self.dict[cur]
for n in cur.neighbors:
if not n in self.dict:
copied_n = UndirectedGraphNode(n.label)
copied_cur.neighbors.append(copied_n)
self.dict[n] = copied_n
queue.append(n)
else:
copied_n = self.dict[n]
copied_cur.neighbors.append(copied_n)
return copied_node
12/29复习注，是先把第一个node加入queue，每次queue出列一个node，然后检查这个node的所有neighbors，如果没访问过，就update 新节点的neighbors，还要把neighbor节点加入queue，并且update hashtable。
1/5复习注，用到hashtable和queue。hashtable两个作用，一是添加访问过的节点，这样的话就能在queue里添加未访问的节点。二是mapper出新节点。
Course Schedule
- 有向图
利用入度和出度，adjacency list。
思路是由入度为0的节点开始，通过adjacency list来查找它出去的neighbors，并且去减掉neighbors的入度。当入度减为0时，就表示这个节点(课程)可以抵达，并累加课程数。edge case要判断有无环，有环的话queue是empty，返回false。
class Solution:
def canFinish(self, numCourses, prerequisites):
edges = {i: [] for i in range(numCourses)} ## out adjacency list {precourse:[courses]}
degrees = [0 for i in range(numCourses)] ## a list of nodes' in degree
for i, j in prerequisites:
edges[j].append(i)
degrees[i] += 1
import collections
queue, count = collections.deque(), 0
for i in range(numCourses):
if degrees[i] == 0: ## add nodes with 0 in-degree to a queue
queue.append(i)
while queue:
node = queue.popleft()
count += 1
for x in edges[node]: ## scan the 0 in-degree node's out neighbors
degrees[x] -= 1 ## decrease the in-degree of neighbors by 1
if degrees[x] == 0:
queue.append(x)
return count == numCourses
2/14补充，
Course Schedule II (Order Dependency)
Amazon的九道OA之一，跟上题的思路很接近。不同之处是，order的排序是根据order name，而不是order本身。而最后的输出是一个list of orders，所以需要用到dict{ordername:order}，根据排好的ordername来输出order。另外需要两个dict，一个记录入度{ordername:num_count}，一个出度{ordername:[ordername list]}。
时间复杂度是O(n)，因为每个order只被push/pop一次。
class Order:
def __init__(self, ordername):
self.orderName = ordername
class OrderDependency:
def __init__(self, cur, pre):
self.cur = cur
self.pre = pre
class Solution:
def dependency(self, orderDependencies):
res = []
inmap, outmap, recordmap = {}, {}, {}
for orderDp in orderDependencies:
cur = orderDp.cur
pre = orderDp.pre
curName = cur.orderName
preName = pre.orderName
if not curName in recordmap:
recordmap[curName] = orderDp.cur
if not preName in recordmap:
recordmap[preName] = orderDp.pre
if not preName in inmap:
inmap[preName] = 0
if curName in inmap:
inmap[curName] += 1
else:
inmap[curName] = 1
if not preName in outmap:
outmap[preName] = []
outmap[preName].append(curName)
if not curName in outmap:
outmap[curName] = [] ## pay attention, each order should have an out list
from collections import deque
queue = deque([])
for name in inmap:
if inmap[name] == 0:
queue.append(name)
while queue:
top = queue.popleft()
res.append(recordmap[top])
for out in outmap[top]:
inmap[out] -= 1
if inmap[out] == 0:
queue.append(out)
return res
## test case
o0 = Order('泡面')
o1 = Order('热水')
o2 = Order('Z')
o3 = Order('M')
o4 = Order('O')
o5 = Order('A')
o6 = Order('N')
o7 = Order('A')
od0 = OrderDependency(o7, o0)
od1 = OrderDependency(o3, o0)
od2 = OrderDependency(o5, o3)
od3 = OrderDependency(o2, o1)
od4 = OrderDependency(o6, o4)
od5 = OrderDependency(o4, o2)
dependencies_list = [od1, od3, od2, od4, od0, od5]
s = Solution()
res = s.dependency(dependencies_list)
for od in res:
print(od.orderName) ## 泡面->热水->M->Z->A->O->N
和上面的solution区别在inmap和outmap的初始化方式，这里不用考虑course存不存在。
class Solution:
def findOrder(self, numCourses, prerequisites):
inmap = {i: 0 for i in range(numCourses)} ## or use a list to save some place
outmap = {i: [] for i in range(numCourses)}
res = []
for cur, pre in prerequisites:
inmap[cur] += 1
outmap[pre].append(cur)
from collections import deque
queue = deque([])
for i in range(numCourses):
if inmap[i] == 0:
queue.append(i)
while queue:
top = queue.popleft()
res.append(top)
for n in outmap[top]:
inmap[n] -= 1
if inmap[n] == 0:
queue.append(n)
if numCourses == len(res): ## pay attention
return res
return []
Search Graph Nodes
- 无向图
用queue找到距离给的点最短的点，利用给的hashtable，找值并且删掉访问过的点，防止无限循环。
class Solution:
def searchNode(self, graph, values, node, target):
from collections import deque
q = deque([node])
if values[node] == target: ## pay attention, check the node itself first
return node
del values[node] ## remove the node visited
while q:
top = q.popleft()
for n in top.neighbors: ## check each neighbor of top has been visited or not
if n in values: ## if not visited yet
if values[n] == target:
return n
del values[n] ## remove
q.append(n)
return None
Topological Sorting
- 有向图
输入为一个list of nodes，先要通过它得到入度。
class Solution:
def topSort(self, graph):
inmap = {} ## 用dict保存 {节点:入度}
for node in graph:
inmap[node] = 0
for i in graph:
for j in i.neighbors:
inmap[j] += 1
from collections import deque
q = deque([])
for node in graph:
if inmap[node] == 0:
q.append(node)
res = []
while q:
top = q.popleft()
res.append(top)
for n in top.neighbors: ## 已知每个节点的neighbors
inmap[n] -= 1
if inmap[n] == 0:
q.append(n)
return res
这道题的另一种解法是用DFS，区别是迭代和用queue储存可以访问的节点，相比之下BFS的方法能够减少function calls。
Word Ladder II
上题的follow up，要找所有最短的路径，BFS+DFS。