24.总结

1.概述

---

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 题解

贪心算法

// 方法一：贪心算法
// 从左到右遍历数组，不断更新最远能够到达的位置，判断能否到达最后一个下标
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;
}

动态规划

// 方法二：动态规划
// 从右到左遍历数组，不断更新当前位置能够到达的最远位置，如果最远位置大于等于当前位置，说明当前位置能够到达最后一个下标，返回 true；否则，返回 false。
static bool CanJump2(int[] nums)
{
    int lastPos = nums.Length - 1; // 记录当前能够到达的最远位置

    // 从右到左遍历数组
    for (int i = nums.Length - 2; i >= 0; i--)
    {
        // 更新当前位置能够到达的最远位置
        if (i + nums[i] >= lastPos)
        {
            lastPos = i;
        }
    }

    // 如果最远位置为起始位置，说明能够到达最后一个下标，返回 true；否则，返回 false
    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;
    }

    // 方法二：动态规划
    // 从右到左遍历数组，不断更新当前位置能够到达的最远位置，如果最远位置大于等于当前位置，说明当前位置能够到达最后一个下标，返回 true；否则，返回 false。
    static bool CanJump2(int[] nums)
    {
        int lastPos = nums.Length - 1; // 记录当前能够到达的最远位置

        // 从右到左遍历数组
        for (int i = nums.Length - 2; i >= 0; i--)
        {
            // 更新当前位置能够到达的最远位置
            if (i + nums[i] >= lastPos)
            {
                lastPos = i;
            }
        }

        // 如果最远位置为起始位置，说明能够到达最后一个下标，返回 true；否则，返回 false
        return lastPos == 0;
    }
    

    #endregion
}

---

55.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False

---

---

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