上海建设银行网站莘庄,免费开网站,微信公众号免费模板网站,网站产品图怎么做给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件#xff0c;其中 equations[i] [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题#xff0c;其中 queries[j]…给你一个变量对数组 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 20equations[i].length 21 Ai.length, Bi.length 5values.length equations.length0.0 values[i] 20.01 queries.length 20queries[i].length 21 Cj.length, Dj.length 5Ai, 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:vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) {// 用邻接表表示图unordered_mapstring, unordered_mapstring, 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;}// 结果数组vectordouble 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_setstring 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_mapstring, unordered_mapstring, double graph, string current, string target, unordered_setstring 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启发 图论的广泛应用 将关系映射为图解决复杂的关系查询问题。 DFS 和 BFS 的灵活性 DFS 适用于路径累积的问题而 BFS 更适合求最短路径。 邻接表的高效性 在稀疏图中邻接表比矩阵更高效。 步骤5实际应用 实际场景货币汇率转换 问题给定一些货币汇率查询两种货币间的转换率。实现方法 使用货币为节点汇率为边权构建图。对每次转换查询使用类似算法计算结果。 其他行业应用 网络传输中的最优路径计算。化学反应方程中分子质量关系的推导。
