leetcode：399. 除法求值

题目

给你一个变量对数组 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"]]
  2. 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
  3. 解释：
  4. 条件：a / b = 2.0, b / c = 3.0
  5. 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
  6. 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
  1. 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
  2. 输出：[3.75000,0.40000,5.00000,0.20000]
  1. 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
  2. 输出：[0.50000,2.00000,-1.00000,-1.00000]

解答 & 代码

变量之间的倍数关系具有传递性，处理有传递性的问题，可以使用“并查集”，需要在并查集的“合并”与“查询”操作中维护这些变量之间的倍数关系。

  • 若两个变量同在一个集合（连通图）中，就能计算出它们的比值，即，可以将不同变量的比值转换成相同变量倍数的比值
  • 若两个变量不在一个集合（连通图）中，则无法计算比值，返回 -1.0

并查集：

  • 定义：

[中等] 399. 除法求值 - 图1

  • **int find(int x)**：递归函数，定义：查询节点 x 的根节点 id 并返回，寻找根节点的过程进行路径压缩，并更新权值

[中等] 399. 除法求值 - 图2

  • **void _union(int x, int y, double value)**：合并操作：x 在一个连通图中，y 在一个连通图中，现有一条 x 指向 y 的路径，合并两个连通图

[中等] 399. 除法求值 - 图3

  • **isConnected(int x, int y)**：判定 x、y 是否在一个连通图内，返回 x/y 的结果

    • 若 x、y 根节点相同，说明在一个连通图内，返回 weight[x]/weight[y]

    • 若 x、y 根节点不同，说明不在一个连通图内，无法计算结果，返回 -1.0 ```cpp class UnionFind { private: vector parent; // 父节点数组，parent[i] 代表节点 i 的父节点 vector weight; // 指向父节点权值数组，weight[i] 代表节点 i 指向 parent[i] 的权值 public: /* 构造函数

      • param n: 并查集的大小/节点数 */ UnionFind(int n) { parent.resize(n); weight.resize(n); for(int i = 0; i < n; ++i) {
        1.  parent[i] = i;        // 将每个节点的父节点都初始化为自己本身
        2.  weight[i] = 1.0;    // 将每个节点指向父节点的权重都初始化为 1.0
        } }

      /* 递归函数定义：查询节点 x 的根节点 id 并返回，寻找根节点的过程进行路径压缩，并更新权值

      • 路径压缩指的是：将节点 x 及其各代祖先节点的父节点都设为根节点（最祖先的节点）
      • param x: 节点 id

      • return: x 的根节点 id */ int find(int x) { // 递归结束条件：如果节点 x 的父节点是 x 本身，说明 x 已经是根节点，直接返回 if(x == parent[x])

        1.  return x;

        int originParent = parent[x]; // 记录节点 x 原本的父节点 id // 递归寻找 parent[x] 的根节点，作为 x 的父节点。寻找的过程中进行路径压缩 parent[x] = find(parent[x]);
        weight[x] *= weight[originParent]; // 更新节点 x 指向父节点（根节点）的权重 return parent[x]; }

      /* 合并操作：x 在一个连通图中，y 在一个连通图中，现有一条 x 指向 y 的路径，合并两个连通图

      • param x: 节点 x 的 id
      • param y: 节点 y 的 id

      • param value: 节点 x 指向节点 y 的权重 */ void _union(int x, int y, double value) { int rootX = find(x); // 节点 x 的根节点 id（find() 查找过程中就会进行路径压缩） int rootY = find(y); // 节点 y 的根节点 id（find() 查找过程中就会进行路径压缩） // 如果节点 x、y 的根节点相同，则无需合并 if(rootX == rootY)

        1.  return;

        // 令 x 的根节点指向 y 的根节点 parent[rootX] = rootY; weight[rootX] = value * weight[y] / weight[x]; // 更新 rootX->rootY 的权重 }

      /* 判定 x、y 是否在一个连通图内，返回 x/y 的结果，

      • 若无法确定答案（x、y 不在一个连通图内）则返回 -1.0
      • param x: 分子
      • param y: 分母
      • return result: x/y 的结果，若无法确定答案则返回 -1.0 */ double isConnected(int x, int y) { int rootX = find(x); // 节点 x 的根节点 id（find() 查找过程中就会进行路径压缩） int rootY = find(y); // 节点 y 的根节点 id（find() 查找过程中就会进行路径压缩） // 如果节点 x、y 的根节点相同，说明 x、y 在一个连通图内，则返回 x/y 的结果 if(rootX == rootY)
        1.  return weight[x] / weight[y];
        // 如果节点 x、y 的根节点不同，说明 x、y 不在一个连通图内，则无法确定答案，返回 -1.0 else
        1.  return -1.0;
        } };

class Solution { public: vector calcEquation(vector>& equations, vector& values, vector>& queries) { // 初始化并查集 int equationsSize = equations.size(); UnionFind unionFind(2 * equationsSize);

  1.     // 1. 预处理：将变量字符串与 id 进行映射，存入哈希表(<变量字符串，id>)
  2.     //    使得并查集的底层实现用数组实现，方便编码
  3.     unordered_map<string, int> hashMap;
  4.     int id = 0;
  5.     for(int i = 0; i < equations.size(); ++i)
  6.     {
  7.         string var1 = equations[i][0];        // 变量 1
  8.         string var2 = equations[i][1];        // 变量 2
  9.         // 插入哈希表
  10.         if(hashMap.find(var1) == hashMap.end())
  11.         {
  12.             hashMap[var1] = id;
  13.             ++id;
  14.         }
  15.         if(hashMap.find(var2) == hashMap.end())
  16.         {
  17.             hashMap[var2] = id;
  18.             ++id;
  19.         }
  21.         // 通过 var1->var2 的边将 var1 的图和 var2 的图合并（构建并查集）
  22.         unionFind._union(hashMap[var1], hashMap[var2], values[i]);
  23.     }
  25.     // 2. 做查询
  26.     int queriesSize = queries.size();
  27.     vector<double> result(queriesSize);        // 结果数组
  28.     for(int i = 0; i < queriesSize; ++i)
  29.     {
  30.         string var1 = queries[i][0];        // 变量 1
  31.         string var2 = queries[i][1];        // 变量 2
  33.         // 若分子、分母的字符串至少有一个在 equations 未出现过，则直接返回 -1.0
  34.         if(hashMap.find(var1) == hashMap.end() || hashMap.find(var2) == hashMap.end())
  35.             result[i] = -1.0;
  36.         else
  37.             result[i] = unionFind.isConnected(hashMap[var1], hashMap[var2]);
  38.     }
  39.     return result;
  40. }

};

  1. 复杂度分析：设 `equations` 包含 N 对变量，其中包含 A 种不同的字符；设 `queries` 包含 Q 对变量
  3. - 时间复杂度 O((N + Q) logA)：
  4.    - 初始化并查集 O(N)
  5.    - 构建并查集 O(N logA)：遍历 `equations`，针对每对变量的边 `var1->var2`，调用 `_union()` 合并两个节点的图。`_union()` 的时间复杂度 O(logA)（`_union()` 中调用 `find()` 路径压缩的时间复杂度），共调用 N 次`_union()` 
  6.    - 查询并查集 O(Q logA)：每次查询调用 `isConnected()` 的时间复杂度 O(logA)（`_union()` 中调用 `find()` 路径压缩的时间复杂度），共 Q 次查询
  7. > 路径压缩时间复杂度应该是 O(h)，h 是树的高度，等于 O(logN)，N 是节点数
  9. - 空间复杂度 O(N)：
  10.    - 哈希表长为 A
  11.    - 并查集中数组 `parent` 和 `weight` 长为 N（初始化为 N，实际只用到 A）
  13. 执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 46.47% 的用户 内存消耗：7.9 MB, 在所有 C++ 提交中击败了 80.42% 的用户 ```