LeetCode Evaluate Division Equations are given in the format A / B = k, where A and B are variables represented as strings, and k 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. Return vector<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=2.0,b/c=3.0，问a/c=?。 本题的解法是把一系列表达式转换为图，比如a/b=2.0转换为a指向b的边，边的值为2.0，同时b指向a的边的值为1/2.0。如果要求a/c，则在图中找一条a到c的边，并且把走过的边的值乘起来。 构建图的过程先把表达式中的string编码成int，然后把已知的直连边加入到图中。对于要查询的边start/target，首先判断一下两个端点是否在图中，如果至少有一个端点不在图中，则无法求值，返回-1。否则，在图中DFS或BFS找到target，走过的路径乘积就是结果。 题目说明所有values都是正数，所以不存在除0问题。 DFS代码如下： [cpp] class Solution { private: bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) { graph[start][y] = graph[start][x] * graph[x][y]; graph[y][start] = 1.0 / graph[start][y]; if(y == target)return true; int n = graph.size(); for(int i = 0; i < n; ++i){ if(graph[start][i] == 0 && graph[y][i] != 0){ if(dfs(graph, start, y, i, target))return true; } } return false; } double helper(vector<vector<double>>& graph, int start, int target) { if (start == target)return 1.0; else if (graph[start][target] != 0.0)return graph[start][target]; int n = graph.size(); for (int y = 0; y < n; ++y) { if (y == start)continue; if (graph[start][y] != 0.0) { if (dfs(graph, start, start, y, target))return graph[start][target]; } } return -1.0; } public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { int cnt = 0, n = equations.size(); unordered_map<string, int> hash; for (int i = 0; i < n; ++i) { if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++; if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++; } vector<vector<double>> graph(cnt, vector<double>(cnt, 0)); for (int i = 0; i < n; ++i) { int x = hash[equations[i].first], y = hash[equations[i].second]; graph[x][x] = 1; graph[y][y] = 1; graph[x][y] = values[i]; graph[y][x] = 1.0 / values[i]; } vector<double> ans; for (int i = 0; i < queries.size(); ++i) { if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0); else { int x = hash[queries[i].first], y = hash[queries[i].second]; ans.push_back(helper(graph, x, y)); } } return ans; } }; [/cpp] 本代码提交AC，用时3MS。 BFS代码如下： [cpp] class Solution { private: double bfs(vector<vector<double>>& graph, int start, int target) { if (start == target)return 1.0; else if (graph[start][target] != 0.0)return graph[start][target]; int n = graph.size(); queue<int> q; for(int x = 0; x < n; ++x){ if(x != start && graph[start][x] != 0)q.push(x); } while(!q.empty()){ int x = q.front(); if(x == target) return graph[start][target]; q.pop(); for(int y = 0; y < n; ++y){ if(graph[start][y] == 0 && graph[x][y] != 0){ graph[start][y] = graph[start][x] * graph[x][y]; graph[y][start] = 1.0 / graph[start][y]; q.push(y); } } } return -1.0; } public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { int cnt = 0, n = equations.size(); unordered_map<string, int> hash; for (int i = 0; i < n; ++i) { if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++; if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++; } vector<vector<double>> graph(cnt, vector<double>(cnt, 0)); for (int i = 0; i < n; ++i) { int x = hash[equations[i].first], y = hash[equations[i].second]; graph[x][x] = 1; graph[y][y] = 1; graph[x][y] = values[i]; graph[y][x] = 1.0 / values[i]; } vector<double> ans; for (int i = 0; i < queries.size(); ++i) { if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0); else { int x = hash[queries[i].first], y = hash[queries[i].second]; ans.push_back(bfs(graph, x, y)); } } return ans; } }; [/cpp] 本代码提交AC，用时0MS，类似的题BFS显然要比DFS快，而且这题用BFS思路更清晰。]]>