algorithm002 · cc1901 · Jun 23, 2019 · Jun 23, 2019
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+.DS_STORE
diff --git a/Week_01/id_51/LeetCode_101_51.java b/Week_01/id_51/LeetCode_101_51.java
@@ -0,0 +1,26 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public boolean isSymmetric(TreeNode root) {        
+        return isMirror(root, root);
+    }
+
+    public boolean isMirror(TreeNode node1, TreeNode node2) {
+        if (node1 == null && node2 == null) {
+            return true;
+        } else if (node1 != null && node2 != null) {
+            return node1.val == node2.val && 
+                isMirror(node1.right, node2.left) &&
+                isMirror(node1.left, node2.right);
+        } else {
+            return false;
+        }                
+    }
+}
diff --git a/Week_01/id_51/LeetCode_1021_51.java b/Week_01/id_51/LeetCode_1021_51.java
@@ -0,0 +1,11 @@
+class Solution {
+    public String removeOuterParentheses(String S) {                
+        int open = 0;
+        StringBuilder sb = new StringBuilder();
+        for (char c : S.toCharArray()) {            
+            if (c == '(' && open++ != 0) sb.append(c);
+            if (c == ')' && open-- != 1) sb.append(c);            
+        }
+        return sb.toString();
+    }
+}
diff --git a/Week_01/id_51/LeetCode_1047_51.java b/Week_01/id_51/LeetCode_1047_51.java
@@ -0,0 +1,17 @@
+class Solution {
+    public String removeDuplicates(String S) {
+        if (S == null) return S;
+        StringBuilder sb = new StringBuilder();
+
+        for (char c : S.toCharArray()) {
+            int length = sb.length();
+            if (length == 0 || sb.charAt(length - 1) != c) {
+                sb.append(c);
+            } else {
+                sb.deleteCharAt(length - 1);
+            }                            
+        }
+
+        return sb.toString();
+    }
+}
diff --git a/Week_01/id_51/LeetCode_236_51.java b/Week_01/id_51/LeetCode_236_51.java
@@ -0,0 +1,24 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+        if (root == null || root == p || root == q) return root;
+        TreeNode left = lowestCommonAncestor(root.left, p, q);
+        TreeNode right = lowestCommonAncestor(root.right, p, q);
+
+        if (left != null && right != null) {
+            return root;
+        } else if (left != null) {
+            return left;
+        } else {
+            return right;
+        }            
+    }
+}
diff --git a/Week_01/id_51/LeetCode_42_51.java b/Week_01/id_51/LeetCode_42_51.java
@@ -0,0 +1,88 @@
+public class TrapWater {
+
+    private static Function<Integer[], Integer> stackSolution = height -> {
+        if (height == null || height.length == 0) return 0;
+        Stack<Integer> s = new Stack<>();
+
+        int result = 0;
+        for (int current = 0; current < height.length; current++) {
+            while (!s.isEmpty() && height[current] >= height[s.peek()]) {
+                int top = s.pop();
+                if (s.isEmpty()) continue;
+                int squareHeight = Math.min(height[current], height[s.peek()]) - height[top];
+                int squareWidth = current - s.peek() - 1;
+                result += squareHeight * squareWidth;
+            }
+            s.push(current);
+        }
+
+        return result;
+
+    };
+
+    private static Function<Integer[], Integer> dynamicProgramming = height -> {
+        if (height == null || height.length == 0) return 0;
+        int result = 0;
+        int size = height.length;
+        int[] leftMax = new int[size];
+        int[] rightMax = new int[size];
+
+        leftMax[0] = height[0];
+        for (int i = 1; i < size; i++) {
+            leftMax[i] = Math.max(leftMax[i-1], height[i]);
+        }
+        rightMax[size - 1] = height[size - 1];
+        for (int i = size - 2; i >= 0; i--) {
+            rightMax[i] = Math.max(rightMax[i+1], height[i]);
+        }
+
+        for (int i = 0; i < size-1; i++) {
+            result += Math.min(leftMax[i], rightMax[i]) - height[i];
+        }
+
+        return result;
+    };
+
+    private static Function<Integer[], Integer> twoPointer = height -> {
+        if (height == null || height.length == 0) return 0;
+        int result = 0;
+        int size = height.length;
+        int leftMax = 0;
+        int rightMax = 0;
+        int left = 0;
+        int right = size - 1;
+
+        while (left < right) {
+            if (height[left] < height[right]) {
+                if (height[left] > leftMax) {
+                    leftMax = height[left];
+                } else {
+                    result += leftMax - height[left];
+                }
+                left++;
+            } else {
+                if (height[right] > rightMax) {
+                    rightMax = height[right];
+                } else {
+                    result += rightMax - height[right];
+                }
+                right--;
+            }
+        }
+
+        return result;
+    };
+
+
+
+    public static void main(String[] args) {
+        int trap1 = stackSolution.apply(new Integer[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
+        int trap2 = dynamicProgramming.apply(new Integer[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
+        int trap3 = twoPointer.apply(new Integer[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
+        System.out.println(trap1);
+        System.out.println(trap2);
+        System.out.println(trap3);
+    }
+
+
+}
diff --git a/Week_01/id_51/LeetCode_441_51.java b/Week_01/id_51/LeetCode_441_51.java
@@ -0,0 +1,31 @@
+class Solution {
+    public int arrangeCoins(int n) {
+        int left = 0;
+        int right = n;
+        int middle = middle(0, n);
+        while ((left <= right) && !(formula(middle + 1) > n && formula(middle) < n)) {
+            if (formula(middle + 1) < n) {
+                left = middle;
+            }
+            if (formula(middle) > n) {
+                right = middle;
+            }
+            if (formula(middle) == n) {
+                return middle;
+            }
+            if (formula(middle + 1) == n) {
+                return middle + 1;
+            }
+            middle = middle(left, right);
+        }
+        return middle;
+    }
+
+    private long formula(long n) {
+        return n * (n + 1) / 2;
+    }
+
+    private int middle(int left, int right) {
+        return left + (right - left) / 2;
+    }
+}
diff --git a/Week_01/id_51/LeetCode_84_51.java b/Week_01/id_51/LeetCode_84_51.java
@@ -0,0 +1,21 @@
+class Solution {
+    public int largestRectangleArea(int[] heights) {
+        Deque<Integer> stack = new ArrayDeque<>();
+        stack.push(-1);
+        int maxArea = 0;
+        int size = heights.length;
+        for (int cur = 0; cur < size; cur++) {
+            while (stack.peek() != -1 && heights[stack.peek()] >= heights[cur]) {
+                int area = heights[stack.pop()] * (cur - stack.peek() - 1);
+                maxArea = Math.max(maxArea, area);
+            }
+            stack.push(cur);
+        }
+
+        while (stack.peek() != -1) {
+            int area = heights[stack.pop()] * (size - stack.peek() - 1);
+            maxArea = Math.max(maxArea, area);
+        }
+        return maxArea;
+    }
+}
diff --git a/Week_01/id_51/LeetCode_938_51.java b/Week_01/id_51/LeetCode_938_51.java
@@ -0,0 +1,28 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public int rangeSumBST(TreeNode root, int L, int R) {
+        int result = 0;
+        if (root == null) return result;
+
+        if (L < root.val) {
+            result += rangeSumBST(root.left, L, R);              
+        }
+        if (root.val >= L && root.val <= R) {
+            result += root.val;
+        }
+        if (R > root.val) {
+            result += rangeSumBST(root.right, L, R);
+        }
+
+        return result;
+    }
+
+}
diff --git a/Week_01/id_51/NOTE.md b/Week_01/id_51/NOTE.md
@@ -1 +1,33 @@
-# 学习笔记
+# Study Notes
+
+####coding exercise 
+1.  Do exercise for each problem at least 5 times
+1.  Time box for each problem, if no idea, just start read solution or discuss. Try to understand the solution and write it myself; write it again 1 week later;    
+
+####recursion
+recursion template
+```
+1. recusion terminator
+2. process logic in current level
+3. drill down
+4. reverse the current level status if needed
+``` 
+
+####BFS/DFS code template
+
+####Binary Search code template
+```
+mid = left + (right - left)/2
+```
+
+
+####BST
+1. In order traverse will get increasing list
+1. All the nodes in left child < root < all nodes in right child, child tree is in the same way;  
+
+####Java implementation skill
+1. Beside Stack<>, can also use Deque for stack implementation, like ArrayDeque
+1. Use LinkedList<> as queue when needed
+
+####Knowledge mind map
+![Alt text](./data-structure-and-algorithm.png?raw=true "Title")
diff --git a/Week_01/id_51/data-structure-and-algorithm.png b/Week_01/id_51/data-structure-and-algorithm.png