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.
解题思路：想到要用图做后，第一个问题是如何转换string来实现图的储存和查找，当时没动脑子就用了特别复杂的办法（先用map做string和int的对应，然后暴力floyd方法遍历邻接矩阵得到答案），但是这样的程序时间复杂度近似是O（n^3），太过于繁琐），度娘了一下才发现自己再多想一下可以用map< string,map<string,double>的数据结构来保存图，然后对于每一个询问，应用dfs来查询是否存在路径，这样时间复杂度降低到了大约O（n^2).
代码如下：
class Solution { public: vector<double> calcEquation(vector<pair<string, string> > equations, vector<double>& values, vector<pair<string, string> > queries) { map<string,int> note; int count=0; double map[100][100]; for(int i=0;i<100;i++) { for(int p=0;p<100;p++) map[i][p]=1000000; } for(int i=0;i<equations.size();i++) { if(note.end()==note.find(equations[i].first)) { note[equations[i].first]=count; count++; } if(note.end()==note.find(equations[i].second)) { note[equations[i].second]=count; count++; } map[note[equations[i].first]] [note[equations[i].second]]=values[i]; //cout<<map[note[equations[i].first]] [note[equations[i].second]]<<endl; map[note[equations[i].second]] [note[equations[i].first]]=1/values[i]; //cout<<map[note[equations[i].second]] [note[equations[i].first]]<<endl; } for(int i=0;i<queries.size();i++) { if(note.end()==note.find(queries[i].first)) { note[queries[i].first]=count; count++; } if(note.end()==note.find(queries[i].second)) { note[queries[i].second]=count; count++; } } for(int i=0;i<count;i++) { for(int p=0;p<count;p++) { for(int q=0;q<count;q++) { if(map[p][q]>map[p][i]*map[i][q]&&map[p][i]!=1000000&&map[i][q]!=1000000) { map[p][q]=map[p][i]*map[i][q]; } } } } vector<double> ans; for(int i=0;i<queries.size();i++) { //cout<<map[note[queries[i].first]][note[queries[i].second]]<<endl; if(map[note[queries[i].first]][note[queries[i].second]]==1000000) { ans.push_back(-1.0); //cout<<map[note[queries[i].first]][note[queries[i].second]]<<endl; } else { ans.push_back(map[note[queries[i].first]][note[queries[i].second]]); //cout<<map[note[queries[i].first]][note[queries[i].second]]<<endl; } } return ans; } };
后记：这是未修改之前的代码主要是在于floyd算法的使用，代码简洁复杂度却很高，还有就是自己没有想清楚如何用map导致储存图的时候代码繁琐，这也提示自己并不是只有邻接表和邻接矩阵可以储存图（思维定式），有时候用map更高效和简洁。
