Medium

题目描述

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

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

返回所有问题的答案。如果存在某个无法确定的答案，则用 -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 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj 由小写英文字母与数字组成

解题思路

这是一个典型的图论问题。我们可以将每个变量看作图中的节点，每个等式看作有向边。

方法一：深度优先搜索（DFS）

  • 构建有向图：对于每个等式 a/b = k，我们建立两条边：从 a 到 b 权重为 k，从 b 到 a 权重为 1/k
  • 对于每个查询，使用 DFS 从起始节点搜索到目标节点，如果找到路径，将路径上的权重相乘即为答案
  • 如果找不到路径或节点不存在，返回 -1.0

方法二：并查集

  • 使用带权并查集，每个节点维护到根节点的权重比值
  • 查询时检查两个节点是否在同一连通分量中，如果是则计算比值

方法三：Floyd-Warshall算法

  • 将问题转化为求最短路径问题，使用 Floyd 算法预处理所有节点对之间的比值关系

推荐使用 DFS 方法，代码简洁且易于理解。时间复杂度适中，适合题目的数据规模。

代码实现

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;
        
        // 构建图
        for (int i = 0; i < equations.size(); i++) {
            string a = equations[i][0], b = equations[i][1];
            double val = values[i];
            graph[a][b] = val;
            graph[b][a] = 1.0 / val;
        }
        
        vector<double> result;
        for (auto& query : queries) {
            string start = query[0], end = query[1];
            if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
                result.push_back(-1.0);
            } else if (start == end) {
                result.push_back(1.0);
            } else {
                unordered_set<string> visited;
                double ans = dfs(graph, start, end, visited);
                result.push_back(ans);
            }
        }
        return result;
    }
    
private:
    double dfs(unordered_map<string, unordered_map<string, double>>& graph, 
               string start, string end, unordered_set<string>& visited) {
        if (start == end) return 1.0;
        
        visited.insert(start);
        for (auto& neighbor : graph[start]) {
            if (visited.find(neighbor.first) == visited.end()) {
                double result = dfs(graph, neighbor.first, end, visited);
                if (result != -1.0) {
                    return neighbor.second * result;
                }
            }
        }
        return -1.0;
    }
};

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        from collections import defaultdict
        
        # 构建图
        graph = defaultdict(dict)
        for (a, b), val in zip(equations, values):
            graph[a][b] = val
            graph[b][a] = 1.0 / val
        
        def dfs(start, end, visited):
            if start == end:
                return 1.0
            
            visited.add(start)
            for neighbor, weight in graph[start].items():
                if neighbor not in visited:
                    result = dfs(neighbor, end, visited)
                    if result != -1.0:
                        return weight * result
            return -1.0
        
        result = []
        for start, end in queries:
            if start not in graph or end not in graph:
                result.append(-1.0)
            elif start == end:
                result.append(1.0)
            else:
                visited = set()
                ans = dfs(start, end, visited)
                result.append(ans)
        
        return result

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();
        
        // 构建图
        for (int i = 0; i < equations.Count; i++) {
            string a = equations[i][0], b = equations[i][1];
            double val = values[i];
            
            if (!graph.ContainsKey(a)) graph[a] = new Dictionary<string, double>();
            if (!graph.ContainsKey(b)) graph[b] = new Dictionary<string, double>();
            
            graph[a][b] = val;
            graph[b][a] = 1.0 / val;
        }
        
        var result = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string start = queries[i][0], end = queries[i][1];
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) {
                result[i] = -1.0;
            } else if (start == end) {
                result[i] = 1.0;
            } else {
                var visited = new HashSet<string>();
                result[i] = DFS(graph, start, end, visited);
            }
        }
        return result;
    }
    
    private double DFS(Dictionary<string, Dictionary<string, double>> graph, 
                       string start, string end, HashSet<string> visited) {
        if (start == end) return 1.0;
        
        visited.Add(start);
        foreach (var neighbor in graph[start]) {
            if (!visited.Contains(neighbor.Key)) {
                double result = DFS(graph, neighbor.Key, end, visited);
                if (result != -1.0) {
                    return neighbor.Value * result;
                }
            }
        }
        return -1.0;
    }
}

var calcEquation = function(equations, values, queries) {
    const graph = new Map();
    
    // Build graph
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        const val = values[i];
        
        if (!graph.has(a)) graph.set(a, []);
        if (!graph.has(b)) graph.set(b, []);
        
        graph.get(a).push([b, val]);
        graph.get(b).push([a, 1 / val]);
    }
    
    const dfs = (start, end, visited) => {
        if (!graph.has(start) || !graph.has(end)) return -1.0;
        if (start === end) return 1.0;
        
        visited.add(start);
        
        for (const [neighbor, weight] of graph.get(start)) {
            if (!visited.has(neighbor)) {
                const result = dfs(neighbor, end, visited);
                if (result !== -1.0) {
                    return weight * result;
                }
            }
        }
        
        return -1.0;
    };
    
    const results = [];
    for (const [c, d] of queries) {
        results.push(dfs(c, d, new Set()));
    }
    
    return results;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(M × (N + E))，其中 M 是查询数量，N 是节点数量，E 是边数量
空间复杂度O(N + E)，用于存储图和递归栈

相关题目