C++刷leetcode（399. 除法求值）【回溯】【有向权重图】

糖逗

题目描述：

1. 给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
   
2. 
   
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 ]
   
7. 
   
8. 输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)，&#160;其中&#160;equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。&#160;返回vector<double>类型。
   
9. 
   
10. 基于上述例子，输入如下：
    
11. 
    
12. equations(方程式) = [ ["a", "b"], ["b", "c"] ],
    
13. values(方程式结果) = [2.0, 3.0],
    
14. queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
    
15. 输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
    
16. 
    
17. 来源：力扣（LeetCode）
    
18. 链接：https://leetcode-cn.com/problems/evaluate-division
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(double res, map<string, vector<pair<string, double> > >&store , string start, string end, string cur, double& out, map<string, int> & visit, bool & flag){
   
4.         if(store.find(cur) == store.end())return;
   
5.         if(cur == end){
   
6.             out = res;
   
7.             flag = true;
   
8.             return;
   
9.         }
   
10.         for(auto cha : store[cur]){
    
11.             if(visit[cha.first] <= 0){
    
12.                 visit[cha.first]++;
    
13.                 double temp = cha.second;
    
14.                 string t1 = cha.first;
    
15.                 res *= temp;
    
16.                 dfs(res, store, start, end, cha.first, out, visit, flag);
    
17.                 res /= temp;
    
18.                 visit[t1]--;
    
19.             }
    
20.         }
    
21.     }
    
22.     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    
23.         map<string, vector<pair<string, double> > > store;
    
24.         for(int i = 0; i < equations.size(); i++){
    
25.             store[equations[i][0]].push_back(make_pair(equations[i][1], values[i]));
    
26.             store[equations[i][1]].push_back(make_pair(equations[i][0], 1/values[i]));
    
27.             
    
28.         }
    
29.         vector<double> res;
    
30.         for(int i = 0; i < queries.size(); i++){
    
31.             if(store.find(queries[i][1]) == store.end()) res.push_back(-1);
    
32.             else{
    
33.                 double temp = 1;
    
34.                 string temp1 = queries[i][0];
    
35.                 string temp2 = queries[i][1];
    
36.                 double out;
    
37.                 map<string, int> visit;
    
38.                 bool flag = false;
    
39.                 dfs(temp, store, temp1, temp2, temp1, out, visit, flag);
    
40.                 if(flag == false) res.push_back(-1);
    
41.                 else res.push_back(out);
    
42.             }
    
43.         }
    
44.         return res;
    
45.     }
    
46. };

复制代码

注意事项：
1、使用visit记录是否访问，防止出现闭环。

糖逗