LeetCode--055--跳跃游戏(java)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

动态规划：

思路：每次计算当前所能走到的最大的索引，当nums[i] = 0 并且当前能走的最大值等于当前位置则返回false，当前所能走的最大值大于等于nums.length - 1的时候，可以走到最后。

 1 class Solution {
 2     public static boolean canJump(int[] nums) {
 3             int maxPos = 0;
 4             if(nums[0]==0 && nums.length >1)return false;
 5             else if (nums.length == 1)return true;
 6             for(int i = 0;i < nums.length;i++){
 7                 maxPos = Math.max(maxPos,nums[i]+i);
 8                 if(maxPos >=nums.length-1){
 9                     return true;
10                 }
11                 if(nums[i] == 0 && maxPos  - i <= 0){//注意，不要用maxPos - nums[i] - i <= 0来判定false如[2,3,1,1,4]当i=2时 满足这个。当时case [2,3,1,1,0,1]为了让i=4时返回false
12                     return false;
13                 }
14             }
15             return false;
16     }
17 }

和上面写的一样

 1 class Solution {
 2     public static boolean canJump(int[] nums) {
 3         int maxPos = 0;
 4         if(nums.length == 0)return false;
 5         int i = 0;
 6         while(i < nums.length && i <= maxPos){
 7             if(i+nums[i] >= nums.length - 1){
 8                 return true;
 9             }
10             maxPos = Math.max(maxPos,nums[i] + i);
11             i++;
12         }
13         
14         return false;
15     }
16 }

以前写的好烂还是看下面的吧

从后往前贪心，如果当前能跳跃的步数加索引大于最后能到的位置，则最后能到的位置记录当前的索引

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        endReachable = len(nums)-1
        for i in range(len(nums)-1,-1,-1):
            if nums[i]+i >= endReachable:
                endReachable = i
        return endReachable == 0

从前往后，遍历每个位置，找到跳跃最远的位置

1 class Solution:
2     def canJump(self, nums: List[int]) -> bool:
3         k = 0
4         for i in range(len(nums)):
5             if i > k:
6                 return False
7             k = max(k,i+nums[i])
8         return True

2020-01-17 17:59:32