题目链接:计算除法
题目:
输入两个数组 equations 和 values,其中,数组 equations 的每个元素包含两个表示变量名的字符串,数组 values 的每个元素是一个浮点数值。如果 equations[i] 的两个变量名分别是 和 ,那么 = values[i]。再给定一个数组 queries,它的每个元素也包含两个变量名。对于 queries[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 等于多少?由数学常识可知 ,所以 a / c = 6.0。由于 a / b = 2.0 对应图中从节点 a 指向节点 b 的一条权重为 2.0 的边,b / c = 3.0 对应图中从节点 b 指向节点 c 的一条权重为 3.0 的边,计算 a / c 的过程可以看成在图中找到一条从节点 a 到节点 c 的路径,并将该路径经过的边的权重相乘。