当前位置：首页 > news >正文

算法通过村第十七关-贪心|黄金笔记|跳跃游戏

news 2025/8/15 21:01:12

文章目录

前言
跳跃游戏
最短跳跃游戏
总结

前言

提示：曾走过山，走过水，其实只是借助他们走过我的生命；我看着天，看着地，其实只是借助它们确定我的位置；我爱这她，爱着你，其实只不过借助别人实现了我的爱欲。 --史铁生《务虚笔记》

跳跃问题也是常考的类型之一，这里务必学习以下，我们就接着往下看。

💕😎💡⭐🥰🌰😭😥😒💣❔😂🤩👌👍🤖✅🤔

跳跃游戏

参考题目地址：55. 跳跃游戏 - 力扣（LeetCode）

在这里插入图片描述

在这里插入图片描述
如果当前位置元素如果是3，我究竟是要跳几步呢？其实这不是考虑的重点，关键在于是否最终可以到达重点，而不是每一步跳到哪里，而是尽可能的跳跃到最远的位置，看看最多的可以覆盖到哪里，只要不断更新覆盖的距离没最终覆盖到结尾就可以了。

在这里插入图片描述
从上图可以看出：

第一组：

3可以覆盖到{2，1，0}，2可以覆盖到{1，0}，1可以覆盖到{0}，最终无法达到4.

第二组：

2可以覆盖到{3，1}，3可以覆盖到{1，1，4}，1可以覆盖到{1}，1可以覆盖到{4}.到达终点。可达路径有

3条，{2，1，1 ，4}和{2，3，1，1，4}两种走法。

我们可以定义一个cover表示最远可以到达的方位，也就是i每次移动只能在cover的范围内移动，每次一档，cover得到该元素的值（新的覆盖范围）的补充，让i继续移动下去，儿cover每次按照下面的结果判断，如果cover大于等于最终下标直接返回true就可以了。

cover = max(该元素可以覆盖到的范围，该元素数值补充后的范围)

针对这个判断：我们再看下序列图：

第二组数据：

nums[0] = 2,此时cover = 2 能覆盖到{3.1}两个元素。

继续第二个元素，nums[1] = 3,此时能继续覆盖的范围就是1 + 3 ，可以覆盖到{1，1，4}三个位置，此时cover = 2，而该元素数值的补充后的范围值1 + 3 = 4，所以新的cover = max{4,2}.当然在这里已经可以结束了，cover >= nums.length- 1.

其他的情况也是如此，我们看下代码实现：

    /*** 跳跃游戏* @param nums* @return*/public static boolean canJump(int[] nums) {if (nums.length == 1){return true;}// 初始覆盖值0，也就从下标0开始遍历int cover = 0;for(int i = 0; i <= cover; i++){cover = Math.max(cover, i + nums[i]);// 超过就返回if (cover >= nums.length - 1){return true;}}return false;}

这个题目，如果你想到采用覆盖范围这个想法，我想解决不是难事，这里就是转换一下。

最短跳跃游戏

参考题目地址：45. 跳跃游戏 II - 力扣（LeetCode）

在这里插入图片描述

这是上一道题目的进阶版，假设一定到达末尾，求最短步数。就拿上图的3种走法，我们怎么选出最短的那个呢？

❔

这里采用骨头哥的：贪婪+双指针

在上一题的基础上做改进，这里准备4个变量。

left用来一步步遍历数组
steps用来记录到达当前位置的最少步数
right表示当前步数下能够覆盖到的最大范围
我们还需要一个临时变量cover，假如left到达right时才更新right。

此时还么有达到终点，我们需要继续走，这是可以选择的元素是{2，4}，如果选择2，则可以到达left+num[left]=3 + 2 = 5,如果选择4,则是left+num[left]=4 +8= 8，此时以已经过界了，一定可以覆盖到结尾的。
在这里插入图片描述
然后用left和right将step的范围标记一下：

此时还么有达到终点，我们需要继续走，这是可以选择的元素是{2，4}，如果选择2，则可以到达left+num[left]=3 + 2 = 5,如果选择4,则是left+num[left]=4 +8= 8，此时以已经过界了，一定可以覆盖到结尾的。

在这里插入图片描述
也就是说，最后一定可以到达，至少需要走3步的。

看了这么多，代码要怎么写呢？

    /*** 跳跃游戏进阶* @param nums* @return*/public static int jump(int[] nums) {int step = 0;int maxPosition = 0;int right = 0;for(int left = 0; left < nums.length ; left++) {// 覆盖的最远距离maxPosition = Math.max(maxPosition, nums[left] + left);// 遇到边界，更新边界if (left == right){right = maxPosition;step++;}// 当然如果越界了，直接返回+1if (right >= nums.length - 1){return step;}}return step;}