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
public class Solution { public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { HashMap<String, ArrayList<String>> strmap = new HashMap<String, ArrayList<String>>(); HashMap<String, ArrayList<Double>> valmap = new HashMap<String, ArrayList<Double>>(); for (int i = 0; i < equations.length; i++) { String[] equation = equations[i]; double weight = values[i]; if(!strmap.containsKey(equation[0])) { strmap.put(equation[0], new ArrayList<String>()); valmap.put(equation[0], new ArrayList<Double>()); } if(!strmap.containsKey(equation[1])) { strmap.put(equation[1], new ArrayList<String>()); valmap.put(equation[1], new ArrayList<Double>()); } strmap.get(equation[0]).add(equation[1]); strmap.get(equation[1]).add(equation[0]); valmap.get(equation[0]).add(weight); valmap.get(equation[1]).add(1.0/weight); } double[] res = new double[queries.length]; for (int i = 0; i < res.length; i++) { String start = queries[i][0]; String end = queries[i][1]; res[i] = dfs(strmap, valmap, start, end, new HashSet<String>(), 1.0); if(res[i] == 0.0) res[i] = -1.0; } return res; } public double dfs(HashMap<String, ArrayList<String>> strmap, HashMap<String, ArrayList<Double>> valmap, String start, String end, HashSet<String> set, double val) { if(set.contains(start)) return 0.0; if(!strmap.containsKey(start)) return 0.0; if(start.equals(end)) return val; set.add(start); double tmp = 0.0; ArrayList<String> strlist = strmap.get(start); ArrayList<Double> vallist = valmap.get(start); for (int i = 0; i < strlist.size(); i++) { tmp = dfs(strmap, valmap, strlist.get(i), end, set, val*vallist.get(i)); if(tmp != 0.0) break; } //set.remove(start); return tmp; }}新闻热点
疑难解答
