跳跃游戏II(python)
2023-04-18 14:24:02 时间
链接: https://leetcode.cn/problems/jump-game-ii
题目描述:
给定一个长度为 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 <= 1 0 4 10^4 104
- 0 <= nums[i] <= 1000
- 题目保证可以到达 nums[n-1]
思路
用贪心算法来做是最简单,时间效率最高的。动态规划会超时。
end保存上一次跳跃能到达的最大位置,max_pos保存当前能到达的最大位置,count计算跳跃的次数
如果上一次跳跃不能到达终点,那么跳跃次数加1,更新目前能到达的最大位置
代码
class Solution:
def jump(self, nums: List[int]) -> int:
end,max_pos=0,0
count=0
for i in range(len(nums)-1):
max_pos=max(max_pos,nums[i]+i)
if i==end:
end=max_pos
count+=1
return count
相关文章
- 开源和云原生技术如何使API策略现代化
- 前后端分离开发模式下后端质量的保证 —— 单元测试
- python自动化测试(2)-自动化基本技术原理
- Direct3D Draw函数 异步调用原理解析
- 用JavaScript编写一个Java虚拟机?谈谈哗众取宠的BicaVM
- HTML5以及WebGL
- MVC与WebForm最大的区别
- Asp.Net Mvc: 浅析TempData机制
- 生成你的自定义密码本Python
- python奇葩反爬-你是故意的还是不小心的
- Python、C++、Swift或任何其他语言会取代Java吗?为什么?
- python通过轮子安装第三方库(以Wordcloud为例)
- SpringBoot中对拦截器和过滤器的理解
- gazebo黑屏问题
- 81python装饰器
- golang执行命令 && 实时获取输出结果
- python项目中的“填坑”记录
- wagger也不好用了!API文档还得是Apipost
- 深入理解npm scripts
- 基于高层次综合器(Vivado HLS)的硬件优化[原创www.cnblogs.com/helesheng]