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.

一刷
题解：
一种最简单的做法：
构建一个map<String, HashMap<String, Double>>, key为分子，value为<分母， value>. 然后有个对称的，比如<a, <b,2>>, <b, <a,0.5>>。并且每次加入一个equation, 就一次迭代分子，分母的map. 最后只用在map里面查表即可。

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        HashMap<String, HashMap<String, Double>> map = new HashMap<>();
        for(int i=0; i<equations.length; i++) {
            String[] eq = equations[i]; 
            if(!map.containsKey(eq[0]))
                map.put(eq[0], new HashMap<>());
            if(!map.containsKey(eq[1]))
                map.put(eq[1], new HashMap<>());
            
            HashMap<String, Double> map0 = map.get(eq[0]);
            HashMap<String, Double> map1 = map.get(eq[1]);
            map0.put(eq[1], values[i]);
            map1.put(eq[0], 1/values[i]);
            
            insert(map, eq[0], eq[1], values[i]);
        }
        int len = queries.length;
        double[] re = new double[len];
        for(int i=0; i<len; i++) {
            String[] qu = queries[i];
            if(!map.containsKey(qu[0]) || !map.get(qu[0]).containsKey(qu[1]))
                re[i] = -1;
            else {
                re[i] = map.get(qu[0]).get(qu[1]);
            }
        }
        return re;
    }
    
    private void insert(HashMap<String, HashMap<String, Double>> map, String a, String b, double value) {
        HashMap<String, Double> map0 = map.get(a);
        HashMap<String, Double> map1 = map.get(b);
        for( String key : map1.keySet()) {
            double val = map1.get(key)*value;
            if(!map0.containsKey(key)){
                map0.put(key, val);
                map.get(key).put(a, 1/val);
                insert(map, a, key, val);
            }
        }
        for( String key : map0.keySet()) {
            double val = map0.get(key)/value;
            if(!map1.containsKey(key)){
                map1.put(key, val);
                map.get(key).put(b, 1/val);
                insert(map, b, key, val);
            }
        }
    }
}

Speed up
相当于给了root一个基准值，如果a/b=2, 那么b->a (在root中)，在b=2, a=1(value map中)

于是得到了每个character对应的root

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if(equations==null || equations.length==0) return new double [] {};
        
        Map<String, String>root=new HashMap<>();
        Map<String, Double>map=new HashMap<>();
        
        for (int i=0;i<equations.length;i++){
            String x1=equations[i][0], x2=equations[i][1];
            root.putIfAbsent(x1, x1);
            root.putIfAbsent(x2, x2);
            map.putIfAbsent(x1, 1.0);
            map.putIfAbsent(x2, 1.0);
            
            String r1=find(root, x1);
            String r2=find(root, x2);
            root.put(r2, r1);
            map.put(r2, map.get(x1)*values[i]/map.get(x2));
        }

        double[] res=new double[queries.length];
        for (int i=0;i<queries.length;i++){
            //res[i]=-1.0;
            String x1=queries[i][0], x2=queries[i][1];
            if (!root.containsKey(x1) || !root.containsKey(x2)) continue;
            String r1=find(root, x1);
            String r2=find(root, x2);
            if (r1.equals(r2))
                res[i]=get(root, map, x2) / get(root, map, x1);
        }
        return res;
    }
    
    private String find(Map<String, String>root, String var){
        if (root.get(var).equals(var)) return var;
        return find(root, root.get(var));
    }
    
    private double get(Map<String, String>root, Map<String, Double>map, String var){
        String r=root.get(var);
        double result=map.get(var);
        
        if (r.equals(var)) return result;
        return result*get(root, map, r);
    }

}

要用图算法来解，因为(A/B)(B/C)(C/D) is like the path A->B->C->D。例如Floyd-Warshall算法是解决两点间的最短路径的一种算法。

Floyd-Algorithm