本文主要是介绍LeetCode：Evaluate Division，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Equations are given in the format A / B = k, whereA andB are variables represented as strings, andk is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, where equations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],values = [2.0, 3.0],queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
思路：
按题意，输入很多a/b，b/c等的除法等式，然后再输入一些新的式子，看能否从已有的等式当中推理出结果，能的话就输出结果，不能的话就输出-1.0。值得注意的是，x/x=-1.0，虽然题目已经确保了x不为0，按照实际上答案应该是1.0，但题目的例子输出为-1.0，这说明一定要从给出的式子来推理。
这道题首先需要做的工作是，已知a/b=k的情况下，推断出b/a=1/k的情况。将所有a作为被除数的情况下能作为除数的全部集合起来。
然后就有搜索的方式（我用的是DFS），搜索有没有一个这样的链：a/c = a/x1 x1/x2 x2/x3*…..*xn/c ，这样就能推导出最终的结果了。
首先将图初始化，from和to都存入双向mp中；然后开始对每一个queries进行dfs；如果有一个query不存在于mp里，就在answer中放入-1.0，否则说明可以到达，开始dfs：如果from = to 则放入-1.0，否则进行dfs。在dfs中，首先看是否可以直达，是的话就返回val× mp[from][to]，然后对所有的from可达的点进行判断，如果访问过了，就pass，否则就记录访问过该点，然后继续进行下一层的dfs。
代码：
class Solution {
public:vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {unordered_map<string, unordered_map<string, double>> mp;for (int i = 0; i < equations.size(); i++) {string from = equations[i].first;string to = equations[i].second;mp[from][to] = values[i];mp[to][from] = 1.0 / values[i];}vector<double> answer;for (int i = 0; i < queries.size(); i++) {string from = queries[i].first;string to = queries[i].second;if (mp.count(from) && mp.count(to)) {if (from == to) {answer.push_back(1.0);continue;} else {unordered_set<string> visited;answer.push_back(dfs(from, to, mp, visited, 1.0));}} else {answer.push_back(-1.0);}}return answer;}double dfs(string from, string to, unordered_map<string, unordered_map<string, double>> &mp, unordered_set<string> & visited, double value) {if (mp[from].count(to)) {return mp[from][to] * value;}for (pair<string, double> p : mp[from]) {if (visited.count(p.first) == 0) {visited.insert(p.first);double c = dfs(p.first, to, mp, visited, value * p.second);if (c != -1.0) return c;}}return -1.0;}
};
class Solution {
public:vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {unordered_map<string, unordered_map<string, double>> mp;for (int i = 0; i < equations.size(); i++) {string from = equations[i].first;string to = equations[i].second;mp[from][to] = values[i];mp[to][from] = 1.0 / values[i];}vector<double> answer;for (int i = 0; i < queries.size(); i++) {string from = queries[i].first;string to = queries[i].second;if (mp.count(from) && mp.count(to)) {if (from == to) {answer.push_back(1.0);continue;} else {unordered_set<string> visited;answer.push_back(dfs(from, to, mp, visited, 1.0));}} else {answer.push_back(-1.0);}}return answer;}double dfs(string from, string to, unordered_map<string, unordered_map<string, double>> &mp, unordered_set<string> & visited, double value) {if (mp[from].count(to)) {return mp[from][to] * value;}for (pair<string, double> p : mp[from]) {if (visited.count(p.first) == 0) {visited.insert(p.first);double c = dfs(p.first, to, mp, visited, value * p.second);if (c != -1.0) return c;}}return -1.0;}
};
这篇关于LeetCode：Evaluate Division的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
