55.跳跃游戏

LeetCode LeetCode 数组 热题100 贪心 动态规划
发布时间 :
字数:1.8k 阅读 : 评论:
  1. 55.跳跃游戏
    1. 55.1 题目
    2. 55.2 题解
      1. 方法一：贪心算法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：贪心（逆向）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 55.3 代码
    4. 55.4 运行结果

55.跳跃游戏

55.1 题目

给你一个非负整数数组 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 <= 10^4
  • 0 <= nums[i] <= 10^5

55.2 题解

方法一：贪心算法

思路

维护一个变量 maxReach 表示当前能到达的最远位置。从左到右遍历数组：如果当前位置 i 超过了 maxReach，说明无法到达当前位置，返回 false；否则更新 maxReach = Math.Max(maxReach, i + nums[i])。如果 maxReach >= n - 1，说明已经能到达终点，返回 true。核心思想：只要能到达当前位置，就能继续向后扩展可达范围。

核心思想：贪心维护最远可达位置。

具体步骤：

  1. 初始化 maxReach = 0。
  2. 遍历数组：
    • 如果 i > maxReach：返回 false
    • 更新 maxReach = max(maxReach, i + nums[i])
    • 如果 maxReach >= n - 1：返回 true
  3. 遍历结束返回 false。

举例：对于 nums = [2,3,1,1,4]：

  • i=0：maxReach = max(0, 0+2) = 2
  • i=1：maxReach = max(2, 1+3) = 4 >= 4
  • 返回 true

举例：对于 nums = [3,2,1,0,4]：

  • i=0：maxReach = 3
  • i=1：maxReach = 3
  • i=2：maxReach = 3
  • i=3：maxReach = 3
  • i=4：i=4 > maxReach=3，返回 false

复杂度分析

  • 时间复杂度：O(n)，遍历一次数组。
  • 空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：贪心算法
// 从左到右遍历数组，不断更新最远能够到达的位置，判断能否到达最后一个下标
static bool CanJump1(int[] nums)
{
    int maxReach = 0; // 记录当前能够到达的最远位置

    // 遍历数组
    for (int i = 0; i < nums.Length; i++)
    {
        // 如果当前位置超过了最远能够到达的位置，说明肯定不可能到达最后一个下标，返回 false
        if (i > maxReach)
        {
            return false;
        }

        // 更新最远能够到达的位置，i + nums[i]是当前位置能达到的最大值，和maxReach比较更新maxReach
        maxReach = Math.Max(maxReach, i + nums[i]);

        // 如果最远能够到达的位置超过或等于最后一个下标，返回 true
        if (maxReach >= nums.Length - 1)
        {
            return true;
        }
    }

    // 如果遍历完成后仍未能到达最后一个下标，返回 false
    return false;
}

方法二：贪心（逆向）

思路

从右向左遍历，维护变量 lastPos 表示能到达终点的最左位置。

对于每个位置 i，如果 i + nums[i] >= lastPos，说明从 i 能跳到 lastPos，更新 lastPos = i。

最终如果 lastPos == 0，说明从起点能到达终点。

本质是逆向思考：从终点倒推，看哪些位置能到达终点。

举个例子：nums = [2,3,1,1,4]

  • lastPos = 4
  • i=3：3+1=4 ≥ 4，lastPos = 3
  • i=2：2+1=3 ≥ 3，lastPos = 2
  • i=1：1+3=4 ≥ 2，lastPos = 1
  • i=0：0+2=2 ≥ 1，lastPos = 0
  • lastPos == 0，返回 true

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

// 方法二：贪心（逆向）
// 从右到左维护「能跳到当前已知可达终点的最左下标」，若最终该位置为 0 则从起点可达终点。
static bool CanJump2(int[] nums)
{
    int lastPos = nums.Length - 1; // 当前「已确认可到达终点」的最左下标，初始为终点

    // 从右到左遍历数组
    for (int i = nums.Length - 2; i >= 0; i--)
    {
        // 若从 i 能跳到 lastPos，则把可到达终点的最左位置左扩到 i
        if (i + nums[i] >= lastPos)
        {
            lastPos = i;
        }
    }

    // 起点也在可到达区间内则 true
    return lastPos == 0;
}

55.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个非负整数数组 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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 2, 3, 1, 1, 4 };
        bool result1_1 = CanJump1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = CanJump2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 3, 2, 1, 0, 4 };
        bool result2_1 = CanJump1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = CanJump2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：贪心算法
    // 从左到右遍历数组，不断更新最远能够到达的位置，判断能否到达最后一个下标
    static bool CanJump1(int[] nums)
    {
        int maxReach = 0; // 记录当前能够到达的最远位置

        // 遍历数组
        for (int i = 0; i < nums.Length; i++)
        {
            // 如果当前位置超过了最远能够到达的位置，说明肯定不可能到达最后一个下标，返回 false
            if (i > maxReach)
            {
                return false;
            }

            // 更新最远能够到达的位置，i + nums[i]是当前位置能达到的最大值，和maxReach比较更新maxReach
            maxReach = Math.Max(maxReach, i + nums[i]);

            // 如果最远能够到达的位置超过或等于最后一个下标，返回 true
            if (maxReach >= nums.Length - 1)
            {
                return true;
            }
        }

        // 如果遍历完成后仍未能到达最后一个下标，返回 false
        return false;
    }

    // 方法二：贪心（逆向）
    // 从右向左维护「能一步跳到当前已知可达终点的最左下标」lastPos；若最终 lastPos==0 则从起点可达。
    static bool CanJump2(int[] nums)
    {
        int lastPos = nums.Length - 1; // 当前视为「已确认可到达终点」的最左下标，初始为终点

        // 从右到左遍历数组
        for (int i = nums.Length - 2; i >= 0; i--)
        {
            // 若从 i 能跳到 lastPos，则把可到达终点的最左位置左扩到 i
            if (i + nums[i] >= lastPos)
            {
                lastPos = i;
            }
        }

        // 起点也在「可到达终点」的区间内则 true
        return lastPos == 0;
    }
    

    #endregion
}

55.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