贪心算法-01:跳跃游戏

这篇具有很好参考价值的文章主要介绍了贪心算法-01:跳跃游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

关于贪心算法

贪心算法是动态规划的一个特例,相对于动态规划,使用贪心算法需要满足更多条件,但是效率比动态规划要高。

贪心选择的性质就是:每一步都做出一个局部最优解,最终的结果就是全局最优。不过这是一种特殊性质,只有一部分问题拥有这个性质。

比如面前放有100张人民币,你只能拿十张。想要拿到最高的金额,就需要每次选择剩下钞票中面值最大的一张,最后你的选择一定是最优的。

接下来,我会演示跳跃游戏Ⅱ的 动态规划解法 和 贪心算法解法,通过对比来说明贪心算法的 “局部最优解” 是怎样的。

力扣45.跳跃游戏Ⅱ

贪心算法-01:跳跃游戏,手把手带你刷力扣Hot100,贪心算法,游戏,算法

动态规划解法 

定义dp函数

使用动态规划解法就是 [分解问题]。

我们的原始问题是:从初始位置跳到最后一个位置的最小跳跃次数。

我们将其分解出子问题:从索引 p 跳到最后一个位置的最小跳跃次数。

//定义dp函数:从索引p跳到数组末尾的最小跳跃次数为dp(nums,p)
int dp(int[] nums,int p)

base case

对边界问题进行处理。这里的边界问题就是当索引 p 到达数组末尾时,不需要跳跃

if(p >= nums.length - 1){
    return 0;
}

使用备忘录数组解决重叠子问题,写出动态规划解法的代码

public int jump(int[] nums) {
    int n = nums.length;
    //memo[i] 表示从 0 到 i 下标最少跳跃次数 
    int[] memo = new int[n];
    //将数组初始化为一个不可能取到的值,比如 n
    //(因为从 0 到 n-1 最多 n-1 步)
    Arrays.fill(memo, n);
    return dp(nums, 0, memo);
}

public int dp(int[] nums, int p, int[] memo) {
    int n = nums.length;
    //base case
    if (p >= n - 1) {
        return 0;
    }
    if (memo[p] != n) {
        return memo[p];
    }
    //获取索引 p 中的跳跃步数,做为选择列表
    int steps = nums[p];
    for (int i = 1; i <= steps; i++) {
        //写出子问题
        int subProblem = dp(nums, p + i, memo);
        //写出状态转移方程
        memo[p] = Math.min(memo[p], subProblem + 1);
    }
    return memo[p];
}

贪心算法解法

刚才的动态规划思路穷举了所有的子问题,然后取最小的作为结果。而贪心算法并不穷举所有子问题,而是每次做出最优的选择

贪心算法-01:跳跃游戏,手把手带你刷力扣Hot100,贪心算法,游戏,算法

对于这个 0 下标来说,有1、2、3 三种跳法。其中选择跳两步到 2 下标,然后再跳 4 步,能挑到最远距离。所以我们只选择这种情况来遍历,这就是我们的最优解

我们使用 end 来记录 :“目前能够到达的最远距离”。以上图为例,当 i = 0 时,我们能够到达的最远距离为 3 下标。

我们使用 farthest 来记录 : “以当前下标为起点能够跳到的最远距离”。以上图为例,当 i = 0 时,我们能够到达的最远距离为 3 下标;当 i = 2 时,我们能够到达的最远距离就是 6 下标。

那么我们就要选择能够跳的最远的下标作为我们的最优解。当我们以 0 下标为起点时,“目前能够到达的最远距离” 是 3 下标,所以 end = 3.

我们能够选择的下标中(能选择1、2、3 下标),2下标能跳的最远,最远能跳到 6 下标,farthest = 6。所以我们以 2 下标为目的地进行一次跳跃 。

所以我们遍历数组中每一个下标的目的,就是为了找到 “以这个下标为起始点,能够跳到最远距离”,当遍历的下标超出了目前我们能够到达的最远距离,我们进行一次跳跃,并更新 “目前能够到达的最远距离” end

public int jump(int[] nums) {
    int n = nums.length;
    int end = 0, farthest = 0;
    int jumps = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(nums[i] + i, farthest);
        //当下标遍历到我们目前能够到达的最远距离时,进行一次跳跃
        if (end == i) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

 力扣55、跳跃游戏

贪心算法-01:跳跃游戏,手把手带你刷力扣Hot100,贪心算法,游戏,算法

这道题比较简单,我们只需要判断跳到的最远距离是否能够超出数组长度即可

class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0;
        int n = nums.length;
        for(int i = 0;i < n - 1;i++){
            farthest = Math.max(farthest,i+nums[i]);
            if(farthest <= i){
                return false;
            }
        }
        return farthest >= n - 1;
    }
}

 问题1:farthest <= i 代表着什么?

