2ms java solution used the idea from group problem


  • 0
    T
    public class Solution {
        class Pair{
            int n;
            double v;
            public Pair(int a, double b){
                n = a;
                v = b;
            }
        }
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            List<Pair> list = new ArrayList<>();
            HashMap<String, Integer> map = new HashMap<>();
            for(int i = 0; i < equations.length; i++){
                String[] str = equations[i];
                if(!map.containsKey(str[0])){
                    map.put(str[0], list.size());
                    list.add(new Pair(list.size(), 1.0));
                }
                if(!map.containsKey(str[1])){
                    map.put(str[1], list.size());
                    list.add(new Pair(list.size(), 1.0));
                }
                int n1 = map.get(str[0]);
                int n2 = map.get(str[1]);
                Pair a = findgroup(list, list.get(n1));
                Pair b = findgroup(list, list.get(n2));
                if(a.n < b.n) {
                    b.n = a.n;
                    b.v = a.v / values[i];
                }
                else if(a.n > b.n) {
                    a.n = b.n;
                    a.v = b.v * values[i];
                }
            }
            double[] ret = new double[queries.length];
            for(int i = 0; i < queries.length; i++){
                String s1 = queries[i][0];
                String s2 = queries[i][1];
                if(!map.containsKey(s1) || !map.containsKey(s2)){
                    ret[i] = -1.0;
                    continue;
                }
                int n1 = map.get(s1);
                int n2 = map.get(s2);
                Pair a = findgroup(list, list.get(n1));
                Pair b = findgroup(list, list.get(n2));
                if(a.n != b.n){
                    ret[i] = -1.0;
                    continue;
                }
                ret[i] = a.v / b.v;
            }
            
            return ret;
        }
        public Pair findgroup(List<Pair> list, Pair p){
            if(p.n == list.get(p.n).n) return p;
            p.v *= list.get(p.n).v;
            p.n =list.get(p.n).n;
            return findgroup(list, p);
        }
    }
    

Log in to reply
 

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