Added 4 solutions & modified 1 solution

varunu28 · varunu28 · commit ffe284e73ef5 · 2019-07-06T20:00:07.000-07:00
diff --git a/Easy/Defanging an IP Address.java b/Easy/Defanging an IP Address.java
@@ -0,0 +1,15 @@
+class Solution {
+    public String defangIPaddr(String address) {
+        StringBuilder sb = new StringBuilder();
+        for (char c : address.toCharArray()) {
+            if (c == '.') {
+                sb.append("[.]");
+            }
+            else {
+                sb.append(c);
+            }
+        }
+        
+        return sb.toString();
+    }
+}
diff --git a/Medium/Corporate Flight Bookings.java b/Medium/Corporate Flight Bookings.java
@@ -0,0 +1,24 @@
+class Solution {
+    public int[] corpFlightBookings(int[][] bookings, int n) {
+        int[] ans = new int[n];
+
+        for (int[] booking : bookings) {
+            int tickets = booking[2];
+            int from = booking[0];
+            int to = booking[1];
+
+            ans[from - 1] += tickets;
+            if (to < n) {
+                ans[to] -= tickets;
+            }
+        }
+
+        int currSum = 0;
+        for (int i = 0; i < n; i++) {
+            currSum += ans[i];
+            ans[i] = currSum;
+        }
+
+        return ans;
+    }
+}
diff --git a/Medium/Delete Nodes And Return Forest.java b/Medium/Delete Nodes And Return Forest.java
@@ -0,0 +1,50 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    List<TreeNode> forest;
+    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
+        forest = new ArrayList<>();
+        Set<Integer> toDelete = new HashSet<>();
+        for (int val : to_delete) {
+            toDelete.add(val);
+        }
+        
+        helper(root, toDelete);
+        
+        if (!toDelete.contains(root.val)) {
+            forest.add(root);
+        }
+        
+        return forest;
+    }
+    
+    private TreeNode helper(TreeNode root, Set<Integer> toDelete) {
+        if (root == null) {
+            return null;
+        }
+        
+        root.left = helper(root.left, toDelete);
+        root.right = helper(root.right, toDelete);
+        
+        if (toDelete.contains(root.val)) {
+            if (root.left != null) {
+                forest.add(root.left);
+            }
+            
+            if (root.right != null) {
+                forest.add(root.right);
+            }
+            
+            return null;
+        }
+        
+        return root;
+    }
+}
diff --git a/Medium/Random Pick Index.java b/Medium/Random Pick Index.java
@@ -0,0 +1,21 @@
+class Solution {
+    Map<Integer, List<Integer>> map = new HashMap();
+    Random rand;
+    public Solution(int[] nums) {
+        rand = new Random();
+        for (int i = 0; i < nums.length; i++) {
+            map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
+        }
+    }
+    
+    public int pick(int target) {
+        List<Integer> indexes = map.get(target);
+        return indexes.get(rand.nextInt(indexes.size()));
+    }
+}
+
+/**
+ * Your Solution object will be instantiated and called as such:
+ * Solution obj = new Solution(nums);
+ * int param_1 = obj.pick(target);
+ */
diff --git a/Medium/Random Pick With Weight.java b/Medium/Random Pick With Weight.java
@@ -1,33 +1,37 @@
 class Solution {
 
-    List<Integer> prefixSum;
-    int total;
-    Random rand;
+    int[] accumulatedSum;
+    Random random;
     public Solution(int[] w) {
-        prefixSum = new ArrayList<>();
-        total = 0;
-        for (int i=0; i<w.length; i++) {
-            total += w[i];
-            prefixSum.add(total);
+        random = new Random();
+        accumulatedSum = new int[w.length];
+        int currSum = 0;
+        for (int i = 0; i < w.length; i++) {
+            currSum += w[i];
+            accumulatedSum[i] = currSum;
         }
-        rand = new Random();
     }
     
     public int pickIndex() {
-        int target = rand.nextInt(total);
-        int i = 0;
-        int j = prefixSum.size() - 1;
-        while (i != j) {
-            int mid = (i+j)/2;
-            if (target >= prefixSum.get(mid)) {
-                i = mid + 1;
+        int target = random.nextInt(accumulatedSum[accumulatedSum.length - 1]) + 1;
+        return binarySearch(accumulatedSum, 0, accumulatedSum.length - 1, target);
+    }
+    
+    private int binarySearch(int[] arr, int left, int right, int target) {
+        while (left <= right) {
+            int mid = (left + right) / 2;
+            if (arr[mid] == target) {
+                return mid;
+            }
+            else if (arr[mid] > target) {
+                right = mid - 1;
             }
             else {
-                j = mid;
+                left = mid + 1;
             }
         }
         
-        return j;
+        return left;
     }
 }
 
