refactor 300

fishercoder1534 · fishercoder1534 · commit 14108df2fab0 · 2021-03-30T08:33:30.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_300.java b/src/main/java/com/fishercoder/solutions/_300.java
@@ -4,38 +4,115 @@
 
 public class _300 {
 
+    /**
+     * credit: https://leetcode.com/problems/longest-increasing-subsequence/solution/
+     */
     public static class Solution1 {
+        /**
+         * brute force:
+         * Time: O(2^n), size of recursion tree will be: 2^n
+         * Space: O(n^2)
+         * will result in Time Limit Exceeded exception.
+         * <p>
+         * The idea is straightforward: we'll iterate through each number, check to see if its next neighbor is smaller or bigger than itself,
+         * if bigger, then we'll take it, if not, we'll not take it.
+         */
+        public int lengthOfLIS(int[] nums) {
+            return recursion(nums, Integer.MIN_VALUE, 0);
+        }
+
+        private int recursion(int[] nums, int prev, int curr) {
+            if (curr == nums.length) {
+                return 0;
+            }
+            int taken = 0;
+            if (nums[curr] > prev) {
+                taken = 1 + recursion(nums, nums[curr], curr + 1);
+            }
+            int notTaken = recursion(nums, prev, curr + 1);
+            return Math.max(taken, notTaken);
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * This is an iteration on the previous solution, we use a 2-d array to memoize the previously calculated result
+         * Time: O(n^2)
+         * Space: O(n^2)
+         */
+        public int lengthOfLIS(int[] nums) {
+            int len = nums.length;
+            int[][] memo = new int[len + 1][len];
+            for (int[] m : memo) {
+                Arrays.fill(m, -1);
+            }
+            return recusionWithMemo(nums, -1, 0, memo);
+        }
+
+        private int recusionWithMemo(int[] nums, int prevIndex, int currIndex, int[][] memo) {
+            if (currIndex == nums.length) {
+                return 0;
+            }
+            if (memo[prevIndex + 1][currIndex] >= 0) {
+                //because we initialize all elements in memo to be -1,
+                // so if it's not -1, then it means we have computed this value before,
+                // we'll just return it and this way it avoid duplicate recursion
+                return memo[prevIndex + 1][currIndex];
+            }
+            int taken = 0;
+            if (prevIndex < 0 || nums[currIndex] > nums[prevIndex]) {
+                taken = 1 + recusionWithMemo(nums, currIndex, currIndex + 1, memo);
+            }
+            int notTaken = recusionWithMemo(nums, prevIndex, currIndex + 1, memo);
+            memo[prevIndex + 1][currIndex] = Math.max(taken, notTaken);
+            return memo[prevIndex + 1][currIndex];
+        }
+    }
+
+    public static class Solution3 {
+        /**
+         * DP solution
+         * Time: O(n^2)
+         * Space: O(n)
+         */
+        public int lengthOfLIS(int[] nums) {
+            if (nums.length == 0) {
+                return 0;
+            }
+            int[] dp = new int[nums.length];
+            dp[0] = 1;
+            int result = 1;
+            for (int i = 1; i < nums.length; i++) {
+                int maxVal = 0;
+                for (int j = 0; j < i; j++) {
+                    if (nums[i] > nums[j]) {
+                        maxVal = Math.max(maxVal, dp[j]);
+                    }
+                }
+                dp[i] = maxVal + 1;
+                result = Math.max(result, dp[i]);
+            }
+            return result;
+        }
+    }
 
+    public static class Solution4 {
         /**
-         * credit: https://discuss.leetcode.com/topic/28719/short-java-solution-using-dp-o-n-log-n
-         * The idea is that as you iterate the sequence,
-         * you keep track of the minimum value a subsequence of given length might end with,
-         * for all so far possible subsequence lengths.
-         * So dp[i] is the minimum value a subsequence of length i+1 might end with.
-         * Having this info, for each new number we iterate to,
-         * we can determine the longest subsequence where it can be appended using binary search.
-         * The final answer is the length of the longest subsequence we found so far.
+         * use binary search.
+         * Time: O(nlogn)
+         * Space: O(n)
+         * <p>
+         * The reason we can use binary search here is because all numbers we put into dp array are sorted
          */
         public int lengthOfLIS(int[] nums) {
             int[] dp = new int[nums.length];
             int len = 0;
-            for (int x : nums) {
-                /**Java Doc of this binarySearch API:
-                 * @return index of the search key, if it is contained in the array
-                 *         within the specified range;
-                 *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
-                 *         <i>insertion point</i> is defined as the point at which the
-                 *         key would be inserted into the array: the index of the first
-                 *         element in the range greater than the key,
-                 *         or <tt>toIndex</tt> if all
-                 *         elements in the range are less than the specified key.  Note
-                 *         that this guarantees that the return value will be &gt;= 0 if
-                 *         and only if the key is found.*/
-                int index = Arrays.binarySearch(dp, 0, len, x);
+            for (int num : nums) {
+                int index = Arrays.binarySearch(dp, 0, len, num);
                 if (index < 0) {
                     index = -(index + 1);
                 }
-                dp[index] = x;
+                dp[index] = num;
                 if (index == len) {
                     len++;
                 }
diff --git a/src/test/java/com/fishercoder/_300Test.java b/src/test/java/com/fishercoder/_300Test.java
@@ -9,18 +9,44 @@
 public class _300Test {
 
     private static _300.Solution1 solution1;
+    private static _300.Solution2 solution2;
+    private static _300.Solution3 solution3;
+    private static _300.Solution4 solution4;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _300.Solution1();
+        solution2 = new _300.Solution2();
+        solution3 = new _300.Solution3();
+        solution4 = new _300.Solution4();
     }
 
     @Test
     public void test1() {
         nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};
         assertEquals(4, solution1.lengthOfLIS(nums));
+        assertEquals(4, solution2.lengthOfLIS(nums));
+        assertEquals(4, solution3.lengthOfLIS(nums));
+        assertEquals(4, solution4.lengthOfLIS(nums));
+    }
+
+    @Test
+    public void test2() {
+        nums = new int[]{0, 1, 0, 3, 2, 3};
+        assertEquals(4, solution1.lengthOfLIS(nums));
+        assertEquals(4, solution2.lengthOfLIS(nums));
+        assertEquals(4, solution3.lengthOfLIS(nums));
+        assertEquals(4, solution4.lengthOfLIS(nums));
+    }
 
+    @Test
+    public void test3() {
+        nums = new int[]{7, 7, 7, 7, 7, 7, 7};
+        assertEquals(1, solution1.lengthOfLIS(nums));
+        assertEquals(1, solution2.lengthOfLIS(nums));
+        assertEquals(1, solution3.lengthOfLIS(nums));
+        assertEquals(1, solution3.lengthOfLIS(nums));
     }
 
 }
