首页 > 其他 > 详细

leetcode-399-除法求值

时间:2019-10-11 20:55:04      阅读:122      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 方法一:dfs+图

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}
        for (x,y),v in zip(equations,values):
            if x not in graph:
                graph[x] = {y:v}
            else:
                graph[x][y] = v
            if y not in graph:
                graph[y] = {x:1/v}
            else:
                graph[y][x] = 1/v
        
        def dfs(x,y):
            if x not in graph:
                return -1
            if x == y:
                return 1
            for node in graph[x].keys():
                if node == y:
                    return graph[x][node]
                elif node not in visited:
                    visited.add(node)
                    v = dfs(node,y)
                    if v!= -1:
                        return graph[x][node]*v
            return -1
        res = []
        for x,y in queries:
            visited = set()
            res.append(dfs(x,y))
        return res

 

leetcode-399-除法求值

原文:https://www.cnblogs.com/oldby/p/11656678.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!