专栏首页用户画像Leetcode No.45 跳跃游戏 II

Leetcode No.45 跳跃游戏 II

一、题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

假设你总是可以到达数组的最后一个位置。

二、解题思路

我们「贪心」地进行正向查找,每次找到可到达的最远位置,就可以在线性时间内得到最少的跳跃次数。

例如,对于数组 [2,3,1,2,4,2,3],初始位置是下标 0,从下标 0 出发,最远可到达下标 2。下标 0 可到达的位置中,下标 1 的值是 3,从下标 1 出发可以达到更远的位置,因此第一步到达下标 1。

从下标 1 出发,最远可到达下标 4。下标 1 可到达的位置中,下标 4 的值是 4 ,从下标 4 出发可以达到更远的位置,因此第二步到达下标 4。

在具体的实现中,我们维护当前能够到达的最大下标位置,记为边界。我们从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加 1。

在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次「不必要的跳跃次数」,因此我们不必访问最后一个元素。

三、代码

class Solution {
    public int jump(int[] nums) {
        int steps=0;
        int max=0;
        int end=0;
        int len=nums.length;
        for(int i=0;i<len-1;i++){
            max=Math.max(max,i+nums[i]);
            if(i==end){
                end=max;
                steps++;
            }
        }
        return steps;
    }
}

四、复杂度分析

时间复杂度:O(n),其中 n是数组长度。

空间复杂度:O(1)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 45. 跳跃游戏 II

    CaesarChang张旭
  • leetcode 45 | 跳跃游戏 II(贪心)

    对于输入的数组[2,3,1,1,4],首先从位置0开始,位置0的元素是2,表示最大跳跃2个长度,那么在这里可以跳跃到位置1、2,在位置1可以跳跃3步,位置2跳跃...

    ACM算法日常
  • 【刷穿 LeetCode】45. 跳跃游戏 II(困难)

    我们定义 f(i) 为到达第 i 个位置所需要的最少步数,那么答案是 f(n - 1)。

    宫水三叶的刷题日记
  • ​LeetCode刷题实战45:跳跃游戏 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • Leetcode 45 跳跃游戏 II (贪心+数学)

    glm233
  • LeetCode 45. 跳跃游戏 II(贪心/BFS,难)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业...

    Michael阿明
  • LeetCode40-60题汇总,速度收藏!

    今天把最近发布的40-60篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很多人都没看过,如果对于算法感兴趣的,建议可以每篇认真阅读一...

    程序IT圈
  • LeetCode 55. 跳跃游戏(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请...

    Michael阿明
  • [Leetcode][python]Jump Game/Jump Game II/跳跃游戏/跳跃游戏 II

    数组中的每个值表示在当前位置最多能向前面跳几步,判断给出的数组是否否存在一种跳法跳到最后。

    蛮三刀酱
  • leetcode 第45题:跳跃游戏2

    我们的目的是要跳跃到最后一个点上,我们可以从最后一个点往左开始寻找,例如非负数组为 arr = {2,3,1,1,4,2,1},从最右边的 1 往左寻找,找那个...

    帅地
  • 9月技术文章汇总

    Leetcode名企之路
  • 【面试高频系列】修改数据范围,可以从「简单 BFS」变为「挖掘性质」的贪心 DP 题

    学习过 路径 DP 专题 的同学应该知道,通常确定 DP 的「状态定义」有两种方法。

    ACM算法日常
  • 【leetcode刷题】T173-跳跃游戏 II

    可以用动态规划来做,对于所有的j=i,dp[i] = min(dp[j] + 1)

    木又AI帮
  • LeetCode1-100题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到100道题了。今天把发布的1-100篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • LeetCode45. 跳跃游戏 II

     还是以样例为例,[2,3,1,1,4],起点是nums[0] = 2,那么在nums[1] = 3和nums[2] = 1中我们应该选择哪个进行跳跃?很...

    mathor
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • LeetCode1-50题汇总,速度收藏!

    时间很快,公众号发布的LeetCode题目,已经达到50道题了。今天把发布的1-50篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很...

    程序IT圈
  • 【Leetcode】55. 跳跃游戏

    给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1:

    Leetcode名企之路
  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85

扫码关注云+社区

领取腾讯云代金券