C++刷leetcode（399. 除法求值）【回溯】【有向权重图】
本帖最后由 糖逗 于 2020-6-7 15:23 编辑题目描述：
给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回
输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。
基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = ,
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
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){
if(store.find(cur) == store.end())return;
if(cur == end){
out = res;
flag = true;
return;
}
for(auto cha : store){
if(visit <= 0){
visit++;
double temp = cha.second;
string t1 = cha.first;
res *= temp;
dfs(res, store, start, end, cha.first, out, visit, flag);
res /= temp;
visit--;
}
}
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
map<string, vector<pair<string, double> > > store;
for(int i = 0; i < equations.size(); i++){
store].push_back(make_pair(equations, values));
store].push_back(make_pair(equations, 1/values));
}
vector<double> res;
for(int i = 0; i < queries.size(); i++){
if(store.find(queries) == store.end()) res.push_back(-1);
else{
double temp = 1;
string temp1 = queries;
string temp2 = queries;
double out;
map<string, int> visit;
bool flag = false;
dfs(temp, store, temp1, temp2, temp1, out, visit, flag);
if(flag == false) res.push_back(-1);
else res.push_back(out);
}
}
return res;
}
};
注意事项：
1、使用visit记录是否访问，防止出现闭环。 {:10_298:}
页:
[1]