Leetcode 399. 除法求值
题目
给出方程式 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 = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
输入为: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector类型。
基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
题解
dfs深搜回溯 我们建立一个有向图，我们假设a/b=2，则图中结点a->b的权值为2，b->a的权值为1/2。我们以这种方式建图，最终我们获取方程式a/b的结果，就是从a到b的路径权值的成绩。利用dfs深搜找到该条路径。详细过程见代码
代码
vector
<double> ans
;
unordered_map
<string
,vector
<pair
<string
,double>>> group
;
unordered_map
<string
,int> visit
;
bool flag
;
void dfs(double conclude
,string
& now
,string
& des
){
if(group
.count(now
)!=0 && now
== des
){
ans
.push_back(conclude
);
flag
= true;
}else{
vector
<pair
<string
,double>>::iterator iter
= group
[now
].begin();
while(iter
!=group
[now
].end() && !flag
){
if(visit
[(*iter
).first
] == 0){
visit
[(*iter
).first
] = 1;
dfs(conclude
*((*iter
).second
),(*iter
).first
,des
);
visit
[(*iter
).first
] = 0;
}
iter
++;
}
}
}
vector
<double> calcEquation(vector
<vector
<string
>>& equations
, vector
<double>& values
, vector
<vector
<string
>>& queries
) {
int n
= equations
.size();
for(int i
=0; i
<n
; i
++){
group
[equations
[i
][0]].push_back(make_pair(equations
[i
][1],values
[i
]));
group
[equations
[i
][1]].push_back(make_pair(equations
[i
][0],1/values
[i
]));
}
n
= queries
.size();
for(int i
=0; i
<n
; i
++){
flag
= false;
dfs(1,queries
[i
][0],queries
[i
][1]);
if(!flag
) ans
.push_back(-1.0);
}
return ans
;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/evaluate-division 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
