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.
代码模板是： public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { } 看一看这一题的其他测试用例：
我的思路是：用一个HashMap<String, HashMap<String,Double>> map，key存储被除数，value的map则存储 除数 和 计算的值。比如这样：
(x1,x2) (x2,x1) (x3,x1) (x4,x1) (x5,x3) (x1,x3) (x2,x4) (x3,x5) (x4,x2) (x1,x4) 求(x1,x5)) 就先map.get(x1)，得到的除数map中包含x2,x3,x4，发现x5不在其中。那么就遍历这个map，以map中的数作为“被除数”再次进行递归，直到发现除数map中包含x5为止。我们发现一个问题，比如以x2作为被除数进行再次递归时，得到的除数map中出现了1，与前面形成了一个环，如此递归将无穷循环下去，因此要有一个visited数组，一旦发现之前已经有x1作为被除数了，再次在除数map中出现x1时，要跳过去。
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { double[] result=new double[queries.length]; HashMap<String, HashMap<String,Double>> map=new HashMap<String, HashMap<String,Double>>(); for(int i=0;i<equations.length;i++){ String a=equations[i][0]; String b=equations[i][1]; HashMap<String, Double> m=map.getOrDefault(a, new HashMap<String, Double>()); m.put(b, values[i]); map.put(a, m); HashMap<String, Double> n=map.getOrDefault(b, new HashMap<String, Double>()); n.put(a, 1/values[i]); map.put(b, n); } for(int i=0;i<queries.length;i++){ String beichushu=queries[i][0]; String chushu=queries[i][1]; if(map.get(beichushu)==null||map.get(chushu)==null){ result[i]=-1.0; continue; } if(beichushu.equals(chushu)){ result[i]=1.0; continue; } if(map.get(beichushu).get(chushu)!=null){ result[i]=map.get(beichushu).get(chushu); continue; } HashSet<String> visited=new HashSet<String>(); result[i]=helper(beichushu, chushu, map,visited); } return result; } public double helper(String beichushu,String chushu, HashMap<String, HashMap<String,Double>> map,HashSet<String> visited){ visited.add(beichushu); HashMap<String, Double> tmp=map.get(beichushu); if(tmp.get(chushu)!=null){ return tmp.get(chushu); } else{ for(Entry<String, Double> entry:tmp.entrySet()){ String newBeichushu=entry.getKey(); if(visited.contains(newBeichushu)){ continue; } double val=helper(newBeichushu, chushu, map, visited); if(val!=-1){ return entry.getValue()*val; } } } visited.remove(beichushu); return -1; } 大神则想到了用“图"来解决，将每个String看做一个结点，如果两个String之间有计算关联的话，两者之间就是连通的。 而等式 A/B=k 就像图的边 A->B ，相应地， (A/B)*(B/C)*(C/D) 就像路径 A->B->C->D 一样。如果 a/b = 2.0 ， b/c = 3.0, 我们可以把a,b, and c 看做结点。 那么边 edge(a,b) 的权重是 2.0 ， edge(b,c) 的权重是 3.0 反过来， edge(b,a) 的权重是 1/2.0 ， edge(c,b)的权重是 1/3.0 那么 a,c 是a到c的路径， distance (a,c) = weight(a,b) * weight(b,c)
比如：
equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].构造一个图，就像这样:
["a","c"] = a -> b -> c = 2.0 * 3.0 = 6.0
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { double[] res = new double[queries.length]; if(equations.length == 0) return res; Map<String, List<Edge>> adjs = new HashMap(); for(int i=0;i<equations.length;i++){ String v = equations[i][0]; String u = equations[i][1]; Edge ef = new Edge(u, values[i]); Edge eb = new Edge(v, 1.0/values[i]); if(adjs.containsKey(v)){ adjs.get(v).add(ef); } else { List<Edge> adjsV = new ArrayList(); adjsV.add(ef); adjs.put(v, adjsV); } if(adjs.containsKey(u)){ adjs.get(u).add(eb); } else { List<Edge> adjsU = new ArrayList(); adjsU.add(eb); adjs.put(u, adjsU); } } for(int i=0;i<queries.length;i++){ String s = queries[i][0]; String t = queries[i][1]; Set<String> visited = new HashSet(); dfs(adjs,visited, s, t, 1.0,i, res); if(res[i] == 0 && s != t) res[i] = -1.0; } return res; } private void dfs(Map<String, List<Edge>> adjs,Set<String> visited, String s, String t, double distance, int index, double[] res){ if(s.equals(t)) { res[index] = distance; } if(visited.contains(s)) return; visited.add(s); if(!adjs.containsKey(s) || !adjs.containsKey(t)) { res[index] = -1.0; return; } List<Edge> adjsV = adjs.get(s); Iterator<Edge> iter = adjsV.iterator(); while(iter.hasNext()){ Edge e = iter.next(); dfs(adjs,visited, e.to, t, distance * e.weight,index, res); } } class Edge{ String to; double weight; Edge(String t, double w){ to = t; weight = w; } }感觉解法还是大同小异啊，只不过套上了”图“的外衣。
