55. 跳跃游戏（高频题）

55. 跳跃游戏

• 题目
• 解题思路
• 代码

题目

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

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

判断你是否能够到达最后一个下标。

解题思路

从倒数第二个元素往前推，看倒数第二个元素能不能到达最后一个元素，能的话就再看倒数第三个元素能不能到倒数第二个元素…以此类推。

维护一个positon变量，表示能到到达最后一个元素的下标，最后只要看一下这个positon是不是0，也即能不能从开始那个元素到最后一个元素。

代码

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length==0){
            return false;
        }
        if(nums.length==1){
            return true;
        }

        int position=nums.length-1;
        for(int i=nums.length-2;i>=0;i--){
            /*
    假如数组为 [2,3,1,1,4]
    以nums[1]为起点，后面三格位置都是可达的，也就是如果某个数组下标i是可达的，
    那么i+1，i+2，i+3。。。i+nums[i]这片区域都是可达的。
    */
            if(nums[i]+i>=position){
                position=i;
            }
        }
    return position==0;
    }
}