3ms, Two HashMap solution.


  • 0
    H

    My idea is just give each node with an actual value and seperate them into different group. So two HashMap are needed, one is for grouping, one is for assigning actual value.

    '''
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    HashMap<String, Double> hm = new HashMap<String,Double>();
    HashMap<String, Integer> group = new HashMap<String, Integer>();
    double[] res = new double[queries.length];
    Queue<Integer> q = new LinkedList<Integer>();

        for(int i = 0; i < equations.length; i++) {
            q.offer(i);
        }
        
        int count = 0, gid = 0;
        while(!q.isEmpty()) {
            int i = q.poll();
            String b = equations[i][1], a = equations[i][0];
            double num_a = 1.0, num_b = 1.0;
            
            if(hm.containsKey(b)) {
                num_a = hm.get(b) * values[i];
                hm.put(a,num_a);
                group.put(a, group.get(b));
            } else if (hm.containsKey(a)) {
                num_b = hm.get(a) / values[i];
                hm.put(b,num_b);
                group.put(b, group.get(a));
            } else if (hm.isEmpty() || (hm.size() == count)){
                gid ++;    // start a new group
                hm.put(b,num_b);
                group.put(b,gid);
                num_a = num_b * values[i];
                hm.put(a,num_a);
                group.put(a,gid);
                count = 0;
            } else {
                count++;
                q.offer(i);
            }
        }
        
        for(int i = 0; i < queries.length; i++) {
            String b = queries[i][1], a = queries[i][0];
            if(hm.containsKey(a) && hm.containsKey(b) && group.get(a) == group.get(b)) {
                res[i] = hm.get(a) / hm.get(b);
            } else {
                res[i] = -1.0;
            }
        }
        return res;
    }
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.