Modified 2 solutions

varunu28 · varunu28 · commit f0fa96979c05 · 2020-02-03T18:14:13.000-08:00
diff --git a/Easy/Number of Equivalent Domino Pairs.java b/Easy/Number of Equivalent Domino Pairs.java
@@ -1,16 +1,23 @@
 class Solution {
-    public int numEquivDominoPairs(int[][] dominoes) {
-        Map<String, Integer> map = new HashMap <>();
-        for (int i = 0; i < dominoes.length; i++) {
-            String key = Math.min(dominoes[i][0], dominoes[i][1]) + "|" + Math.max(dominoes[i][0], dominoes[i][1]);
-            map.put(key, map.getOrDefault(key, 0) + 1);
+  public int numEquivDominoPairs(int[][] dominoes) {
+    int count = 0;
+    Map<String, Integer> map = new HashMap<>();
+    for (int i = 0; i < dominoes.length; i++) {
+      String straightKey = dominoes[i][0] + "/" + dominoes[i][1];
+      String revKey = dominoes[i][1] + "/" + dominoes[i][0];
+      if (map.containsKey(straightKey)) {
+        count += map.get(straightKey);
+      }
+      else if (!straightKey.equals(revKey)) {
+        if (map.containsKey(revKey)) {
+          count += map.get(revKey);
         }
-        
-        int count = 0;
-        for (int value : map.values()) {
-            count += (value * (value - 1)) / 2;
-        }
-        
-        return count;
+      }
+      map.put(straightKey, map.getOrDefault(straightKey, 0) + 1);
+      if (dominoes[i][0] != dominoes[i][1]) {
+        map.put(revKey, map.getOrDefault(revKey, 0) + 1);
+      }
     }
+    return count;
+  }
 }
diff --git a/Medium/Evaluate Division.java b/Medium/Evaluate Division.java
@@ -1,73 +1,44 @@
 class Solution {
-    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
-        double[] ans = new double[queries.size()];
-
-        Map<String, Set<String>> map = new HashMap<>();
-        Map<String, Double> resMap = new HashMap<>();
-
-        for (int i = 0; i < equations.size(); i++) {
-            String operand1 = equations.get(i).get(0);
-            String operand2 = equations.get(i).get(1);
-
-            map.computeIfAbsent(operand1, k -> new HashSet<>()).add(operand2);
-            map.computeIfAbsent(operand2, k -> new HashSet<>()).add(operand1);
-
-            resMap.put(operand1 + "|" + operand2, values[i]);
-        }
-
-        for (int i = 0; i < queries.size(); i++) {
-            String operand1 = queries.get(i).get(0);
-            String operand2 = queries.get(i).get(1);
-
-            if (!map.containsKey(operand1) || !map.containsKey(operand2)) {
-                ans[i] = -1.0;
-            }
-            else if (operand1.equals(operand2)) {
-                ans[i] = 1.0;
-            }
-            else if (map.get(operand1).contains(operand2)) {
-                ans[i] = getSimpleDivisionVal(resMap, operand1, operand2);
-            }
-            else if (operand2.contains(operand1)) {
-                ans[i] = getSimpleDivisionVal(resMap, operand2, operand1);
-            }
-            else {
-                ans[i] = dfs(map, resMap, operand1, operand2, 1.0, new HashSet<>());
-            }
-        }
-
-        return ans;
+  public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
+    Map<String, List<String>> map = new HashMap<>();
+    Map<String, List<Double>> valueMap = new HashMap<>();
+    for (int i = 0; i < equations.size(); i++) {
+      List<String> equation = equations.get(i);
+      map.computeIfAbsent(equation.get(0), k -> new ArrayList<>()).add(equation.get(1));
+      map.computeIfAbsent(equation.get(1), k -> new ArrayList<>()).add(equation.get(0));
+      valueMap.computeIfAbsent(equation.get(0), k -> new ArrayList<>()).add(values[i]);
+      valueMap.computeIfAbsent(equation.get(1), k -> new ArrayList<>()).add(1 / values[i]);      
     }
-
-    private double dfs (Map<String, Set<String>> map, Map<String, Double> resMap, String operand1, String operand2,
-                        double base, Set<String> visited) {
-        if (visited.contains(operand1)) {
-            return -1.0;
-        }
-        if (map.get(operand1).contains(operand2)) {
-            return base * getSimpleDivisionVal(resMap, operand1, operand2);
-        }
-
-        visited.add(operand1);
-
-        double ans = -1.0;
-        Iterator<String> children = map.get(operand1).iterator();
-
-        while (children.hasNext()) {
-            String child = children.next();
-            if (!visited.contains(child)) {
-                ans = Math.max(ans, dfs(map, resMap, child, operand2, base * getSimpleDivisionVal(resMap, operand1, child), visited));
-            }
-        }
-
-        return ans;
+    double[] ans = new double[queries.size()];
+    for (int i = 0; i < queries.size(); i++) {
+      List<String> query = queries.get(i);
+      ans[i] = dfs(map, valueMap, query.get(0), query.get(1), new HashSet<>(), 1.0);
+      ans[i] = ans[i] == 0.0 ? -1.0 : ans[i];
     }
-
-    private double getSimpleDivisionVal (Map<String, Double> resMap, String operand1, String operand2) {
-        if (resMap.containsKey(operand1 + "|" + operand2)) {
-            return resMap.get(operand1 + "|" + operand2);
-        }
-
-        return 1 / resMap.get(operand2 + "|" + operand1);
+    return ans;
+  }
+  
+  private double dfs(Map<String, List<String>> map, Map<String, List<Double>> valueMap, String a, String b, Set<String> set, double curr) {
+    if (set.contains(a)) {
+      return 0.0;
     }
+    if (!map.containsKey(a)) {
+      return 0.0;
+    }
+    if (a.equals(b)) {
+      return curr;
+    }
+    set.add(a);
+    List<String> children = map.get(a);
+    List<Double> valueList = valueMap.get(a);
+    double temp = 0.0;
+    for (int i = 0; i < children.size(); i++) {
+      temp = dfs(map, valueMap, children.get(i), b, set, curr * valueList.get(i));
+      if (temp != 0.0) {
+        break;
+      }
+    }
+    set.remove(a);
+    return temp;
+  }
 }
