55. 跳跃游戏：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。_给你一个非负整数数组nums，你最初第一下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路

使用贪心的思路解决问题：

1. 只要有当前可跳的最长距离大于最后一个位置的下标，便可以返回true
2. 数组的第一个数x是当前可以跳的最长距离x，依次遍历目标数组的下标：1，2，，，nums.length；首先判断目前的下标是否小于等于当前可跳的最长距离，小于等于的话便需要更新当前能跳的最长距离，然后再判断更新后可跳的最长距离是否大于数组的最后一个下标的位置，大于的话，返回true；否则进入下一个循环

   示例二：[3, 2, 1, 0, 4]

   1. 我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
   2. 我们遍历到位置 1，由于 1 ≤ 3，因此位置 1 可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；
   3. 位置 2、位置 3 同理，最远可以到达的位置不会被更新；
   4. 我们遍历到位置44，由于 4 >3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。

详情请看代码，上面有注释说明

代码

class Solution {
    public boolean canJump(int[] nums) {
        //获取最后一个下标的位置
        int n = nums.length;
        //当前能跳的最长距离
        int rightMost = 0;
        //遍历整个数组
        for(int i = 0; i < n; i++){
            //如果当前下标小于等于更新后目前能跳的最长距离，证明还不能跳到数组的最后一个位置；大于的话，进入下一个循环（证明当前不可达）
            if(i <= rightMost){
                //更新当前能跳的最长距离
                rightMost = Math.max(rightMost, i + nums[i]);
                //如果当前能跳的最长距离大于数组的最后一个下标，则返回true
                if(rightMost >= n - 1){
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码说明

注释见。。。