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



    前言


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

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

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

    跳跃游戏

    参考题目地址: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(该元素可以覆盖到的范围,该元素数值补充后的范围)
    
    • 1

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

    第二组数据:

    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;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

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

    最短跳跃游戏

    参考题目地址:45. 跳跃游戏 II - 力扣(LeetCode)

    在这里插入图片描述
    在这里插入图片描述
    这是上一道题目的进阶版,假设一定到达末尾,求最短步数。就拿上图的3种走法,我们怎么选出最短的那个呢?

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

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

    1. left用来一步步遍历数组
    2. steps用来记录到达当前位置的最少步数
    3. right表示当前步数下能够覆盖到的最大范围
    4. 我们还需要一个临时变量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++;
              }
              // 当然如果越界了,直接返回+1
              if (right >= nums.length - 1){
                  return step;
              }
          }
          return step;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    总结

    提示:贪婪算法;跳跃游戏;进阶游戏;跳跃问题;跳跃游戏进阶


    如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

    如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

    也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

    在这里插入图片描述

  • 相关阅读:
    Maven
    天龙八部门派采集任务坐标
    计算机图形学入门11:图形管线与着色器
    国内免费版ChatGPT
    网红长沙,为何常红?
    【Liunx】部署MariaDB
    第3章-指标体系与数据可视化-3.1.1-Matplotlib绘图库
    贪心算法练习
    【JDBC笔记】向数据表中插入Blob类型数据
    蓝桥杯冲刺_二分(正在补题)
  • 原文地址:https://blog.csdn.net/weixin_46585492/article/details/134086795