【力扣经典面试题】55. 跳跃游戏

题目描述：

给你一个非负整数数组 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. 初始化变量： 代码中使用变量 k 来表示目前能够到达的最远的索引位置。

2. 遍历数组： 通过一个循环遍历数组元素，其中 i 表示当前的索引位置。

3. 判断是否能够到达： 在每一步，都检查当前索引 i 是否超出了目前能够到达的最远索引位置 k。如果超出，则说明无法到达最后一个元素，直接返回 false。

4. 更新最远可到达的位置： 如果当前索引 i 在可到达的范围内，就通过比较 k 和 i + nums[i] 来更新能够到达的最远索引位置。这是贪心算法的核心部分，每次都选择能够跳跃最远的位置。

5. 循环结束： 如果成功遍历整个数组，说明可以通过一系列跳跃操作到达最后一个元素，返回 true。

代码：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;  // 表示目前能够到达的最远的索引位置
        
        for(int i = 0; i < nums.size(); i++) {
            if(i > k) 
                return false;  // 如果当前索引超出了能够到达的范围，返回false
            k = max(k, i + nums[i]);  // 更新能够到达的最远的索引位置
            
            // 每一步都检查当前索引是否能够到达，根据当前索引和其值更新能够到达的最远索引。
            // 如果循环完成而没有遇到 i > k 的条件，意味着最后的索引可以到达，函数返回true。
        }
        
        return true;  // 如果成功遍历数组而没有达到终止条件，返回true
    }
};

总结：

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，因为它只对数组进行一次线性遍历。这种贪心算法的思想是每次都选择能够跳跃最远的位置，以尽可能地覆盖更多的元素，从而判断是否能够到达最后一个元素。

代码007普通

打赏 收藏 海报 链接