建站工具有哪些社区,wordpress page页,太原做网站哪里好,网站二次开发教程文章目录 前言跳跃游戏最短跳跃游戏总结 前言 提示#xff1a;曾走过山#xff0c;走过水#xff0c;其实只是借助他们走过我的生命#xff1b;我看着天#xff0c;看着地#xff0c;其实只是借助它们确定我的位置#xff1b;我爱这她#xff0c;爱着你#xff0c;其实… 文章目录 前言跳跃游戏最短跳跃游戏总结 前言 提示曾走过山走过水其实只是借助他们走过我的生命我看着天看着地其实只是借助它们确定我的位置我爱这她爱着你其实只不过借助别人实现了我的爱欲。 --史铁生《务虚笔记》 跳跃问题也是常考的类型之一这里务必学习以下我们就接着往下看。 ⭐❔✅
跳跃游戏
参考题目地址55. 跳跃游戏 - 力扣LeetCode 如果当前位置元素如果是3我究竟是要跳几步呢其实这不是考虑的重点关键在于是否最终可以到达重点而不是每一步跳到哪里而是尽可能的跳跃到最远的位置看看最多的可以覆盖到哪里只要不断更新覆盖的距离没最终覆盖到结尾就可以了。 从上图可以看出
第一组
3可以覆盖到{210}2可以覆盖到{10}1可以覆盖到{0}最终无法达到4.
第二组
2可以覆盖到{31}3可以覆盖到{114}1可以覆盖到{1}1可以覆盖到{4}.到达终点。可达路径有
3条{211 4}和{23114}两种走法。
我们可以定义一个cover表示最远可以到达的方位也就是i每次移动只能在cover的范围内移动每次一档cover得到该元素的值新的覆盖范围的补充让i继续移动下去儿cover每次按照下面的结果判断如果cover大于等于最终下标直接返回true就可以了。
cover max(该元素可以覆盖到的范围该元素数值补充后的范围)针对这个判断我们再看下序列图
第二组数据
nums[0] 2,此时cover 2 能覆盖到{3.1}两个元素。
继续第二个元素nums[1] 3,此时能继续覆盖的范围就是1 3 可以覆盖到{114}三个位置此时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。
此时还么有达到终点我们需要继续走这是可以选择的元素是{24}如果选择2则可以到达leftnum[left]3 2 5,如果选择4,则是leftnum[left]4 8 8此时以已经过界了一定可以覆盖到结尾的。 然后用left和right将step的范围标记一下
此时还么有达到终点我们需要继续走这是可以选择的元素是{24}如果选择2则可以到达leftnum[left]3 2 5,如果选择4,则是leftnum[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;}总结
提示贪婪算法跳跃游戏进阶游戏跳跃问题跳跃游戏进阶 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
