算法:经典贪心算法--跳一跳[2]

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

算法:经典贪心算法--跳一跳[2],算法,算法,贪心算法,贪心,最优策略,数据结构,java

1、题目:

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

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

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]


2、分析特点:

  • 这道题是典型的贪心算法,通过局部最优解得到全局最优解。
  • 反向思维解决每次都找最左位置-最后一个位置,距离最远,即最大概率最小跳跃次数。
  • 【解题口:寻找最左位置–寻找的次数,即最小跳跃次数】

我们的目标是到达数组的最后一个位置,因此我们可以考虑最后一步跳跃前所在的位置,该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置,那么我们应该如何进行选择呢?直观上来看,我们可以「贪心」地选择距离最后一个位置最远的那个位置,也就是对应下标最小的那个位置。因此,我们可以从左到右遍历数组,选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后,我们继续贪心地寻找倒数第二步跳跃前所在的位置,以此类推,直到找到数组的开始位置。


3、代码:

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

4、复杂度分析:

  • 时间复杂度:O(n2),其中 nnn 是数组长度。有两层嵌套循环,在最坏的情况下,例如数组中的所有元素都是 1,position 需要遍历数组中的每个位置,对于 position 的每个值都有一次循环。
  • 空间复杂度:O(1)。

5、总结:

  • 这道题是典型的贪心算法,通过局部最优解得到全局最优解。
  • 反向思维解决每次都找最左位置-最后一个位置,距离最远,即最大概率最小跳跃次数。
  • 【解题口:寻找最左位置–寻找的次数,即最小跳跃次数】

我们的目标是到达数组的最后一个位置,因此我们可以考虑最后一步跳跃前所在的位置,该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置,那么我们应该如何进行选择呢?直观上来看,我们可以「贪心」地选择距离最后一个位置最远的那个位置,也就是对应下标最小的那个位置。因此,我们可以从左到右遍历数组,选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后,我们继续贪心地寻找倒数第二步跳跃前所在的位置,以此类推,直到找到数组的开始位置。




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!文章来源地址https://www.toymoban.com/news/detail-719377.html

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

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

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

相关文章

  • 计算机算法分析与设计(14)---贪心算法(会场安排问题和最优服务次序问题)

     假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 数据输入: 第 1 1 1 行中有一个整数 n n n ,表示有 n n n 个待安排的活动。接下来的 n n n 行中,每行有 2 2 2 个正整数,分别表示 n n n 个待安排的活动的开始时间和结束

    2024年02月02日
    浏览(44)
  • Java 贪心算法经典问题解决

    题目 一块金条切成两半,是需要花费和长度数值一样的铜板的。比如 长度为20的 金条,不管切成长度多大的两半,都要花费20个铜 板。一群人想整分整块金 条,怎么分最省铜板? 例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分

    2024年02月16日
    浏览(62)
  • 探索经典算法:贪心、分治、动态规划等

    贪心算法是一种常见的算法范式,通常在解决最优化问题中使用。 贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法范式。其核心思想是选择每一步的最佳解决方案,以期望达到最终的全局最优解。这种算法特点在于只考虑局部最优解,而不会回溯或重新考虑

    2024年02月05日
    浏览(44)
  • 贪心算法:简单而高效的优化策略

    在计算机科学中,贪心算法是一种简单而高效的优化策略,用于解决许多组合优化问题。虽然它并不适用于所有问题,但在一些特定情况下,贪心算法能够产生近似最优解,而且计算成本较低。在本文中,我们将深入探讨贪心算法的原理、适用性以及一些经典应用。同时在以

    2024年02月11日
    浏览(38)
  • 贪心算法及几个经典例子c语言

    一、基本概念: 所谓贪心算法是指,在对问题求解时,总是做出在 当前看来是最好的选择 。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的 局部最优解 。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不

    2024年02月01日
    浏览(34)
  • <算法>贪心策略设计并解决会场安排问题

    🎉  每个不曾起舞的日子都是对生命的辜负 🎉 写在前面 期末考试邻近,为了更好的应对《算法设计与分析》这门课程,我把书上以及老师讲过的案例都详细的做一个重现及解剖,让你熟记每一个潜在的考点,希望能给大家帮助。 🎉 目录 问题描述  贪心策略  算法设计

    2024年02月08日
    浏览(93)
  • class092 贪心经典题目专题4【左程云算法】

    2024-4-23 14:00:04 以下内容源自《【左程云算法】》 仅供学习交流使用 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN@日星月云 博客主页是https://jsss-1.blog.csdn.net 禁止其他平台发布时删除以上此话 算法讲解092【必备】贪心经典题目专题4 先占个位 迎着日光

    2024年04月26日
    浏览(39)
  • 一道经典的小学数学题,和它背后的贪心算法(35)

    小朋友们好,大朋友们好! 我是猫妹,一名爱上Python编程的小学生。 欢迎和猫妹一起,趣味学Python。 今日主题 这个五一小长假,你玩得怎么样? 今天,咱们先做一道经典的小学数学题,抛砖引玉,然后了解下贪心算法。 一个地主临终前留下了遗嘱,将自己的11头牛分给三

    2024年02月02日
    浏览(42)
  • 数据结构与算法——贪心算法简介

    贪心算法是一种算法范式,它遵循在每个阶段做出局部最优选择的问题解决启发式,希望找到全局最优。换句话说,贪心算法在每一步都选择最好的选项,而不考虑该选择对未来步骤的影响。 当一个问题可以分解成更小的子问题,并且每个子问题的解决方案可以组合起来解决

    2023年04月08日
    浏览(37)
  • 数据结构与算法(3)——贪心算法

    定义:所谓“贪心”,就是每次只考虑自己附近局部范围的最优解,但这种局部最优会导致全局最优。 考虑当前的附近一两步即可 455. 分发饼干 简评:简单的贪心算法,将“胃口”和“饼干”按升序排列后,每次都只考虑“胃口”最小的小孩,然后把最小的饼干给他,如果

    2024年02月07日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包