跳跃游戏I 题解

题目详情

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

题解

题目重要内容解析：

首先，我们要注意，题干中的 你最初位于数组的 第一个下标 和 可以跳跃的最大长度，这句话非常关键，也就是说，我们在一个数组中，我们首先会跳到 nums[0] 对应的值的 对应的下标，也就是说我们最开始其实是位于 nums[nums[0]]的位置，而且我们要保证我们无论如何都不能跳到 值为 0的位置，其他情况都能跳出

所以本题的关键在于，我们需要维护一个最大的step，如果遇到0，看能否回溯跳过0的值

题解1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// eg [2,5,0,0]    
   public boolean canJump(int[] nums) {
        // 如果该数组长度为1,证明已经在最后一个下表，直接返回true
        if(nums.length == 1) {
            return true;
        }
        // 遍历数组
        for(int i=0;i<nums.length;i++) {
            // 如果当前值为0，那么我们就要回溯，看能否跳过0
            if(nums[i] == 0 && !check(nums, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean check(int[] nums, int end) {
        // 我们只遍历 nums [0,end-1]的位置
        for(int j=end-1;j>=0;j--) {
            // 判断当前值 nums[j]的步长是否大于 从当前位置跳过0 或者，当前位置+nums[j] 超过数组长度
            if(nums[j] > (end - j) || (j+nums[j]) >= nums.length-1) {
                return true;
            }
        }
        return false;
    }

image-20231213220608941

题解2

我们发现上面的代码又是双层for循环，我们是否能像之前一样，通过假定一个值来减少for循环的层数，答案是肯定的

1
2
3
4
5
6
7
8
9
10
11
12
//  eg [2,5,0,0]   [3,2,1,0,4]
static boolean canJump(int[] nums) {
   	// 定义步长
     int step = 0;
     for (int index = 0; index < nums.length; index++) {
         // 如果index>step说明，存在下标为0 的数据 且该位置无法跳脱
         if (index > step) return false;
         // 循环便利，并且取步长最大的值
         step = Math.max(step, index + nums[index]);
     }
     return true;
 }

image-20231213221420221