leetcode每日一题——45.跳跃游戏II(面试经典150题)

这篇具有很好参考价值的文章主要介绍了leetcode每日一题——45.跳跃游戏II(面试经典150题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目描述与要求

45. 跳跃游戏 II - 力扣(LeetCode)

题目描述

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

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

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

示例

示例1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例2:

输入: nums = [2,3,0,1,4]
输出: 2

提示

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

二、解题思路

总的思路:

       先分析题目,跳跃游戏II与跳跃游戏相比更加复杂了一点,跳跃游戏只需要判断能否通过跳跃到达最后一个下标,而跳跃游戏II需要我们计算出跳跃到最后一个下标所需要的最小跳跃次数。对此,我们还是可以采用贪心算法的思想,我们找出每一个下标所能到达的最远位置,从而来找到最远位置是最后一个下标的下标,进而判断出什么时候进行跳跃,同时统计跳跃次数即可。这是对整体的一个构思。从整体构思可以看出我们需要解决两个问题,一个是我们怎么判断是否到了最后一个下标,另一个就是我们怎么去统计跳跃次数。(因为当我们在每一个下标的时候可能会有多种跳跃方案)

      首先解决怎么判断是否到最后一个下标,首先题目告诉我们“题目保证可以到达nums[n-1]”,因此不需要我们对其进行判断,而是只需要通过计算来获得最远位置为nunsSize-1。因此我们可以采用for循环的方法,遍历整个数组,依次计算i+nums[i](当前下标所能到达的最远位置)的值,并将其与当下的最远位置进行比较,取较大值。以此不断计算,我们就可以让site=numsSize-1。这样第一个问题解决了。【求每个范围的最远位置,最后找到最后一个下标】

       然后第二个问题就是我们怎么去计算这个跳跃次数。当我们在一个下标上的时候,我们会获得一个跳跃范围,也就是下一个下标到所能到达的最远位置下标。那我们怎么去判断什么时候跳跃呢,因为可能我走一步更好,也可能走两步更好,这就是相对于详细的,就是跳跃一次跳跃几步,但我们只需要知道跳跃次数,而对跳跃步数不用管。因而我们只需要知道它什么时候一定要跳跃一次就行。

       那当我们可以在一个范围内随意选择跳跃时什么时候我们必须进行跳跃呢?是不是我们到达了这个范围的边界的时候,因为当我们访问到这个范围的边界的时候,这个范围的最远位置我们就已经统计出来了,因此我们肯定会进行跳跃,然后继续更新边界,直至到达最后一个下标。最开始的边界设置为0,因为从第一个下标出来我们必须要跳跃一步(至于跳到了哪个下标我们不知道),然后我们将这个边界更新成目前得到的最远下标,然后继续进行找在这一个范围内所能到的最远位置【局部最优解】,因为我们不需要知道具体跳跃到了哪个下标,所以我们以每个范围的边界为条件来计算跳跃次数,一旦到达边界则次数增加,直至到达最后一个下标,则结束,如此就能够得到最小次数。

       实际上就是一个不断扩大范围的过程,直至将范围扩大至最后一个下标,在这个过程中,有几次到达边界就意味着跳跃了几次。

具体步骤:

①定义最小跳跃次数num,范围边界end,最远位置site变量

②定义max函数用来更新最远位置

③遍历数组更新最远位置并计算跳跃次数

④返回跳跃次数文章来源地址https://www.toymoban.com/news/detail-540681.html


三、具体代码【C语言】

int max(int x,int y){
    return x>y?x:y;
}
int jump(int* nums, int numsSize){
    int num = 0;//达到nums[n-1]的最小跳跃次数
    int end = 0;//用来标志所能到达的最远边界
    int site=0;//能到达的最远位置
    for (int i = 0; i < numsSize-1; i++)
    {
        //通过遍历来找出每一个下标所能跳跃到的最远位置,取最远的
        site = max(site,i+nums[i]);
        //如果已经遍历到了所能到达的范围的边界,此时必须进行一次跳跃,同时更新所能到达的范围的边界
        if (i == end)
        {
            end = site;
            num++;
        }
    }
    return num;
}

到了这里,关于leetcode每日一题——45.跳跃游戏II(面试经典150题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Golang | Leetcode Golang题解之第45题跳跃游戏II

    题目: 题解:

    2024年04月25日
    浏览(54)
  • 跳跃游戏 + 45. 跳跃游戏 II

    给你一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回  true  ;否则,返回  false  。 示例 1: 示例 2: 解析: 每次遍历,只需要贪心跳到最远即可

    2024年02月04日
    浏览(42)
  • 贪心 55. 跳跃游戏 45.跳跃游戏 II

    题目: 给定非负数组,初始位置在数组第一格,数组值是可以选择的最大跳跃步数,判断能不能达到数组末尾。 示例  1: * 输入: [2,3,1,1,4] * 输出: true * 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例  2: * 输入: [3,2,1,0,4] * 输出

    2024年03月21日
    浏览(47)
  • 代码随想录:55. 跳跃游戏;45. 跳跃游戏 II

    给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 示例 2: 其实跳几步无所谓,关键在于可跳的覆盖范围! 不一定非要明确一次究竟跳几步,每次取最

    2023年04月11日
    浏览(48)
  • 力扣45. 跳跃游戏 II

    Problem: 45. 跳跃游戏 II Problem: 55.跳跃游戏 该题在上述的基础上,我们每次 先求取当前可跳区间内的最远距离farthest;每当走到当前的区间胃部时(end == i):跳跃步数加一(jumps++),同时将下一次的可跳的最远区间更新(end = farthest;) 时间复杂度: O ( n ) O(n) O ( n ) ;其中 n n n 为数组

    2024年02月22日
    浏览(63)
  • 力扣:45. 跳跃游戏 II

    动态规划: 1.声明一个dp数组来表示到下标i时要跳转的最小次数,同时要个每个dp数组的值赋值为最大。之后初始化dp【0】=0,用for循环来进行遍历下标i和遍历下标i之前的值,判断条件为如果i之前的某个下标跳转的距离=i时要根新dp【i】的值 ,递推公式为dp【i】=math,min(dp[

    2024年02月20日
    浏览(43)
  • 跳跃游戏 II——力扣45

    题目描述 解法一 贪心

    2024年02月13日
    浏览(41)
  • 算法 贪心2 || 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

    如果想到其实 最终利润是可以分解的 ,那么本题就很容易了! 如何分解呢? 假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。 此时就是把利润分解为每天为单位的维度,而不是从0天到第3天整体去

    2023年04月13日
    浏览(49)
  • 代码随想录 第三十二天 45.跳跃游戏 II||122.买卖股票的最佳时机 II55. 跳跃游戏

    力扣题目链接(opens new window) 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例  1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位

    2024年02月15日
    浏览(56)
  • Day32 贪心算法 part02 122. 买卖股票的最佳时机 II 55. 跳跃游戏 45. 跳跃游戏 II

    思路:计算每天的利润,利润如果为正,加到结果中去

    2024年01月19日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包