当前位置:网站首页>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)
参考
边栏推荐
- nfs挂载服务器,解决挂载后无法更改用户id,无法修改、写文件,文件只读权限Read-only file system等问题
- 手把手教你Charles抓包工具使用
- MySQL数据库的主从复制部署详解
- Transferrin (TF) Modified Paclitaxel (PTX) Liposomes (TF-PTX-LP) | Transferrin (Tf) Modified Curcumin Liposomes
- C语言详解系列——关于调试那些事
- UnitTest中的Path must be within the project 问题
- 机器学习模型验证:被低估的重要一环
- 优雅退出在Golang中的实现
- 铱钌合金/氧化铱仿生纳米酶|钯纳米酶|GMP-Pd纳米酶|金钯复合纳米酶|三元金属Pd-M-Ir纳米酶|中空金铂合金纳米笼核-多空二氧化硅壳纳米酶
- 2020 ICPC Shanghai Site G
猜你喜欢
FEMRL: A Framework for Large-Scale Privacy-Preserving Linkage of Patients’ Electronic Health Rec Paper Summary
线性结构----链表
机器学习|模型评估——AUC
A fullGC problem troubleshooting caused by groovy
三子棋的设计和代码
UE4 - 河流流体插件Fluid Flux
"Distributed Microservice E-commerce" Topic (1) - Project Introduction
laya打包发布apk
The most complete GIS related software in history (CAD, FME, ArcGIS, ArcGISPro)
力扣150-逆波兰表达式求值——栈实现
随机推荐
[SemiDrive source code analysis] [MailBox inter-core communication] 52 - DCF Notify implementation principle analysis and code combat
《分布式微服务电商》专题(一)-项目简介
铱钌合金/氧化铱仿生纳米酶|钯纳米酶|GMP-Pd纳米酶|金钯复合纳米酶|三元金属Pd-M-Ir纳米酶|中空金铂合金纳米笼核-多空二氧化硅壳纳米酶
The servlet mapping path matching resolution
【SemiDrive源码分析】【MailBox核间通信】51 - DCF_IPCC_Property实现原理分析 及 代码实战
深度学习实战教程(一):感知器
servlet映射路径匹配解析
机器学习|模型评估——AUC
YOLOv3 SPP source analysis
「POJ 3666」Making the Grade 题解(两种做法)
win7开机有画面进系统黑屏怎么办
mysql踩坑----case when then用法
怎么完全卸载赛门铁克_Symantec卸载方法,赛门铁克卸载「建议收藏」
转铁蛋白修饰蛇床子素长循环脂质体/负载三七皂苷R1的PEG-PLGA纳米粒([email protected] NPs)
Knowledge map Knowledge Graph
Colocate Join :ClickHouse的一种高性能分布式join查询模型
壁仞推出全球最大算力芯片,号称以7nm超越英伟达4nm最新GPU
手把手教你Charles抓包工具使用
转铁蛋白Tf功能化β-榄香烯-雷公藤红素/紫杉醇PLGA纳米粒/雷公藤甲素脂质体(化学试剂)
nfs挂载服务器,解决挂载后无法更改用户id,无法修改、写文件,文件只读权限Read-only file system等问题