399 Evaluate Division
https://leetcode.com/problems/evaluate-division/
solution
非常考察如何建模
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = self.build_graph(equations, values)
res = []
for x, y in queries:
if x not in graph or y not in graph:
res.append(-1)
continue
visited = set()
prod = self.dfs(graph, x, y, 1, visited) # 关于返回值,开始很久返回都是空. 通过有的返回-1来识别最终返回非-1的那一个
res.append(prod)
return res
def build_graph(self, equations, values):
graph = collections.defaultdict(dict) # 带权重
for equation, value in zip(equations, values):
x, y = equation
graph[x][y] = value
graph[y][x] = 1 / value
return graph
def dfs(self, graph, x, y, prod, visited):
if x == y:
return prod
visited.add(x)
for next, val in graph[x].items(): # 权重图的值还是一个hash
if next not in visited:
result = self.dfs(graph, next, y, prod*val, visited)
if result != -1: # A path to y is found
return result
return -1 # 这里的-1以及上面的 不等于-1时返回result. 参考树公共祖先, 需要深刻理解递归
时间复杂度:O() 空间复杂度:O()
follow up
1466. Reorder Routes to Make All Paths Lead to the City Zero
类似的建模方式. 同样要注意dfs输出的问题
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
graph = collections.defaultdict(dict)
for x, y in connections:
graph[x][y] = 1
graph[y][x] = 0
visited = set()
visited.add(0)
res = [0] # 注意利用了 list也能保存结果
self.dfs(graph, 0, n, res, visited)
return res[0]
def dfs(self, graph, start, n, res, visited):
if len(visited) == n:
return res[0]
visited.add(start)
for adj, value in graph[start].items():
if adj not in visited:
res[0] += value
out = self.dfs(graph, adj, n, res, visited)
bfs
Last updated