55-跳跃游戏

转载    https://leetcode-cn.com/problems/jump-game/solution/fan-xiang-kao-lu-dang-bu-de-bu-tiao-dao-0de-shi-ho/

 思路:

首先,求的是跳到最后一个元素,最后一个元素的最大步数明显可以是0,因为跳到最后一个元素,算法就结束了,不跳也行。

其次,考虑官方给的例子

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

  可以总结出,当你不管怎么跳,都要经过0时,也就是0是你的必经之路时,是跳不出去数组的。所以只要找到一条可以跳出0 的路径,那么就可以跳跃到最后一位。

所以说,倒叙从倒数第二个元素开始找,找下标在【0,length-2】范围内的,所有nums[i]==0的点。找在这些点的左侧,有没有可以跳过nums【i】==0的下标j。也就是这样一个j,使得nums[j]>i-j。

class Solution {
    public boolean canJump(int[] nums) {
        int len=nums.length;
        if(nums[0]==0&&len!=1)
        return false;
        if(nums[0]==0&&len==1)
        return true;
        boolean ke=true;
        for(int i=nums.length-2;i>=0;i--)//最后一位显然可以是0,
        {
            if(nums[i]!=0)
            {
                continue;
            }
            else
            {   boolean shi=false;
                for(int j=0;j<i;j++)//找到一个等于零的元素nums[i],找下标0到i-1之间,有没有元素j满足nums[j]>i-j(要足够指向零的下一个元素),有的话,就说明可以跳到,如果找不到,就返回false
                {
                    if(nums[j]>(i-j))
                    {
                        shi=true;
                        break;
                    }
                }
                if(!shi)
                {
                    return false;
                }
            }
        }
        return true;
    }
}

  

原文地址:https://www.cnblogs.com/lzh1043060917/p/12807244.html