【Leetcode刷题Python】55. 跳跃游戏
2023-09-14 09:12:58 时间
1 题目
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
2 解析
思路: 尽可能到达最远位置(贪心)。
如果能到达某个位置,那一定能到达它前面的所有位置。
方法: 初始化最远位置为 0,然后遍历数组,如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置。最后比较最远位置和数组长度。
复杂度:时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。
3 Python实现
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 初始化当前位置能到达的最远位置
max_k = 0
end_index = len(nums)-1
for i in range(len(nums)):
# 判断如果最远距离能够超过最后一个位置,提前结束,减少循环次数,能够提高运行时间
if max_k >= end_index:
return True
# 如果当前位置超过能到达位置的最大值,则失败
if i > max_k:
return False
# 更新最远位置
max_k = max(max_k, i+nums[i])
return True
相关文章
- 【Python】执行系统命令的常见用法
- Python进阶学习之特殊方法实例详析
- python数据结构之二叉树的统计与转换实例
- Python类属性的延迟计算
- Python 刷Leetcode题库,顺带学英语单词(30)
- Python 刷Leetcode题库,顺带学英语单词(15)
- Python Django 根路由命名空间URL解析方式代码示例
- Python编程语言学习:python中与数字相关的函数(取整等)、案例应用之详细攻略
- Python之ffmpeg:利用python编程基于ffmpeg将m4a格式音频文件转为mp3格式文件
- Python编程语言学习:python的列表的特殊应用之一行命令实现if判断中的两类判断
- Python之API:基于python语言调用华为云API(华为网站)实现特定功能
- Python编程专属骚技巧8
- 〖Python自动化办公篇⑳〗 - python实现邮件自动化 - 发送html邮件和带附件的邮件
- 〖Python接口自动化测试实战篇⑧〗- 小案例 - 使用python实现接口请求 [查询天行数据]
- Python从入门到爬虫案例实现~
- Python实现贝叶斯优化器(Bayes_opt)优化随机森林回归模型(RandomForestRegressor算法)项目实战
- 【LeetCode Python实现】8. 字符串转换整数 (atoi)(中等)
- 【LeetCode Python实现】737. 句子相似性 II(中等)
- 分享:Python发邮件告别smtplib,迎接zmail
- 【Leetcode刷题Python】232. 用栈实现队列
- 【Leetcode刷题Python】946. 验证栈序列
- 【Leetcode刷题Python】16. 最接近的三数之和
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 【Leetcode刷题Python】从列表list中创建一颗二叉树
- 【Leetcode刷题Python】1049. 最后一块石头的重量 II
- 深入学习Python库中的Pandas 和NumPy
- Python爬虫理论