当前位置:网站首页>leetcode:45. 跳跃游戏II
leetcode:45. 跳跃游戏II
2022-08-10 20:24:00 【uncle_ll】
45. 跳跃游戏 II
来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/jump-game-ii
给你一个非负整数数组 nums
,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输`入: nums = [2,3,0,1,4]
输出: 2
提示:
- 1 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
- 0 < = n u m s [ i ] < = 1000 0 <= nums[i] <= 1000 0<=nums[i]<=1000
解法
- 贪心算法:从第一步起跳,然后找涵盖范围内能跳得最远的,然后之后以最远的那个为起点,开始找后续能跳得远的。
代码实现
贪心算法
- 原始实现
python实现
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
start = 0
end = 0 # 边界下标
step = 0
while end < len(nums)-1:
maxpos = 0
for i in range(start, end+1):
maxpos = max(maxpos, i+nums[i])
start = end # 下一条的起点
end = maxpos # 最远的边界
step += 1
return step
c++实现
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() <= 1) return 0;
int start = 0, end = 0;
int step = 0;
while (end < nums.size()-1) {
int maxpos = 0;
for (int i=start; i <= end; i++) {
maxpos = max(maxpos, i+nums[i]);
}
start = end;
end = maxpos;
step++;
}
return step;
}
};
复杂度分析
- 时间复杂度: O ( N 2 ) O(N^2) O(N2)
- 空间复杂度: O ( 1 ) O(1) O(1)
- 优化
从上面代码观察发现,其实被 while 包含的 for 循环中,i 是从头跑到尾的。
只需要在一次 跳跃 完成时,更新下一次 能跳到最远的距离。
并以此刻作为时机来更新 跳跃 次数。
就可以在一次 for 循环中处理。
python实现
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
max_position = 0
end = 0
step = 0
for i in range(len(nums)-1):
max_position = max(max_position, i+nums[i])
if i == end:
end = max_position
step += 1
return step
c++实现
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() <= 1) return 0;
int end = 0;
int maxPostion = 0;
int step = 0;
for (int i=0; i<nums.size()-1; i++) {
maxPostion = max(maxPostion, i+nums[i]);
if (i == end) {
end = maxPostion;
step++;
}
}
return step;
}
};
复杂度分析
- 时间复杂度: O ( N ) O(N) O(N)
- 空间复杂度: O ( 1 ) O(1) O(1)
参考
边栏推荐
- [SemiDrive source code analysis] [MailBox inter-core communication] 51 - DCF_IPCC_Property implementation principle analysis and code combat
- [CNN] Brush SOTA's trick
- cordova 安装错误 Command failed: powershell 解决方法
- Implementation of graceful exit in Golang
- C语言系列——猜名次、猜凶手、打印杨辉三角
- 电信保温杯笔记——《统计学习方法(第二版)——李航》第17章 潜在语义分析
- 铁蛋白颗粒负载雷替曲塞/培美曲塞/磺胺地索辛/金刚烷(科研试剂)
- 爬虫基本原理介绍、实现以及问题解决
- Heme - gold nanoparticles (Heme - AuNP) composite nanometer enzyme | gold nanoparticles nuclear porous hollow carbon nanometer spherical shell (Au @ HCNs) nano enzyme
- 铁蛋白颗粒Tf包载多肽/凝集素/细胞色素C/超氧化物歧化酶/多柔比星(定制服务)
猜你喜欢
A fullGC problem troubleshooting caused by groovy
[email protected] nanomimetic e"/>
Water-soluble alloy quantum dot nanozymes|CuMoS nanozymes|porous silicon-based Pt(Au) nanozymes|[email protected] nanomimetic e
Echart饼状图标注遮盖解决方案汇总
线性结构----链表
设备管理中数据聚类处理
leetcode 547.省份数量 并查集
ACM MM 2022 统一归一化:加速Transformer工业部署的归一化方法
网络虚拟化
Knowledge map Knowledge Graph
spark学习笔记(九)——sparkSQL核心编程-DataFrame/DataSet/DF、DS、RDD三者之间的转换关系
随机推荐
手把手教你Charles抓包工具使用
Transferrin (TF) Modified Paclitaxel (PTX) Liposomes (TF-PTX-LP) | Transferrin (Tf) Modified Curcumin Liposomes
[CNN] Brush SOTA's trick
spark学习笔记(九)——sparkSQL核心编程-DataFrame/DataSet/DF、DS、RDD三者之间的转换关系
2019河北省大学生程序设计竞赛部分题题解
电脑重装系统Win11格式化硬盘的详细方法
力扣150-逆波兰表达式求值——栈实现
爬虫基本原理介绍、实现以及问题解决
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
双 TL431 级联振荡器
一次由groovy引起的fullGC问题排查
电脑开不了机是什么原因?
参天生长大模型:昇腾AI如何强壮模型开发与创新之根?
Transferrin-modified vincristine-tetrandrine liposomes | transferrin-modified co-loaded paclitaxel and genistein liposomes (reagents)
【luogu CF1534F2】Falling Sand (Hard Version)(性质)(dfs)(线段树 / 单调队列 / 贪心)
Random函数用法
转铁蛋白Tf功能化β-榄香烯-雷公藤红素/紫杉醇PLGA纳米粒/雷公藤甲素脂质体(化学试剂)
The servlet mapping path matching resolution
线性结构----链表
铁蛋白颗粒负载雷替曲塞/培美曲塞/磺胺地索辛/金刚烷(科研试剂)