前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >☆打卡算法☆LeetCode 45、跳跃游戏II 算法解析

☆打卡算法☆LeetCode 45、跳跃游戏II 算法解析

作者头像
恬静的小魔龙
发布2022-08-07 10:01:47
2790
发布2022-08-07 10:01:47
举报
文章被收录于专栏:Unity3DUnity3D
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个非负整数数组,数组中每个元素代表可以跳跃的最大高度,使用最少的跳跃次数跳到数组最后一个位置。”

题目链接:

来源:力扣(LeetCode)

链接:45. 跳跃游戏 II - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

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

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

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

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

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

二、解题

1、思路分析

这个题是典型的贪心算法,通过局部最优解得到全局最优解,可以使用反向查找出发位置,来找到最优解。

首先,我们的目标是找到通过跳跃可以到达最后的一个位置,我们可以贪心地选择距离最后一个位置最远的那个位置,也就是下标最小的位置,然后遍历数组。

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

2、代码实现

代码参考:

代码语言:javascript
复制
public class Solution {
    public int Jump(int[] nums) {
        int count = 0;
        int length = nums.Length;
        for (int i = length - 1; i > 0;) {
            int k = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] + j >= i) {
                    k = j;
                }
            }
            i = k;
            count++;
        }
        return count;
    }
}
image.png
image.png

3、时间复杂度

时间复杂度 : O(n)

其中n是数组的长度。

空间复杂度: O(1)

只需要常数级别的空间存放变量。

三、总结

从尾往头部进行遍历x_i。

如果要最快到达这个节点, 则只需要找到该节点之前任意一点满足 x_i+i 大于等于 n 即可, 且 i 在满足条件的所有下标中最小。

以此类推, 直到找到头节点。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-11-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
    • 1、算法题目
      • 2、题目描述
      • 二、解题
        • 1、思路分析
          • 2、代码实现
            • 3、时间复杂度
            • 三、总结
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档