add a solution for 55

fishercoder1534 · fishercoder1534 · commit 437ff6315381 · 2021-09-16T11:34:03.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_55.java b/src/main/java/com/fishercoder/solutions/_55.java
@@ -3,16 +3,80 @@
 public class _55 {
 
     public static class Solution1 {
+        /**
+         * My very original but lengthy solution.
+         */
         public boolean canJump(int[] nums) {
-            int farthest = nums[0];
-            for (int i = 0; i < nums.length; i++) {
-                if (i <= farthest && nums[i] + i > farthest) {
-                    //i <= farthest is to make sure that this current i is within the current range
-                    // nums[i]+i > farthest is to make sure that it's necessary to update farthest with current nums[i]+i
-                    farthest = nums[i] + i;
+            int furthestReach = nums[0];
+            if (furthestReach >= nums.length - 1) {
+                return true;
+            }
+            int i = 1;
+            for (; i < nums.length; ) {
+                int newFurthestReach = -1;
+                while (i <= furthestReach) {
+                    newFurthestReach = Math.max(newFurthestReach, nums[i] + i);
+                    if (newFurthestReach >= nums.length) {
+                        return true;
+                    }
+                    i++;
+                }
+                if (newFurthestReach <= furthestReach) {
+                    return false;
+                } else if (newFurthestReach >= nums.length - 1) {
+                    return true;
+                } else {
+                    furthestReach = newFurthestReach;
+                }
+            }
+            return false;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * The same idea as mine above, but much more concise.
+         * Credit: https://leetcode.com/problems/jump-game/discuss/20917/Linear-and-simple-solution-in-C%2B%2B
+         */
+        public boolean canJump(int[] nums) {
+            int i = 0;
+            for (int reach = 0; i < nums.length && i <= reach; i++) {
+                reach = Math.max(reach, nums[i] + i);
+            }
+            return i >= nums.length;
+        }
+    }
+
+    public static class Solution3 {
+        /**
+         * Top-down DP.
+         * Credit: https://leetcode.com/problems/jump-game/solution/ approach 2
+         * <p>
+         * Specifically, for this problem, my very own Solution1 and the above Solution2 run much faster than this DP solution.
+         * But just use this problem to practice DP.
+         * <p>
+         * The reason it's called top-down is that it's filling the dp array from the right to the left if you set break points and step through this.
+         */
+        public boolean canJump(int[] nums) {
+            int[] dp = new int[nums.length];
+            //0 means unknown, 1 means reachable, 2 means unreachable
+            dp[nums.length - 1] = 1;
+            return canJumpFrom(0, nums, dp);
+        }
+
+        private boolean canJumpFrom(int index, int[] nums, int[] dp) {
+            if (dp[index] != 0) {
+                return dp[index] == 1;
+            }
+            int furthestReach = Math.min(index + nums[index], nums.length - 1);
+            for (int i = index + 1; i <= furthestReach; i++) {
+                if (canJumpFrom(i, nums, dp)) {
+                    dp[i] = 1;
+                    return true;
                 }
             }
-            return farthest >= nums.length - 1;
+            dp[index] = 2;
+            return false;
         }
     }
 }
diff --git a/src/test/java/com/fishercoder/_55Test.java b/src/test/java/com/fishercoder/_55Test.java
@@ -8,23 +8,88 @@
 
 public class _55Test {
     private static _55.Solution1 solution1;
+    private static _55.Solution2 solution2;
+    private static _55.Solution3 solution3;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _55.Solution1();
+        solution2 = new _55.Solution2();
+        solution3 = new _55.Solution3();
     }
 
     @Test
     public void test1() {
         nums = new int[]{0, 2, 3};
         assertEquals(false, solution1.canJump(nums));
+        assertEquals(false, solution2.canJump(nums));
+        assertEquals(false, solution3.canJump(nums));
     }
 
     @Test
     public void test2() {
         nums = new int[]{1, 2};
         assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
     }
 
+    @Test
+    public void test3() {
+        nums = new int[]{2, 3, 1, 1, 4};
+        assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test4() {
+        nums = new int[]{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0};
+        assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test5() {
+        nums = new int[]{2, 0, 0};
+        assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test6() {
+        nums = new int[]{2, 0};
+        assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test7() {
+        nums = new int[]{1, 1, 0, 1};
+        assertEquals(false, solution1.canJump(nums));
+        assertEquals(false, solution2.canJump(nums));
+        assertEquals(false, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test8() {
+        nums = new int[]{0};
+        assertEquals(true, solution1.canJump(nums));
+        assertEquals(true, solution2.canJump(nums));
+        assertEquals(true, solution3.canJump(nums));
+    }
+
+    @Test
+    public void test9() {
+        nums = new int[]{3, 2, 1, 0, 4};
+//        assertEquals(false, solution1.canJump(nums));
+//        assertEquals(false, solution2.canJump(nums));
+        assertEquals(false, solution3.canJump(nums));
+    }
+
+
 }
