【面试经典 150 | 图】除法求值

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：广度优先搜索
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【图】【广度优先搜索】

题目来源

399. 除法求值

解题思路

方法一：广度优先搜索

思路

我们可以将整个问题建模成一张图：给定图中的一些点（变量），以及某些边的权值（两个变量之间的比值），试着求出任意两点（变量）之间的路径长（两个变量的比值）.

因此，我们首先需要遍历 equations 数组，找出其中所有不同的字符串，并通过哈希表将每个不同的字符串映射成整数。具体地，使用 整型数字 表示字符串，不同的整型数字代表不同的字符串。variables 即为字符串到整型数字的映射哈希表。

接着建图，利用字符串数组 equations 和浮点双精度数组 values 建立无向图。

在构建完图之后，对于任何一个查询，就可以从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。具体地，查询步骤如下：

遍历每一个查询，利用哈希表找出查询的字符串的整型映射值；
如果整型映射值 ia = ib，则更新这两个字符串之间的权值结果 result = 1.0；
否则通过广度优先搜索计算权值：
- 维护一个队列存放整型数值，初始化加入 ia；维护一个数组 rations，rations[y] 表示从 ia 到 y 之间的权值，默认初始化数组元素都为 -1，更新 rations[ia] = 1.0；
- 只要队列非空，并且 rations[ib] < 0（还么找到权值关系），则继续迭代；
- 利用当前出队元素的边，广搜更新下去；
- 最后更新 result = rations[ib]，如果没有找到 ia 与 ib 之间的权值关系（不存在），则 ration[ib] 就是初始化的值 -1。
将当前查询的结果放入答案数组 ret 中；
最后返回答案数组。

代码

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nvars = 0;
        unordered_map<string, int> variables;
        int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end()) {
                variables[equations[i][0]] = nvars++;
            }
            if (variables.find(equations[i][1]) == variables.end()) {
                variables[equations[i][1]] = nvars++;
            }
        }

        //对于每个点，储存其直接连接到所有点及其对应的权值
        vector<vector<pair<int, double>>> edges(nvars);
        for (int i = 0; i <n; ++i) {
            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
            edges[va].push_back(make_pair(vb, values[i]));
            edges[vb].push_back(make_pair(va, 1.0 / values[i]));
        }

        vector<double> ret;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]], ib = variables[q[1]];
                if (ia == ib) {
                    result = 1.0;
                }
                else {
                    queue<int> points;
                    points.push(ia);
                    vector<double> rations(nvars, -1.0);
                    rations[ia] = 1.0;

                    while (!points.empty() && rations[ib] < 0) {
                        int x = points.front(); points.pop();

                        for (const auto [y, val] : edges[x]) {
                            if (rations[y] < 0) {
                                rations[y] = rations[x] * val;
                                points.push(y);
                            }
                        }
                    }
                    result = rations[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};

复杂度分析

时间复杂度： $O(ML+Q\cdot(L+M))$ ，其中 $M$ 为边的数量， $Q$ 为询问的数量， $L$ 为字符串的平均长度。构建图时，需要处理 $M$ 条边，每条边都涉及到 $O (L)$ 的字符串比较；处理查询时，每次查询首先要进行一次 $O (L)$ 的比较，然后至多遍历 $O (M)$ 条边。

空间复杂度： $O (N L + M)$ ，其中 $N$ 为点的数量， $M$ 为边的数量， $L$ 为字符串的平均长度。为了将每个字符串映射到整数，需要开辟空间为 $O (N L)$ 的哈希表；随后，需要花费 $O (M)$ 的空间存储每条边的权重；处理查询时，还需要 $O (N)$ 的空间维护访问队列。最终，总的复杂度为 $O (N L + M + N) = O (N L + M)$ 。