当前位置：首页 > news >正文

leetcode399：除法求值

news 2024/12/14 0:29:29

给你一个变量对数组 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：定义题目问题性质

问题性质：
- 输入：
  - equations: 包含已知等式的字符串对列表，如 [["a", "b"], ["b", "c"]]。
  - values: 对应每个等式的值列表，如 [2.0, 3.0]。
  - queries: 包含待求解问题的字符串对列表，如 [["a", "c"], ["b", "a"]]。
- 输出：
  - 对于每个问题，返回相应的结果。无法确定的结果返回 -1.0。
限制条件：
- 1 <= equations.length, queries.length <= 20
- 每个变量由小写字母和数字组成，长度在 [1, 5] 范围内。
- 保证无除数为 0 的情况，无矛盾结果。
潜在边界条件：
- 查询中涉及未定义变量时，应返回 -1.0。
- 对变量自身的查询（如 ["a", "a"]），结果恒为 1.0。
- 可能出现循环关系，如 a/b = 2.0 和 b/a = 0.5。

步骤2：算法设计和步骤

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

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

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

图的构建：
- 使用邻接表表示图，存储节点和边权。
- 将等式 a / b = k 转化为两条边：
  - a -> b，权重为 k。
  - b -> a，权重为 1/k。
查询处理：
- 如果两个节点之间有路径，通过图的边权相乘计算结果。
- 如果两个节点之间无路径，返回 -1.0。
算法步骤：
- 步骤1：构建图。
- 步骤2：使用深度优先搜索（DFS）处理每个查询：
  - 维护访问记录以防止无限循环。
  - 在路径上累积结果，如果找到目标节点，返回结果。
- 步骤3：将结果存入列表并返回。
时间复杂度分析：
- 图构建：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;}
};