Added 1 solution & modified 4 solutions

varunu28 · varunu28 · commit cbb1b6d96007 · 2020-08-10T18:10:41.000-05:00
diff --git a/Easy/Robot Return to Origin.java b/Easy/Robot Return to Origin.java
@@ -1,17 +1,14 @@
 class Solution {
-  Map<Character, int[]> map;
   public boolean judgeCircle(String moves) {
-    map = new HashMap<>();
-    map.put('U', new int[]{-1, 0});
-    map.put('D', new int[]{1, 0});
-    map.put('L', new int[]{0, -1});
-    map.put('R', new int[]{0, 1});
     int x = 0;
     int y = 0;
-    for (char c : moves.toCharArray()) {
-      int[] dir = map.get(c);
-      x += dir[0];
-      y += dir[1];
+    for (char move : moves.toCharArray()) {
+      if (move == 'U' || move == 'D') {
+        y += move == 'U' ? 1 : -1;
+      }
+      else {
+        x += move == 'L' ? -1 : 1;
+      }
     }
     return x == 0 && y == 0;
   }
diff --git a/Medium/Binary Search Tree Iterator.java b/Medium/Binary Search Tree Iterator.java
@@ -1,43 +1,53 @@
 /**
- * Definition for binary tree
+ * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
- *     TreeNode(int x) { val = x; }
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
  * }
  */
-
-public class BSTIterator {
-    Stack<TreeNode> stack;
-    public BSTIterator(TreeNode root) {
-        stack = new Stack<>();
-        pushLeft(root);
+class BSTIterator {
+  Stack<TreeNode> stack;
+  public BSTIterator(TreeNode root) {
+    stack = new Stack<>();
+    update(root);
+  }
+  
+  private void update(TreeNode node) {
+    if (node == null) {
+      return;
     }
-    
-    private void pushLeft(TreeNode root) {
-        while(root != null) {
-            stack.push(root);
-            root = root.left;
-        }
+    stack.add(node);
+    TreeNode leftNode = node.left;
+    while (leftNode != null) {
+      stack.add(leftNode);
+      leftNode = leftNode.left;
     }
+  }
 
-    /** @return whether we have a next smallest number */
-    public boolean hasNext() {
-        return !stack.isEmpty();
-    }
+  /** @return the next smallest number */
+  public int next() {
+    TreeNode node = stack.pop();
+    update(node.right);
+    return node.val;
+  }
 
-    /** @return the next smallest number */
-    public int next() {
-        TreeNode node = stack.pop();
-        pushLeft(node.right);
-        
-        return node.val;
-    }
+  /** @return whether we have a next smallest number */
+  public boolean hasNext() {
+    return !stack.isEmpty();
+  }
 }
 
 /**
- * Your BSTIterator will be called like this:
- * BSTIterator i = new BSTIterator(root);
- * while (i.hasNext()) v[f()] = i.next();
+ * Your BSTIterator object will be instantiated and called as such:
+ * BSTIterator obj = new BSTIterator(root);
+ * int param_1 = obj.next();
+ * boolean param_2 = obj.hasNext();
  */
diff --git a/Medium/Divide Two Integers.java b/Medium/Divide Two Integers.java
@@ -1,41 +1,32 @@
 class Solution {
-    public int divide(int dividend, int divisor) {
-        
-        boolean isNeg = false;
-        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
-            isNeg = true;
-        }
-        
-        int ans = 0;
-        
-        long Ldividend = Math.abs((long) dividend);
-        long Ldivisor = Math.abs((long) divisor);
-        
-        if (Ldivisor == 0) return Integer.MAX_VALUE;
-        if (Ldividend == 0 || (Ldividend < Ldivisor)) return 0;
-        
-        long quot = ldivide(Ldividend, Ldivisor);
-        
-        if(quot > Integer.MAX_VALUE) {
-            ans = isNeg == false ? Integer.MAX_VALUE : Integer.MIN_VALUE;
-        }
-        else {
-            ans = (int)(isNeg ? -quot : quot);
-        }
-        
-        return ans;
+  private static int HALF_INT_MIN = -1073741824;
+  public int divide(int dividend, int divisor) {
+    if (dividend == Integer.MIN_VALUE && divisor == -1) {
+      return Integer.MAX_VALUE;
     }
-    
-    private long ldivide(long ldividend, long ldivisor) {
-        if (ldividend < ldivisor) return 0;
-        
-        long sum = ldivisor;
-        long multiple = 1;
-        while ((sum+sum) <= ldividend) {
-            sum += sum;
-            multiple += multiple;
-        }
-
-        return multiple + ldivide(ldividend - sum, ldivisor);
+    int negatives = 2;
+    if (dividend > 0) {
+      negatives--;
+      dividend = -dividend;
     }
+    if (divisor > 0) {
+      negatives--;
+      divisor = -divisor;
+    }
+    int quotient = 0;
+    while (divisor >= dividend) {
+      int powerOfTwo = -1;
+      int value = divisor;
+      while (value >= HALF_INT_MIN && value + value >= dividend) {
+        value += value;
+        powerOfTwo += powerOfTwo;
+      }
+      quotient += powerOfTwo;
+      dividend -= value;
+    }
+    if (negatives != 1) {
+      return -quotient;
+    }
+    return quotient;
+  }
 }
diff --git a/Medium/Is Graph Bipartite.java b/Medium/Is Graph Bipartite.java
@@ -1,29 +1,27 @@
 class Solution {
-    public boolean isBipartite(int[][] graph) {
-        int[] colors = new int[graph.length];
-        Arrays.fill(colors, -1);
+  public boolean isBipartite(int[][] graph) {
+    int n = graph.length;
+    int[] color = new int[n];
+    Arrays.fill(color, -1);
+    for (int i = 0; i < n; i++) {
+      if (color[i] == -1) {
         Stack<Integer> stack = new Stack<>();
-        
-        for (int i = 0; i < graph.length; i++) {
-            if (colors[i] == -1) {
-                stack.push(i);
-                colors[i] = 0;
-                
-                while (!stack.isEmpty()) {
-                    Integer removed = stack.pop();
-                    for (Integer connect : graph[removed]) {
-                        if (colors[connect] == -1) {
-                            stack.push(connect);
-                            colors[connect] = colors[removed] == 1 ? 0 : 1;
-                        }
-                        else if (colors[connect] == colors[removed]) {
-                            return false;
-                        }
-                    }
-                }
+        stack.push(i);
+        color[i] = 0;
+        while (!stack.isEmpty()) {
+          Integer node = stack.pop();
+          for (Integer neighbor : graph[node]) {
+            if (color[neighbor] == -1) {
+              stack.push(neighbor);
+              color[neighbor] = color[node] ^ 1;
             }
+            else if (color[neighbor] == color[node]) {
+              return false;
+            }
+          }
         }
-        
-        return true;
+      }
     }
+    return true;
+  }
 }
diff --git a/Medium/Most Stones Removed with Same Row or Column.java b/Medium/Most Stones Removed with Same Row or Column.java
@@ -0,0 +1,22 @@
+class Solution {
+  public int removeStones(int[][] stones) {
+    Set<int[]> visited = new HashSet<>();
+    int numOfIslands = 0;
+    for (int[] stone : stones) {
+      if (!visited.contains(stone)) {
+        dfs(stones, visited, stone);
+        numOfIslands++;
+      }
+    }
+    return stones.length - numOfIslands;
+  }
+  
+  private void dfs(int[][] stones, Set<int[]> visited, int[] stone) {
+    visited.add(stone);
+    for (int[] st : stones) {
+      if ((st[0] == stone[0] || st[1] == stone[1]) && !visited.contains(st)) {
+        dfs(stones, visited, st);
+      }
+    }
+  }
+}
