骨骼清奇BFS+DSU
Catalog:
LC 三九九 Evaluate Division
LC 六八四 六八五及其变种（Tree删除额外边）
LC 803 Bricks Falling When Hit
LC 505 The Maze II
todo:
[Uber] LC 286 Walls and Gates
LC三九九及其变种（汇率）Evaluate Division
频率：21
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction. . If the answer does not exist, return -1.0.
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
分析：首先构建一个graph（注意正反相除，自身相除），如果A和B,C有关系，那么B和C就可以利用A作为桥梁进行相除（换汇）。可以DFS，也可以把所有可能的通道都建立起来。
#Runtime: 68 ms
class Solution:
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
graph = collections.defaultdict(dict)
for (n1, n2), val in zip(equations, values):
graph[n1][n1] = graph[n2][n2] = 1.0
graph[n1][n2] = val
graph[n2][n1] = 1 / val
for k in graph:
for i in graph[k]:
for j in graph[k]:
graph[i][j] = graph[i][k] * graph[k][j]
return [graph[n1].get(n2, -1.0) for n1, n2 in queries]
迭代的方式做BFS, 36ms!
class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
graph = collections.defaultdict(dict)
for (n1, n2), val in zip(equations, values):
#graph[n1][n1] = graph[n2][n2] = 1.0
graph[n1][n2] = val
graph[n2][n1] = 1 / val
def getVal(st, en):
visited = set()
q = [(node, val) for node, val in graph[st].items()]
while q:
nextl = set()
while q:
node, val= q.pop(0)
if node == en:
return val
visited.add(node)
for nnode, nval in graph[node].items():
if nnode not in visited:
nextl.add((nnode, nval*val))
q = list(nextl)
return -1
res = []
for x, y in queries:
if x not in graph or y not in graph:
res.append(-1.0)
elif x == y:
res.append(1.0)
else:
res.append(getVal(x, y))
return res
LC六八四 六八五及其变种（Tree删除额外边）
频率：10
A tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added.
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
分析：Union Find or DFS
the directed graph follow up - [Redundant Connection II].
- Bus Routes [Freq:5]
what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Key: BFS, Memo.
Corner Case: start at intersection. start and end in the same route/stop.
class Solution(object):
def numBusesToDestination(self, routes, S, T):
if S == T: return 0
routes = map(set, routes)
graph = collections.defaultdict(set)
for i, r1 in enumerate(routes):
for j in range(i+1, len(routes)):
r2 = routes[j]
if any(stop in r2 for stop in r1):
graph[i].add(j)
graph[j].add(i)
seen, targets = set(), set()
for node, route in enumerate(routes):
if S in route: seen.add(node)
if T in route: targets.add(node)
queue = [(node, 1) for node in seen]
for node, depth in queue:
if node in targets: return depth
for nei in graph[node]:
if nei not in seen:
seen.add(nei)
queue.append((nei, depth+1))
return -1
•Time Complexity:
- To create the graph, in Python we do O(∑(N−i)bi), where N denotes the number of buses, and bi
is the number of stops on the ith bus.
2.BFS is on N nodes, and each node could have N edges, so it is O(N^2)
•Space Complexity: O(N^2 + ∑bi)
class DSU:
def __init__(self, R, C):
#R * C is the source, and isn't a grid square
self.par = range(R*C + 1)
self.rnk = [0] * (R*C + 1)
self.sz = [1] * (R*C + 1)
def find(self, x):
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr: return
if self.rnk[xr] < self.rnk[yr]:
xr, yr = yr, xr
if self.rnk[xr] == self.rnk[yr]:
self.rnk[xr] += 1
self.par[yr] = xr
self.sz[xr] += self.sz[yr]
def size(self, x):
return self.sz[self.find(x)]
def top(self):
# Size of component at ephemeral "source" node at index R*C,
# minus 1 to not count the source itself in the size
return self.size(len(self.sz) - 1) - 1
LC803 Bricks Falling When Hit
> Return an array representing the number of bricks that will drop after each erasure in sequence.
> grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
> grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Reverse Time and Union-Find
class Solution(object):
def hitBricks(self, grid, hits):
R, C = len(grid), len(grid[0])
def index(r, c):
return r * C + c
def neighbors(r, c):
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
A = [row[:] for row in grid]
for i, j in hits:
A[i][j] = 0
dsu = DSU(R, C)
for r, row in enumerate(A):
for c, val in enumerate(row):
if val:
i = index(r, c)
if r == 0:
dsu.union(i, R*C)
if r and A[r-1][c]:
dsu.union(i, index(r-1, c))
if c and A[r][c-1]:
dsu.union(i, index(r, c-1))
ans = []
for r, c in reversed(hits):
pre_roof = dsu.top()
if grid[r][c] == 0:
ans.append(0)
else:
i = index(r, c)
for nr, nc in neighbors(r, c):
if A[nr][nc]:
dsu.union(i, index(nr, nc))
if r == 0:
dsu.union(i, R*C)
A[r][c] = 1
ans.append(max(0, dsu.top() - pre_roof - 1))
return ans[::-1]
