week 3

sunshead · sunshead · commit 2e4207fcbfc0 · 2020-06-28T00:59:14.000-04:00
diff --git a/Week03/problems/105_construct-binary-tree-from-preorder-and-inorder-traversal.java b/Week03/problems/105_construct-binary-tree-from-preorder-and-inorder-traversal.java
@@ -0,0 +1,21 @@
+class Solution {
+    public TreeNode buildTree(int[] preorder, int[] inorder) {
+        return helper(0, 0, inorder.length - 1, preorder, inorder);
+    }
+
+    private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
+        if (preStart > preorder.length - 1 || inStart > inEnd) {
+            return null;
+        }
+        TreeNode root = new TreeNode(preorder[preStart]);
+        int inIndex = 0;
+        for (int i = inStart; i <= inEnd; i++) {
+            if (inorder[i] == root.val) {
+                inIndex = i;
+            }
+        }
+        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
+        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
+        return root;
+    }
+}
diff --git a/Week03/problems/236_lowest-common-ancestor-of-a-binaty-tree.java b/Week03/problems/236_lowest-common-ancestor-of-a-binaty-tree.java
@@ -0,0 +1,39 @@
+class Solution {
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+        // Stack for tree traversal
+        Deque<TreeNode> stack = new ArrayDeque<>();
+        stack.push(root);
+
+        // HashMap for parent pointers
+        Map<TreeNode, TreeNode> parents = new HashMap<>();
+        parents.put(root, null);
+
+        // interate until both p and q are found
+        while (!parents.containsKey(p) || !parents.containsKey(q)) {
+            TreeNode curr = stack.pop();
+            if (curr.left != null) {
+                parents.put(curr.left, curr);
+                stack.push(curr.left);
+            }
+            if (curr.right != null) {
+                parents.put(curr.right, curr);
+                stack.push(curr.right);
+            }
+        }
+
+        // ancestors set for p
+        Set<TreeNode> ancestors = new HashSet<>();
+
+        // traverse all ancestors (upwards) for p using parent pointers
+        while (p != null) {
+            ancestors.add(p);
+            p = parents.get(p);
+        }
+
+        // the first ancestor of q which appears in p's ancestor set is their LCA
+        while (!ancestors.contains(q)) {
+            q = parents.get(q);
+        }
+        return q;
+    }
+}
diff --git a/Week03/problems/46_permutations.java b/Week03/problems/46_permutations.java
@@ -0,0 +1,21 @@
+class Solution {
+    public List<List<Integer>> permute(int[] nums) {
+        List<List<Integer>> res = new ArrayList<>();
+        if (nums == null || nums.length == 0) {
+            return res;
+        }
+        helper(res, new ArrayList<>(), nums, 0);
+        return res;
+    }
+
+    private void helper(List<List<Integer>> res, ArrayList<Integer> list, int[] nums, int pos) {
+        if (pos == nums.length) {
+            res.add(new ArrayList(list));
+        }
+        for (int i = pos; i < nums.length; i++) {
+            list.add(nums[i]);
+            helper(res, list, nums, pos + 1);
+            list.remove(list.size() - 1);
+        }
+    }
+}
diff --git a/Week03/problems/47_permutations-ii.java b/Week03/problems/47_permutations-ii.java
@@ -0,0 +1,41 @@
+class Solution {
+    public List<List<Integer>> permuteUnique(int[] nums) {
+        List<List<Integer>> res = new ArrayList<>();
+        if (nums == null || nums.length == 0) return res;
+        Arrays.sort(nums);
+        helper(res, nums, 0);
+        return res;
+    }
+    public void helper(List<List<Integer>> res, int[] nums, int start) {
+        if (start == nums.length) {
+            List<Integer> list = new ArrayList<>();
+            for (int num : nums) {
+                list.add(num);
+            }
+            res.add(list);
+            return;
+        }
+
+        for (int i = start; i < nums.length; i++) {
+            if (isUsed(nums, start, i)) continue;
+            swap(nums, start, i);
+            helper(res, nums, start+1);
+            swap(nums, start, i);
+        }
+    }
+
+    public void swap(int[] nums, int i, int j) {
+        int temp = nums[i];
+        nums[i] = nums[j];
+        nums[j] = temp;
+    }
+
+    public boolean isUsed(int[] nums, int left, int right) {
+        for (int i = left; i < right; i++) {
+            if (nums[i] == nums[right]) {
+                return true;
+            }
+        }
+        return false;
+    }
+}
diff --git a/Week03/problems/77_combinations.java b/Week03/problems/77_combinations.java
@@ -0,0 +1,21 @@
+class Solution {
+    public List<List<Integer>> combine(int n, int k) {
+        List<List<Integer>> res = new ArrayList<>();
+        if (n < k || n <= 0 || k <= 0) {
+            return res;
+        }
+        helper(n, k, res, new ArrayList<>(), 1);
+        return res;
+    }
+
+    private void helper(int n, int k, List<List<Integer>> res, ArrayList<Integer> list, int pos) {
+        if (list.size() == k) {
+            res.add(new ArrayList<>(list));
+        }
+        for (int i = pos; i <= n; i++) {
+            list.add(i);
+            helper(n, k, res, list, i+1);
+            list.remove(list.size() - 1);
+        }
+    }
+}
