除法求值

难度: Medium

给定一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [A_i, B_i] 和 values[i] 共同表示等式 A_i / B_i = values[i] 。每个 A_i 或 B_i 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [C_j, D_j] 表示第 j 个问题，请你根据已知条件找出 C_j / D_j = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

1 <= equations.length <= 20
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= C_j.length, D_j.length <= 5
A_i, B_i, C_j, D_j 由小写英文字母与数字组成

注意：本题与主站 399 题相同： https://leetcode-cn.com/problems/evaluate-division/

Submission

运行时间: 19 ms

内存: 16.3 MB

class Solution:
    def dfs (self,x,target,temp,visted,graph):
        if x == target:
            return temp
        for node,value in graph[x]:
            if visted[node]:
                continue
            visted[node] = True
            result = self.dfs(node,target,temp / value,visted, graph)
            visted[node] = False
            if result != -1:
                return result
        return -1
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        graph = collections.defaultdict(list)
        node = set()
        for i, (v1,v2) in enumerate(equations):
            graph[v1].append([v2,1/values[i]])
            graph[v2].append([v1,values[i]])
            node.add(v1)
            node.add(v2)
        result = []
        visted = {n:False for n in node}
        for x,y in queries:
            if x not in node or y not in node:
                result.append(-1)
                continue
            visted[x] = True
            result.append(self.dfs(x,y,1,visted,graph))
            visted[x] = False
        return result
            




















        a = list(zip(equations,values))
        a = sorted(a)
        equations = []
        values = []
        for pair in a:
            e,v = pair
            equations.append(e)
            values.append(v)
        help_dict = {}
        v1,v2 = equations[0]
        help_dict[v1] = 1
        help_dict[v2] = help_dict[v1] / values[0]
        for i in range(1,len(equations)):
            v1, v2 = equations[i]
            if v1 not in help_dict and v2 not in help_dict:
                help_dict[v2] = 1
                help_dict[v1] = help_dict[v2] * values[i]
            elif v1 not in help_dict:
                help_dict[v1] = help_dict[v2] * values[i]
            elif v2 not in help_dict:
                help_dict[v2] = help_dict[v1] / values[i]
        result = []
        for q in queries:
            v1, v2 = q
            v1_list = v1.split()
            v2_list = v2.split()
            # for i in range(len(v1_list)):
            #     ele = v1_list[i]
            #     if ele in v2_list:
            #         v1_list.pop(i)
            #         v2_list.remove(ele)
            v1_result = 1
            v2_result = 1
            judge = False
            for ele in v1_list:
                if ele not in help_dict:
                    result.append(-1)
                    judge = True
                    break
                v1_result *= help_dict[ele]
            if judge:
                continue
            for ele in v2_list:
                if ele not in help_dict:
                    result.append(-1)
                    judge = True
                    break
                v2_result *= help_dict[ele]
            if judge:
                continue
            result.append(v1_result/v2_result)
        return result

Explain

这个题解采用了图的深度优先搜索（DFS）来解决问题。首先，构建一个图，每个节点代表一个变量，每条边代表两个变量之间的除法关系，并存储这个比值。对于每个查询，使用DFS从起点变量尝试到达终点变量，并沿途计算乘积。如果能到达目标节点，则返回计算的结果，否则返回-1。为了避免环路和重复访问，使用一个visited字典来记录访问过的节点。

时间复杂度: O(Q*(V+E))

空间复杂度: O(V+E)

class Solution:
    def dfs(self, x, target, temp, visited, graph):
        # 如果当前节点等于目标节点，返回当前计算的结果
        if x == target:
            return temp
        # 遍历当前节点的所有邻接节点
        for node, value in graph[x]:
            if visited[node]:
                continue
            visited[node] = True
            result = self.dfs(node, target, temp / value, visited, graph)
            visited[node] = False
            if result != -1:
                return result
        return -1
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # 构建图
        graph = collections.defaultdict(list)
        node = set()
        for i, (v1, v2) in enumerate(equations):
            graph[v1].append([v2, 1/values[i]])
            graph[v2].append([v1, values[i]])
            node.add(v1)
            node.add(v2)
        result = []
        visited = {n: False for n in node}
        # 处理每个查询
        for x, y in queries:
            if x not in node or y not in node:
                result.append(-1)
                continue
            visited[x] = True
            result.append(self.dfs(x, y, 1, visited, graph))
            visited[x] = False
        return result

Explore

在构建图时，添加正向和反向的边以及存储除法结果及其倒数，是为了确保无论查询的方向如何，都能通过图中已有的边来找到一条有效路径。例如，如果存在除法关系 a / b = 2，则同时存储 b / a = 0.5。这样，无论查询是要求 a / b 还是 b / a，都可以直接在图中找到对应的边来计算结果。这种双向连接也便于图遍历算法如DFS能在任一方向上探索并找到解答。

在DFS过程中跳过已访问的节点是为了防止无限循环和重复计算，从而提高算法效率。如果在递归的过程中重新访问一个已经访问过的节点，可能会形成一个环，导致算法陷入无限循环。此外，重复访问同一节点通常意味着重复执行相同的计算，这不仅无助于找到正确答案，还会增加时间复杂度。因此，避免重复访问可以保持DFS的正确性和效率。

在处理每个查询之前，visited字典会被重置，确保每次查询都从一个干净的状态开始。这样做可以避免不同查询之间的相互干扰。对于每个查询，DFS开始前将visited标记为所有节点未访问。一旦该查询结束，visited状态会重置，为下一个查询提供了一个未访问的新环境。这保证了每个查询都是独立处理，保持了查询结果的独立性和准确性。