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