MEDIUM/src/medium/JumpGame.java

fishercoder1534 · fishercoder1534 · commit 0da9fe63d2b3 · 2016-09-12T23:16:28.000-07:00
diff --git a/MEDIUM/src/medium/JumpGame.java b/MEDIUM/src/medium/JumpGame.java
@@ -0,0 +1,37 @@
+package medium;
+
+public class JumpGame {
+    
+    public static boolean canJump_greedy(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;
+            }
+        }
+        return farthest >= nums.length-1;
+    }
+
+    //this normal dp ends in TLE for extreme test cases
+    public static boolean canJump_dp(int[] nums) {
+        boolean[] can = new boolean[nums.length];
+        can[0] = true;
+        for(int i = 0; i < nums.length; i++){
+            int reach = nums[i];
+            if(can[i]){
+                for(int j = i+1; j < nums.length && j <= i+reach; j++){
+                    can[j] = true;
+                }
+            }
+        }
+        return can[nums.length-1];
+    }
+
+    public static void main(String...strings){
+//        int[] nums = new int[]{1,2};
+        int[] nums = new int[]{0,2,3};
+        System.out.println(canJump_greedy(nums));
+    }
+}
