【力扣刷题 | 第十七天】

我不是女神ヾ 2024-03-17 19:10 17阅读 0赞

![32582361154b4258a57392c3c16aa671.jpeg][]

**目录**

前言：

55. 跳跃游戏 - 力扣（LeetCode）

45. 跳跃游戏 II - 力扣（LeetCode）

总结：

--------------------

## 前言： ##

今天两道类型都是贪心算法，希望可以有所收获

### [55. 跳跃游戏 - 力扣（LeetCode）][55. _ - _LeetCode] ###

给定一个非负整数数组 `nums` ，你最初位于数组的 **第一个下标** 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

![4a8baa12018242d4863d5cd665ae014e.png][]

其实这道题注重的是思想，很多人把这道题当作贪心算法思路去做，但是都陷入了一个**思维陷阱：**

我在当前位置如何选择下一步，使其最后能够到达目的点。

但是如果这样想，就会陷入很难的一个解题思路，就是如何选取下一步怎么走，因为有的时候贪的步数多反而无法到达重点。

因此**我们不要纠结于到底应该怎么走，而是看覆盖范围**，我用实例给大家举例子：

![d977f2a167644566b8abc5ad2c611933.png][]

我们可以用横线表示覆盖范围：  
![60fe391525054aa2a1671388c92cbe84.png][]

可以清楚的看到3已经覆盖了4，那么我们就可以知道在这个数组中，我们是可以走到最后一个点的。

我们再举一个反例：  
![d23f1def51054031aa974f832595e919.png][]

我们就可以看到这个数组的元素（不包括最后一个元素）是无法覆盖到最后一个点的，那么无论我们怎么走也不可能到达最后一个点。

因此这道题我们根据这种思想，可以写出解法：

class Solution {
    public:
        bool canJump(vector<int>& nums) {
            int size =nums.size();
            int cover=0;
            for(int i=0;i<=cover;i++)
            {
               cover=max(nums[i]+i,cover);
                if(cover>=size-1)
                {
                    return true;
                }         
            }
            return false;
        }
    };

### [45. 跳跃游戏 II - 力扣（LeetCode）][45. _ II - _LeetCode] ###

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums\[0\]。

每个元素 nums\[i\] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums\[i\] 处，你可以跳转到任意 nums\[i + j\] 处:

0 <= j <= nums\[i\]  
i + j < n  
返回到达 nums\[n - 1\] 的最小跳跃次数。生成的测试用例可以到达 nums\[n - 1\]。

![2be69385978e4ff5aad3f1bba8b5a324.png][]

这道题也是贪心算法思路，但是很多人贪心的目的错了，上道题中我们引入了覆盖范围，那么实际上**在最小跳跃次数的前提下我们贪的不是最多的步数，而是最大的覆盖范围。**

根据这个解题思想，我们可以得出：

class Solution {
    public:
        int jump(vector<int>& nums) {
            int size =nums.size();
            int cur=0;
            int next=0;
            int count=0;
            if(size==1)
            {
                return 0;
            }
    
            for(int i=0;i<size;i++)
            {
                next=max(i+nums[i],next);
                if(i==cur)
                {
                    if(cur!=size-1)
                    {
                        count++;
                        cur=next;
                    }
                    if(cur>=size-1)
                    {
                        break;
                    }
                }
            }
            return count;
        }
        
    };

我来做一下详细的解释：先建立四个变量：size 表示到达目的点所需长度，cur 表示当前所在点的覆盖范围，next 表示我们将要跳到的点的覆盖范围，count 记录跳跃次数。

此后基于当前位置的覆盖范围，我们向后寻找下一个最大的覆盖范围，这也就是for语句里面三个if的作用

*  if(i==cur)用来判断我们的是否已经判断完当前覆盖范围内的下一个最大覆盖范围。
 *  if(cur!=size-1)用来判断是否当前覆盖范围未覆盖到目的点，如果不等于就是没覆盖，如果没覆盖，我们就要走到下一个最大覆盖点处（cur=next),并且给跳跃次数+1（count++）
 *  if(cur>=size-1)用来判断是否当前覆盖范围已经覆盖到目的点，如果已经覆盖，则说明此时的跳跃步数就已经是最短跳跃步数，直接退出循环，输出结果。

## 总结： ##

贪心算法的题目万变不离其宗，我们还是要通过大量的刷题掌握更多的贪心算法思路。

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[32582361154b4258a57392c3c16aa671.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c9062782ec1d408fb9d5999e8ff35a24.png
[55. _ - _LeetCode]: https://leetcode.cn/problems/jump-game/
[4a8baa12018242d4863d5cd665ae014e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c99a5a9575a8417e8747474c24ba13ad.png
[d977f2a167644566b8abc5ad2c611933.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7515ead16cbb4e60b0d1788d20fca00a.png
[60fe391525054aa2a1671388c92cbe84.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0fde733e9a674151a60cad553e64a5e3.png
[d23f1def51054031aa974f832595e919.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cb72a6ff12bc40d294aeb64702134fc7.png
[45. _ II - _LeetCode]: https://leetcode.cn/problems/jump-game-ii/
[2be69385978e4ff5aad3f1bba8b5a324.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/318fe391a2fd4b90be067b4c42b65d09.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1d29ef731abb43b8853dd4aa4770001d.png