《剑指 Offer》专项突破版 - 面试题 111 : 计算除法（C++ 实现）

题目链接：计算除法

题目：

输入两个数组 equations 和 values，其中，数组 equations 的每个元素包含两个表示变量名的字符串，数组 values 的每个元素是一个浮点数值。如果 equations[i] 的两个变量名分别是 $A_i$ 和 $B_i$ ，那么 $A_i / B_i$ = values[i]。再给定一个数组 queries，它的每个元素也包含两个变量名。对于 queries[j] 的两个变量名 $C_j$ 和 $D_j$ ，请计算 $C_j / D_j$ 的结果。假设任意 values[i] 大于 0。如果不能计算，那么返回 -1.0。

例如，输入数组 equations 为 [["a", "b"], ["b", "c"]]，数组 values 为 [2.0, 3.0]，如果数组 queries 为 [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]，那么对应的计算结果为 [6.0, 0.5, -1.0, 1.0, -1.0]。由数组 equations 和 values 可知，a / b = 2.0，b / c = 3.0，所以，a / c = 6.0，b / a = 0.5，a / a = 1.0。

分析：

图可以用来表示物体与物体之间的关系，节点对应物体，而物体之间的关系用边表示。这个问题是关于两个变量之间的除法，因此可以将变量看作图中的节点。如果存在两个变量的除法等式，那么这两个变量对应的节点之间有一条边相连。

一个除法等式除了被除数和除数，还有商。被除数和除数都对应图中的节点，商是两个变量的除法的结果，表达的是变量之间的关系，因此商是边的属性。可以给图中的每条边定义一个权重，为两个变量的除法的商。

由于 a / b 一般不等于 b / a，因此从节点 a 到节点 b 的边和从节点 b 到节点 a 的边的权重不同，即这个图是有向图，节点 a 和节点 b 之间有两条不同方向的有向边。

可以尝试根据数组 equations [["a", "b"], ["b", "c"]] 和数组 values [2.0, 3.0] 构建对应的图。因为 a / b = 2.0，所以图中有一条从节点 a 到节点 b 的边，权重为 2.0。同时由数学常识可知 b / a = 1/2，所以图中还有一条由节点 b 指向节点 a 的权重为 1/2 的边。类似地，因为 b / c = 3.0，所以图中有一条由节点 b 指向节点 c 的权重为 3.0 的边，还有一条由节点 c 指向节点 b 的权重为 1/3 的边。构建出来的图如下图所示。

构建出图之后就可以逐一计算数组 queries 中除法表达式的值。

代码实现：

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)
        {
            graph[equations[i][0]].push_back({ equations[i][1], values[i] });
            graph[equations[i][1]].push_back({ equations[i][0], 1.0 / values[i] });
        }

        vector<double> result(queries.size(), -1.0);
        for (int i = 0; i < queries.size(); ++i)
        {
            if (graph.count(queries[i][0]) && graph.count(queries[i][1]))
            {
                unordered_set<string> visited;
                result[i] = dfs(graph, visited, queries[i][0], queries[i][1]);
            }
        }
        return result;
    }
private:
    double dfs(unordered_map<string, vector<pair<string, double>>>& graph, unordered_set<string>& visited, string& from, string& to) {
        if (from == to)
            return 1.0;
        
        visited.insert(from);
        for (pair<string, double>& node : graph[from])
        {
            if (!visited.count(node.first))
            {
                double ret = dfs(graph, visited, node.first, to);
                if (ret > 0)
                    return node.second * ret;
            }
        }
        visited.erase(from);
        return -1.0;
    }
};

在上述代码中，图是用 unordered_map 表示的邻接表，unordered_map 的键是图中的节点（对应一个变量，是有向边的起始节点）；值是一个数组，数组中的每个元素包含有向边的终止节点和边的权重。

接下来考虑如何计算除法。已知 a / b = 2.0、b / c = 3.0，那么 a / c 等于多少？由数学常识可知 $\dfrac{a}{b} \times \dfrac{b}{c} = \dfrac{a}{c}$ ，所以 a / c = 6.0。由于 a / b = 2.0 对应图中从节点 a 指向节点 b 的一条权重为 2.0 的边，b / c = 3.0 对应图中从节点 b 指向节点 c 的一条权重为 3.0 的边，计算 a / c 的过程可以看成在图中找到一条从节点 a 到节点 c 的路径，并将该路径经过的边的权重相乘。