farthest代表能够跳到的最远距离(最远下标),如果farthest <= i ,说明 i 下标无法被越过文章来源地址https://www.toymoban.com/news/detail-814996.html

  • 当 farthest 等于 i 时,表示当前位置 i 是一个零值,无法从该位置继续向后跳跃。但凡 i 下标有一个非零值,farthest 都应该更新为 nums[i] + i
  • 当 farthest 小于 i 时,表示在之前的跳跃过程中,最远距离已经被超过了,不再有效

到了这里,关于贪心算法-01:跳跃游戏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 手把手带你调参Yolo v5(二)

    来源:投稿 作者:王同学 ​​​​​​​编辑:学姐 今天我们继续上次的YOLOv5参数解析,这次主要解析源码中train.py文件中包含的参数。 1.1\\\'--weights\\\' 1.2\\\'--cfg\\\' 1.3\\\'--data\\\' 1.4\\\'--hyp\\\' 1.5\\\'--epochs\\\' 1.6\\\'--batch-size\\\' 1.7\\\'--imgsz\\\', \\\'--img\\\', \\\'--img-size\\\' 1.8\\\'--rect\\\'🍀 1.9\\\'--resume\\\'🍀 1.10\\\'--nosave\\\' 1.11\\\'--nova

    2024年02月05日
    浏览(54)
  • DAY37:贪心算法(四)跳跃游戏+跳跃游戏Ⅱ

    给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 示例 2: 提示: 1 = nums.length = 3 * 104 0 = nums[i] = 105 思路 游戏大致规则如下图。每一步代表着能跳跃的最大长

    2024年02月12日
    浏览(44)
  • 从0手把手带你搭建pytorch深度学习

    目录 一、查看电脑有NVIDIA显卡没 二、更新电脑驱动 三、安装CUDA ToolKit和CUDNN 1、查看显卡驱动版本 2、查看合适的CUDA版本 3、下载CUDA ToolKit 4、安装CUDA 5、查看是否安装成功 6、安装CUDNN 7、CUDNN配置 四、安装anaconda 五、安装pycharm 六、搭建pytorch深度学习环境 1、进入Anaconda Pr

    2024年02月07日
    浏览(50)
  • 手把手带你实现DQN(TensorFlow2)

            大家好,今天给大家带来DQN的思路及实现方法。         关于DQN,就不用我多做介绍了,我会以最简短明白的阐述讲解DQN,尽量让你在10分钟内理清思路。         非常重要的一点!!!         非常重要的一点!!!我在GitHub上下载了DQN代码,跑完后,我重写一

    2023年04月08日
    浏览(55)
  • 【手把手带你学JavaSE】第六篇:类和对象

    对了!给大家推荐一个刷题学习、面试神器——牛客网 里面有非常多的题库,跟面试经验~非常的良心!! 什么是类? 什么是对象? 怎么去理解这两个抽象的概念呢? Java是一门纯面向对象的语言(Object Oriented Program,继承OOP),在面向对象的世界里,一切皆为对象。 面向对象

    2023年04月20日
    浏览(52)
  • 手把手带你配置一个DHCP服务器

    最近部门内部成立一个网络兴趣小组,初衷是通过网络知识学习,在遇到网络问题时能够承担起一个与网络侧同学有效沟通的“连接人”的角色,求学这么多年其实也陆续学了不少的网络相关课程,本科的计算机网络、硕士的高等计网等,不过当时大多都停留在理论层面,趁

    2024年02月05日
    浏览(83)
  • 实战项目:手把手带你实现一个高并发内存池

    1.这个项目做的是什么? 当前项目是实现一个高并发的内存池,他的原型是google的一个开源项目tcmalloc,tcmalloc全称Thread-Caching Malloc,即线程缓存的malloc,实现了高效的多线程内存管理,用于替代系统的内存分配相关的函数(malloc、free)。 2.项目目标 模拟实现出一个自己的高

    2023年04月26日
    浏览(69)
  • 手把手带你啃透比特币白皮书-摘要

    很多人虽然了解了区块链,也可能参与了一些项目,但是可能没有见过比特币白皮书,也没有读过。我接下来就要和大家聊一聊,什么是白皮书,尤其是来给大家精读一下比特币的白皮书。 通过比特币白皮书,你能够 了解到真正的白皮书应该是什么样形式的 。因为很多人可

    2024年02月02日
    浏览(55)
  • 手把手带你做一套毕业设计-征程开启

     本文是《Vue + SpringBoot前后端分离项目实战》专栏的开篇,文本将会包含我们创作这个专栏的初衷,专栏的主体内容,以及我们专栏的后续规划。关于这套毕业设计的作者呢前端部分由狗哥负责,服务端部分则由天哥操刀。我们力求毕业生或者新手通过学完本专栏,可以开心

    2023年04月10日
    浏览(154)
  • 真手把手带你跑r3live

    实验室来了台机器人,上面的设备是依据r3live的设备选的,因为R3LIVE的效果太好了,特别感谢大佬的开源精神。这几天把车子跑起来,就打算写个博客记录一下。 本人能力有限,可能某些地方会有些问题,若发现问题,还请指正。 效果如下: 在多传感器融合slam中,由于会集

    2024年02月09日
    浏览(73)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包