今天休闲一下，分享一道LeetCode上medium难度的题目：Evaluate Division

https://leetcode.com/problems/evaluate-division/

题目详情

翻译如下：

给定一组格式为 A/B=k 的方程式，再给出一组格式为 C/D 的求值式，要求得到求值式的所有值，如果值无法求出，则赋值-1.0

例子：

方程式 = [“a/b=2.0”,“b/c=3.0”]

求值式 = [“b/a”,“a/c”,“a/e"]

答案 = [0.5,6.0,-1.0]

分析

这道题给出的方程式都是两个值之间的比值，每个方程式的分子和分母可能会有重复，并且求值式涉及到的两个值可能出现在不同的方程式中，比如在以上例子中，要求求出 a/c 的值，但是 a和 c分别出现在不同的方程式中，如何找出不同方程式中值的关系，是此题的一大难点。

仔细想的话其实不难想到一个方程组其实是一个双向连接图，每个值是一个节点，每个方程式代表了两个节点之间的连接，而相除得到的值可以看为边的权重。当我们确定一个起始节点A和目标节点B时，我们可以通过一次深度第一搜索(DFS)来得到两者之间的比值，而这个比值则是搜索路径所有边权重的乘积，如下图所示， a/c的值为 2*3=6。

值得注意的是，在双向连接图中进行DFS时需要记录一下已经到达过的节点，不然会陷入无限循环之中，以下是完整的python代码：

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]        """        # construct a bi-directional graph with a nested dict        graph = dict()        for idx in range(, len(equations)):            equation = equations[idx]            numerator = equation[]            denominator = equation[1]            if graph.get(denominator) is None:                # self connecting                graph[denominator] = {denominator: 1.0}
            if graph.get(numerator) is None:                graph[numerator] = {numerator: 1.0}
            graph[numerator][denominator] = values[idx]            graph[denominator][numerator] = 1 / values[idx]
        results = list()        for query in queries:            visited = set()            val, _ = self.dfs(graph, visited, query[], query[1])            results.append(val)
        return results
    def dfs(self, graph, visited, src, dst):        visited.add(src)        src_node = graph.get(src)        if src_node is None:            return -1.0, False        val = src_node.get(dst)        if val is not None:            return val, True        for connection in src_node:            if connection in visited:                continue            val, exists = self.dfs(graph, visited, connection, dst)            if not exists:                continue            return src_node[connection] * val, True        return -1.0, False

往期精彩回顾

直击LeetCode最经典二分算法题：Medium of Two Sorted Arrays

我就知道你“在看”

ITPub博客

LeetCode专题】Evaluate Division

题目详情

分析

最新文章