2ms, Two HashMap solution.


  • 0
    H

    My idea is very straight.
    Just assign each variable with an actual value.
    To avoid value conflict, we also need to separate them into different group.
    For example, a / b = 3, c / d = 2.
    a = 3,
    b = 1,
    c = 2,
    d = 1
    groups[a, b] [c,d]

    So two HashMap are needed, one is for grouping, one is for assigning actual value.

    '''

    public class Solution {
    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() 
                       || (q.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); //throw back to the queue
            }
        }
        
        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.