399. Evaluate Division

https://leetcode.com/problems/evaluate-division/
输入为：

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],

要求输出为：

queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
ans = [6.0,3.0,-1.0,1.0,-1.0]

有两种做法：
建图法，后BFS搜索；这种方法建图方法简单耗时少，但查询耗时长；

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        HashMap<String, Node> graph = buildGraph(equations, values);
        double[] ans = new double[queries.length];
        for(int j = 0; j < queries.length; j++){
            String node1 = queries[j][0];
            String node2 = queries[j][1];
            if(!graph.containsKey(node1) || !graph.containsKey(node2)){
                ans[j] = -1.0d;
            }
            else{
                ans[j] = graphFind(graph.get(node1), graph.get(node2));
            }
        }
        return ans;
    }

    private double graphFind(Node start, Node end){
        Set<String> visited = new HashSet<>();
        Queue<Node> nodeQ = new LinkedList<>();
        Queue<Double> distance = new LinkedList<>();
        nodeQ.add(start);
        distance.add(1.0d);
        while(nodeQ.size() > 0){
            Node tmp = nodeQ.poll();
            double dis = distance.poll();
            if(tmp.name.equals(end.name)){
                return dis;
            }
            for(Node node: tmp.getMap().keySet()){
                if(!visited.contains(node.name)){
                    nodeQ.add(node);
                    distance.add(dis * tmp.getMap().get(node));
                    visited.add(node.name);
                }
            }

        }
        return -1.0d;
    }

    class Node{
        String name;
        HashMap<Node, Double> map;
        public Node(String name){
            this.name = name;
            this.map = new HashMap<>();
        }

        private void assign(Node node, double dis){
            this.map.put(node, dis);
        }

        HashMap<Node, Double> getMap(){
            return this.map;
        }
    }

    private HashMap<String, Node> buildGraph(String[][] equations, double[] values){
        HashMap<String, Node> graph = new HashMap<>();
        for(int i = 0; i < equations.length; i++){
            String node1 = equations[i][0];
            String node2 = equations[i][1];
            if(!graph.containsKey(node1)){
                graph.put(node1, new Node(node1));
            }
            if(!graph.containsKey(node2)){
                graph.put(node2, new Node(node2));
            }
            graph.get(node1).assign(graph.get(node2), values[i]);
            graph.get(node2).assign(graph.get(node1), 1.0d/values[i]);
        }
        return graph;
    }
}

建表法，将所有可能的结果存储进HashMap，建表耗时长，查询耗时短(仅为O(1));

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if(equations.length == 0){return values;}
        List<HashMap<String, Double>> valueMap = new ArrayList<HashMap<String, Double>>();
        // valueMap.add(new HashMap<String, Double>());
        for(int i=0; i < equations.length; i++){
            boolean flag = false;
            for(HashMap<String, Double> tmp: valueMap){
                if(tmp.containsKey(equations[i][0])){
                    System.out.println(tmp.get(equations[i][0]).getClass().getName());
                    tmp.put(equations[i][1], (tmp.get(equations[i][0]).doubleValue() / values[i]));
                    flag = true;
                    break;
                }
                else if(tmp.containsKey(equations[i][1])){
                    tmp.put(equations[i][0], (tmp.get(equations[i][1]).doubleValue() * values[i]));
                    flag = true;
                    break;
                }
            }
            if(!flag){
                HashMap<String, Double> newMap = new HashMap<>();
                newMap.put(equations[i][1], 1.0d);
                newMap.put(equations[i][0], values[i]);
                valueMap.add(newMap);
            }
        }
        // System.out.println(valueMap.size());
        // for(HashMap tmp: valueMap){
        //     System.out.println(tmp);
        // }
        
        
        combineMap(valueMap);
        double[] ans = new double[queries.length];
        int mapLength = valueMap.size();
        for(int i = 0; i < queries.length; i++){
            boolean getValue = false;
            for(int j = 0; j < mapLength; j++){
                if(valueMap.get(j).containsKey(queries[i][0]) && valueMap.get(j).containsKey(queries[i][1])){
                    ans[i] = valueMap.get(j).get(queries[i][0])/ valueMap.get(j).get(queries[i][1]);
                    getValue = true;
                }
            }
            if(!getValue){
                ans[i] = -1.0d;
            }

//            if(valueMap.get(0).containsKey(queries[i][0]) && valueMap.get(0).containsKey(queries[i][1])){
//                ans[i] = valueMap.get(0).get(queries[i][0])/ valueMap.get(0).get(queries[i][1]);
//            }
//            else{
//                ans[i] = -1.0d;
//            }
        }
        return ans;
    }
    
    private void combineMap(List<HashMap<String, Double>> listMap){
        Set<Integer> skip = new HashSet<>();
        for(int i = 0; i < listMap.size(); i++){
            if(skip.contains(i)){
                continue;
            }
            for(int j = i; j < listMap.size(); j++){
                if(skip.contains(j)){
                    continue;
                }
                if(combineMapHelper(listMap, i,j)){
                    skip.add(j);
                }
            }
        }
        List<Integer> array = new ArrayList<>();
        for(int i : skip){
            array.add(i);
        }
        Collections.sort(array, Collections.reverseOrder());
        for(int j = 0; j < array.size(); j++){
            listMap.remove(array.get(j));
        }
    }

    private boolean combineMapHelper(List<HashMap<String, Double>> listMap, int i, int j){
        HashMap<String, Double> map1 = listMap.get(i);
        HashMap<String, Double> map2 = listMap.get(j);
        Set<String> set1 = map1.keySet();
        Set<String> set2 = map2.keySet();
        String pointer = "";
        for(String tmp: set1){
            if(set2.contains(tmp)){
                pointer = tmp;
                break;
            }
        }
        if(pointer == ""){
            return false;
        }
        for(String tmp: set2){
            map1.put(tmp, (map1.get(pointer).doubleValue()/map2.get(pointer).doubleValue())*map2.get(tmp));
        }
        return true;
    }
    
//     private void combineMap(List<Map<String, Integer>> listMap){
//         if(listMap.size() == 0){
//             return listMap;
//         }
        
//     }
}

代码都比较繁琐，也都涉及到非常多的语法问题；之后有时间再来修缮。