leetcode399：除法求值

给你一个变量对数组 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 ]
注意：x 是未定义的 => -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 由小写英文字母与数字组成

步骤1：定义题目问题性质

1. 问题性质：

   • 输入：
     • equations: 包含已知等式的字符串对列表，如 [["a", "b"], ["b", "c"]]。
     • values: 对应每个等式的值列表，如 [2.0, 3.0]。
     • queries: 包含待求解问题的字符串对列表，如 [["a", "c"], ["b", "a"]]。
   • 输出：
     • 对于每个问题，返回相应的结果。无法确定的结果返回 -1.0。

2. 限制条件：

   • 1 <= equations.length, queries.length <= 20
   • 每个变量由小写字母和数字组成，长度在 [1, 5] 范围内。
   • 保证无除数为 0 的情况，无矛盾结果。

3. 潜在边界条件：

   • 查询中涉及未定义变量时，应返回 -1.0。
   • 对变量自身的查询（如 ["a", "a"]），结果恒为 1.0。
   • 可能出现循环关系，如 a/b = 2.0 和 b/a = 0.5。

---

步骤2：算法设计和步骤

此问题本质上是一个 图论问题：

• 每个变量是图的一个节点。
• 每个等式表示节点之间的边，边权重是等式的值。

解决方法：使用 Floyd-Warshall 算法或 DFS/BFS 构建和查询图。

1. 图的构建：

   • 使用邻接表表示图，存储节点和边权。
   • 将等式 a / b = k 转化为两条边：
     • a -> b，权重为 k。
     • b -> a，权重为 1/k。

2. 查询处理：

   • 如果两个节点之间有路径，通过图的边权相乘计算结果。
   • 如果两个节点之间无路径，返回 -1.0。

3. 算法步骤：

   • 步骤1：构建图。
   • 步骤2：使用深度优先搜索（DFS）处理每个查询：
     • 维护访问记录以防止无限循环。
     • 在路径上累积结果，如果找到目标节点，返回结果。
   • 步骤3：将结果存入列表并返回。

4. 时间复杂度分析：

   • 图构建：O(E)，其中 E 是等式数量。
   • 每次查询：O(V + E)，使用 DFS 遍历图。
   • 总体复杂度：O(E + Q * (V + E))，Q 是查询数量。

---

步骤3：详细C++代码

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];string b = equations[i][1];double value = values[i];graph[a][b] = value;graph[b][a] = 1.0 / value;}// 结果数组vector<double> results;// 对每个查询进行DFSfor (auto& query : queries) {string start = query[0];string end = query[1];// 如果变量不存在，直接返回 -1.0if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {results.push_back(-1.0);continue;}// 访问记录unordered_set<string> visited;double result = -1.0;if (dfs(graph, start, end, visited, 1.0, result)) {results.push_back(result);} else {results.push_back(-1.0);}}return results;}private:// 深度优先搜索函数bool dfs(unordered_map<string, unordered_map<string, double>>& graph, string current, string target, unordered_set<string>& visited, double current_value, double& result) {// 如果找到目标节点，返回当前累计结果if (current == target) {result = current_value;return true;}// 标记当前节点为已访问visited.insert(current);// 遍历邻接节点for (auto& neighbor : graph[current]) {if (visited.find(neighbor.first) == visited.end()) {if (dfs(graph, neighbor.first, target, visited, current_value * neighbor.second, result)) {return true;}}}// 回溯visited.erase(current);return false;}
};

步骤4：启发

1. 图论的广泛应用：

   • 将关系映射为图，解决复杂的关系查询问题。

2. DFS 和 BFS 的灵活性：

   • DFS 适用于路径累积的问题，而 BFS 更适合求最短路径。

3. 邻接表的高效性：

   • 在稀疏图中，邻接表比矩阵更高效。

---

步骤5：实际应用

1. 实际场景：货币汇率转换

   • 问题：给定一些货币汇率，查询两种货币间的转换率。
   • 实现方法：
     • 使用货币为节点，汇率为边权，构建图。
     • 对每次转换查询，使用类似算法计算结果。

2. 其他行业应用：

   • 网络传输中的最优路径计算。
   • 化学反应方程中分子质量关系的推导。