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.
package com.graph; import java.util.*; public class Solution { double[] res; Map<String, Map<String, Double>> map; Map<String, Integer> visited; int find; double value; public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { //special case if(queries==null || queries.length==0 || equations==null || equations.length==0) return new double[0]; //normal case //build the graph int m = equations.length; map = new HashMap<String, Map<String, Double>>(); //Set<String> set = new HashSet<String>(); for(int i=0; i<m; i++){ String a = equations[i][0]; String b = equations[i][1]; if(!map.containsKey(a)){ map.put(a, new HashMap<String, Double>()); } map.get(a).put(b, values[i]); if(!map.containsKey(b)){ map.put(b, new HashMap<String, Double>()); } map.get(b).put(a, 1.0/values[i]); //get unique varaible } //for each query int n = queries.length; res = new double[n]; for(int i=0; i<n; i++){ //dfs value = 1.0; find = 0; visited = initVisited(equations); String cur = queries[i][0]; String tar = queries[i][1]; //容易忽略这一步 if(!visited.containsKey(cur) || !visited.containsKey(tar)) { res[i] = -1.0; continue; } visited.put(cur, 1); dfs(cur, tar); if(find==1) res[i] = value; else res[i] = -1.0; } return res; } public Map<String, Integer> initVisited(String[][] equations) { Map<String, Integer> tvisit = new HashMap<String, Integer>(); for(int i=0; i<equations.length; i++) { tvisit.put(equations[i][0], 0); tvisit.put(equations[i][1], 0); } return tvisit; } public void dfs(String cur, String tar){ if(cur.equals(tar)){ find=1; return; } Map<String, Double> tmap = map.get(cur); for(Map.Entry<String, Double> tmp:tmap.entrySet()){ String next = tmp.getKey(); if(visited.get(next)==0){ visited.put(next,1); value*=tmp.getValue(); dfs(next, tar); if(find==1) return;//容易忽略这一步 value/=tmp.getValue(); visited.put(next,0); } } } public static void main(String[] args) { Solution s = new Solution(); s.calcEquation(new String[][] {{"a","b"},{"b","c"}}, new double[] {2.0,3.0}, new String[][] {{"a","c"},{"b","c"},{"a","e"},{"a","a"},{"x","x"}}); } }
