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:
再一次,VS上的结果是对的。LC结果不对。 哎。不管了
主要思路,就是递归找关系, 并把其结果乘积。
class Solution { public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { vector<double> res; int N = equations.size(); unordered_map<string, unordered_map<string, double>> map; for(int i =0;i<N;i++){ string dividend = equations[i][0]; string divisor = equations[i][1]; // include themselves map[dividend][dividend] = 1; map[divisor][divisor] = 1; double value = values[i]; map[dividend][divisor] = value; if(value != 0 ) // as equations can exist 0 / a = 0 map[divisor][dividend] = 1.0 / value; } unordered_set<string> usedStrings; for(auto query : queries){ res.push_back(dfs(query[0], query[1], map, usedStrings)); } return res; } private: double dfs(string a, string b, unordered_map<string, unordered_map<string, double>> &map, unordered_set<string> &usedStrings){ if(usedStrings.find(a) != usedStrings.end()){ return -1; } if(map[a].find(b) != map[a].end()){ return map[a][b]; }else{ usedStrings.insert(a); double res = -1; auto iter = map[a].begin(); while(iter!= map[a].end()){ res = (iter->second) * dfs(iter->first, b, map, usedStrings); if(res != -1){ break; } iter++; } usedStrings.erase(a); return res; } } };
Errors:
1: map里由于我保存了 a->b b -> a 这样会造成循环
2: 再就是double 给写成 long, 肏
No comments:
Post a Comment