写在前面
今天依旧是一道来自图论的题目，而今天这道题目的难度也是相对于前面分享过的题目中难度最大的一种。题主在第一次做这道题的时候根本没有反应过来这道题目可以转化为 图 来解决。而这道题目将一个 二维数组的乘除 运算转化为 图论 的过程需要一定的数学思维思考，今天就让我们一起来看看这道题怎么个事儿吧～～
题目介绍：
题目信息：
- 题目链接：https://leetcode.com/problems/evaluate-division/description/
- 题目类型： Array，Graph， DFS，Union-Find (没错可以用 uf，但是今天暂时不分享这种做法）
- 题目难度：Medium (但其实真的可以算是 hard，在面试中如果第一次碰到这个题就自求多福啦 ～～）
- 题目来源：Google 高频面试题
题目问题：
- 给定一个数组 pairs（equations）每一个 pair 的第一个是除数，第二个是被除数，均由 string 变量名指代）
- 给定一个数组（values），每一个位置的 double 值对应上一数组 pairs 的相除结果
- 给定一个数组 pairs（queries），要求输出每一个 pair 的第一个数 / 第二个数的结果，依次按序输出
- 如果无法计算，则结果为 -1.0
- 举例：
题目想法：
这道题的难点在于，怎么样将一个看似与图论无关的问题转化为 图论问题，或者说，在我们刚拿到这道题的时候，我们是怎么样去思考，从而将一个看似非常独立的题目转化为我们熟悉的解题结构中呢？
我们首先观察给定的题目特性，假设我们拥有 a/b，b/c 和他们对应的值，那我们是怎么得到 a/c 的值的呢：
a/c = a/b * b/c where a/b and b/c are given known value
我们可以发现 a/c 其实就是 a/b 和 b/c 以乘法链接在一起，展现出来的样子相当于先从 a -> b, 再从 b -> c, 诶，是不是感觉好像有图论的感觉了
如果我们要知道，比如说 a/d 的值，我们就需要找到以 a 为起点，d 为重点的一个非循环路径，而在每一次路径的过程中，分子为起点，分母为终点，而每次的结果都是以乘法叠加在一起的：
a/d = a/n1 * n1/n2 * n2/n3 ..... * nk/ d
这其中的 n1, n2, n3, ..., nk 必须满足：
- 任意 n1/n2 的值已知，即要么已经给定，要么存在于图论系统中
- 任意 n1 != n2，一旦有循环则意味着我们不可能抵达终点
而经过这样的转化，我们的问题就变成了，对于每一个 query 的 a/b，我们以 a 为起点，通过遍历图，找寻是否能抵达 b 这个终点。如果不能抵达返回 -1。没经过一个节点，都将当前的值乘加在总的结果上，当我们找到最后一个点时，返回所有的乘法累计结果。
总的来说：在创造这个图的时候，两点之间的连接是双向的，而这个路径上的权重则为 a/b (如果是 a -> b) 或者是 b/a (如果是 b -> a), 而在题目给定 a/b 的结果后，b/a 就是 1/(a/b))
使用 DFS 来对每一个 起点 a 和终点 b 的结果进行找寻即可
题目解法：
- 遍历所有 “equations” 和 “values”，对于每一个位置，分别记录下来 a -> b 和 b -> a 的adjacent 和 相应的经过需要乘算的数。
- 遍历所有需要找寻的 “queries”：
- 以当前 query 的起始点与末端点找寻 DFS
- 如果通路，返回结果
- 如果不同，返回 -1
题目代码：
class Solution {
public:
//store the divisor and dividend's mutual path
unordered_map<string, vector<pair<string, double>>> graph;
set<string> visited;
vector<double> res;
//traverse the graph for a single query
double DFS(string start, string target, double currProduct){
//if we visited this node, then we find the loop, return:
if(visited.find(start) != visited.end()){
return -1.0; //indicate that this route is not ok
}
visited.insert(start);
//if we reach the end:
if(start == target){
return currProduct;
}
//else, go over teh map:
vector<pair<string, double>> neighbours = graph[start];
for(auto neighbour: neighbours){
string new_start = neighbour.first;
double new_product = currProduct * neighbour.second;
double res = DFS(new_start, target, new_product);
if(res != -1.0){
return res;
}
}
return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
//copy the graph down
//for Numerator -> Denominater, it just the values at the position
//for Denominater -> Numerator, it is the 1 / (values at the position)
int size = values.size();
for(int i = 0; i < 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]});
}
//traverse the route for each queries:
for(int i = 0; i < queries.size(); i++){
// if one of the point not in the map, then there is no route
if(!graph.contains(queries[i][0]) || !graph.contains(queries[i][1])){
res.emplace_back(-1.0);
continue;
}
// if the start and destination is the same node, then it should be a self loop
// answer shall be one
if(queries[i][0] == queries[i][1]){
res.emplace_back(1.0);
continue;
}
//traverse the graph and append the answer, clear the map everytime we did it
double ret = DFS(queries[i][0], queries[i][1], 1.0);
res.emplace_back(ret);
visited.clear();
}
return res;
}
};- Runtime: O(M*N) DFS 遍历最差是需要全部遍历 O(N) * 总共有 M 组 query O(M)
- Space: O(N) 存储所有点的adjacent 信息
