LeetCode 跳跃游戏

发布于:2024-11-29 ⋅ 阅读:(22) ⋅ 点赞:(0)

题目描述

给你一个非负整数数组 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 , 所以永远不可能到达最后一个下标。

解题思路

刚看到本题一开始可能想:当前位置元素如果是 3,我究竟是跳一步呢,还是两步呢,还是三步呢,究竟跳几步才是最优呢?

其实跳几步无所谓,关键在于可跳的覆盖范围!

不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。

这个范围内,别管是怎么跳的,反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!

每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。

i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。

cover 每次只取 max (cover 本身范围, 该元素数值补充后的范围 )。

如果 cover 大于等于了终点下标,直接 return true 就可以了。

代码

var canJump = function(nums) {
    if(nums.length === 1) return true
    let cover = 0
    for(let i = 0; i <= cover; i++) {
        cover = Math.max(cover, i + nums[i])
        if(cover >= nums.length - 1) {
            return true
        }
    }
    return false
};

代码分析

  1. 函数定义:canJump 是函数名,nums 是传入的参数,代表一个非负整数数组。

  2. 边界条件处理:如果数组 nums 的长度为 1,即只有一个元素,那么不需要跳跃,直接返回 true

  3. 初始化变量 covercover 用来记录当前能够到达的最远位置。初始值为 0,因为最开始我们还没有开始跳跃。

  4. 循环遍历数组:使用 for 循环从索引 0 开始遍历数组,直到 cover(当前能够到达的最远位置)。

    • for(let i = 0; i <= cover; i++):循环条件是 i 小于等于 cover,这意味着我们只会尝试跳到当前能够到达的最远位置。
  5. 更新 cover:在循环体内,我们更新 cover 的值。cover = Math.max(cover, i + nums[i]) 这行代码意味着我们将当前 cover 的值与当前索引 i 加上该索引处的元素值(即 i + nums[i])进行比较,取两者中的最大值作为新的 cover。这样做是因为在索引 i 处,我们可以选择跳到 i + nums[i] 的位置,这可能比当前 cover 更远。

  6. 判断是否到达终点:if(cover >= nums.length - 1) 这行代码检查当前的 cover 是否已经大于或等于数组的长度减去 1(即数组的最后一个索引)。如果是,说明我们已经能够到达或超过数组的最后一个位置,因此返回 true

  7. 返回结果:如果循环结束后,cover 没有达到数组的最后一个位置,那么返回 false,表示无法到达最后一个位置。

总结来说,这段代码通过维护一个 cover 变量来记录当前能够到达的最远位置,并在每次迭代中更新这个位置。如果这个位置能够覆盖到数组的最后一个元素,那么函数就返回 true,表示可以到达终点;否则,返回 false。这种方法不需要考虑每一步具体跳多远,而是通过贪心策略,每次尽可能跳得更远,从而达到解决问题的目的。

案例分析

示例 1:

输入:nums = [2,3,1,1,4]

  1. 初始化 cover = 0,因为最开始我们位于数组的第一个下标。
  2. 开始循环,i 从 0 开始:
    • i = 0cover 更新为 Math.max(0, 0 + 2),即 2
    • 检查 cover 是否大于等于 nums.length - 1,即 2 >= 4,不是,继续循环。
  3. i 增加到 1:
    • i = 1cover 更新为 Math.max(2, 1 + 3),即 4
    • 检查 cover 是否大于等于 nums.length - 1,即 4 >= 4,是的,返回 true

在这个示例中,我们可以看到,从索引 0 开始,我们可以跳到索引 1 或 2(因为 nums[0] = 2),然后从索引 1,我们可以跳到索引 4(因为 nums[1] = 3 加上我们已经在索引 1)。所以,我们可以覆盖到数组的最后一个位置,函数返回 true

示例 2:

输入:nums = [3,2,1,0,4]

  1. 初始化 cover = 0
  2. 开始循环,i 从 0 开始:
    • i = 0cover 更新为 Math.max(0, 0 + 3),即 3
    • 检查 cover 是否大于等于 nums.length - 1,即 3 >= 4,不是,继续循环。
  3. i 增加到 1:
    • i = 1cover 更新为 Math.max(3, 1 + 2),即 3(因为 1 + 2 小于当前的 cover)。
    • 检查 cover 是否大于等于 nums.length - 1,即 3 >= 4,不是,继续循环。
  4. i 增加到 2:
    • i = 2cover 更新为 Math.max(3, 2 + 1),即 3(因为 2 + 1 小于当前的 cover)。
    • 检查 cover 是否大于等于 nums.length - 1,即 3 >= 4,不是,继续循环。
  5. i 增加到 3:
    • i = 3cover 更新为 Math.max(3, 3 + 0),即 3(因为 3 + 0 等于当前的 cover)。
    • 检查 cover 是否大于等于 nums.length - 1,即 3 >= 4,不是,返回 false

在这个示例中,尽管我们可以从索引 0 跳到索引 3,但是索引 3 的值是 0,意味着我们不能从索引 3 跳到索引 4。因此,cover 始终没有达到数组的最后一个位置,函数返回 false