企业官网建设流程全解析

题目描述：

给你一个变量对数组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]

解题思路：

方法一：图 + DFS/BFS

核心思路：

建图：

对于A / B = k：

• 从 A 到 B 有一条权重为k的边

• 从 B 到 A 有一条权重为1/k的边

这样，A / C就转化为从 A 到 C 的路径上所有边的权重乘积。

具体过程示例：

equations = [["a","b"],["b","c"]], values = [2.0, 3.0]

a --2.0--> b --3.0--> c a <--0.5-- b <--1/3-- c a / c = a->b->c = 2.0 * 3.0 = 6.0

查询逻辑：

• 如果from或to不在图中 → 返回-1.0

• 如果from == to→ 返回1.0

• 否则，从from出发 DFS/BFS 搜索到to，沿途累乘权重

代码实现（DFS）：

class Solution { public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { // 建图：邻接表，存储 (邻居, 权重) unordered_map<string, vector<pair<string, double>>> graph; for (int i = 0; i < equations.size(); i++) { string a = equations[i][0], b = equations[i][1]; double v = values[i]; graph[a].push_back({b, v}); graph[b].push_back({a, 1.0 / v}); } vector<double> result; for (auto& query : queries) { string from = query[0], to = query[1]; // 变量不存在 if (graph.find(from) == graph.end() || graph.find(to) == graph.end()) { result.push_back(-1.0); continue; } // 相同变量 if (from == to) { result.push_back(1.0); continue; } // DFS 搜索 unordered_set<string> visited; result.push_back(dfs(graph, from, to, 1.0, visited)); } return result; } private: double dfs(unordered_map<string, vector<pair<string, double>>>& graph, string curr, string target, double value, unordered_set<string>& visited) { if (curr == target) return value; if (visited.count(curr)) return -1.0; visited.insert(curr); for (auto& [next, weight] : graph[curr]) { double res = dfs(graph, next, target, value * weight, visited); if (res != -1.0) return res; } return -1.0; } };

复杂度分析：

设E是方程式数量，Q是查询数量，V是变量数量。

方法二：并查集

带权并查集的核心：

权重定义

weight[x] = x / parent[x]

• 如果x是根节点，weight[x] = 1.0

• 查找时，路径压缩需要更新权重

合并逻辑：

已知a / b = v，要把a和b合并到同一集合：

• 找到a的根rootA，b的根rootB

• 如果rootA != rootB，把rootA接到rootB上

• 需要计算rootA / rootB的值

推导：

a / b = v a = weight[a] * rootA b = weight[b] * rootB 所以: (weight[a] * rootA) / (weight[b] * rootB) = v 即: rootA / rootB = v * weight[b] / weight[a]

所以weight[rootA] = v * weight[b] / weight[a]。

查询逻辑：

已知from和to：

• 如果它们不在同一集合 → 返回-1.0

• 如果在同一集合，from / to = weight[from] / weight[to]

代码实现：

class Solution { private: unordered_map<string, string> parent; // 父节点 unordered_map<string, double> weight; // weight[x] = x / parent[x] // 查找根节点，路径压缩 + 更新权重 string find(string x) { if (parent[x] != x) { string root = find(parent[x]); weight[x] *= weight[parent[x]]; // 更新 x / root parent[x] = root; } return parent[x]; } // 合并：a / b = v void unite(string a, string b, double v) { string rootA = find(a); string rootB = find(b); if (rootA == rootB) return; // rootA / rootB = v * weight[b] / weight[a] parent[rootA] = rootB; weight[rootA] = v * weight[b] / weight[a]; } public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { // 初始化：每个变量是独立集合，权重为 1 for (int i = 0; i < equations.size(); i++) { string a = equations[i][0], b = equations[i][1]; if (parent.find(a) == parent.end()) { parent[a] = a; weight[a] = 1.0; } if (parent.find(b) == parent.end()) { parent[b] = b; weight[b] = 1.0; } unite(a, b, values[i]); } vector<double> result; for (auto& query : queries) { string from = query[0], to = query[1]; // 变量不存在 if (parent.find(from) == parent.end() || parent.find(to) == parent.end()) { result.push_back(-1.0); continue; } string rootFrom = find(from); string rootTo = find(to); // 不在同一集合 if (rootFrom != rootTo) { result.push_back(-1.0); continue; } // 在同一集合：from / to = weight[from] / weight[to] result.push_back(weight[from] / weight[to]); } return result; } };

具体过程示例：

equations = [["a","b"],["b","c"]], values = [2.0, 3.0]

初始化：

parent: {a:a, b:b, c:c} weight: {a:1.0, b:1.0, c:1.0}

合并 a/b = 2.0：

rootA = a, rootB = b parent[a] = b weight[a] = 2.0 * weight[b] / weight[a] = 2.0 * 1.0 / 1.0 = 2.0 parent: {a:b, b:b, c:c} weight: {a:2.0, b:1.0, c:1.0}

合并 b/c = 3.0:

rootB = b, rootC = c parent[b] = c weight[b] = 3.0 * weight[c] / weight[b] = 3.0 * 1.0 / 1.0 = 3.0 parent: {a:b, b:c, c:c} weight: {a:2.0, b:3.0, c:1.0}

查询 a/c:

find(a): a->b->c，路径压缩 weight[a] = 2.0 * 3.0 = 6.0（a/c） parent[a] = c find(c): c 是根，weight[c] = 1.0 a/c = weight[a] / weight[c] = 6.0 / 1.0 = 6.0 ✅

复杂度分析:

E 是方程式数量，Q 是查询数量，V 是变量数量。

关键细节:

1. 路径压缩时为什么要更新权重？

string root = find(parent[x]); weight[x] *= weight[parent[x]]; parent[x] = root;

因为weight[x]原来表示x / parent[x]，路径压缩后要变成x / root，所以需要乘上parent[x] / root（即weight[parent[x]]）。

2. 合并时 weight[rootA] 怎么算？

a / b = v a = weight[a] * rootA b = weight[b] * rootB (weight[a] * rootA) / (weight[b] * rootB) = v rootA / rootB = v * weight[b] / weight[a]

所以weight[rootA] = v * weight[b] / weight[a]。

3. 查询时为什么是weight[from] / weight[to]？

因为：

from / to = (weight[from] * root) / (weight[to] * root) = weight[from] / weight[to]

根节点被约掉了。

并查集 vs DFS/BFS:

并查集适合查询多的场景，DFS/BFS 代码更直观。