Leetcode 55. Jump Game
2024-10-07 08:45:54
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4]
, return true
.
A = [3,2,1,0,4]
, return false
.
我一开始认为这是一道DP的题目。其实,可以维护一个maxReach,并对每个元素更新这个maxReach = max(maxReach, i + nums[i])。注意如果 i>maxReach,说明从起点开始能跳到的最远距离不到i, 所以i后面的点也就无法到达了。另外如果 maxReach >= n-1 说明已经可以跳到终点了,之后的点也就不用继续检查了。
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
maxReach = 0 for i in range(n):
if i>maxReach or maxReach >= n-1:
break
maxReach = max(maxReach, i+nums[i]) if maxReach < n-1:
return False
else:
return True
最新文章
- loadrunner11录制脚本打开IE9失败,浏览器崩溃,显示无法响应
- python3控制路由器--使用requests重启极路由.py
- Qt Script
- PyCharm 4.0下载(附keygen)
- rcp(插件开发) 如何查找自己定义的扩展点
- JavaScript对象之document对象
- VsCode 附加Chorme调试TS方法
- python之进程----Queue
- 0308-标签的用法(a,ul/ol,table)
- [BZOJ]2194: 快速傅立叶之二
- mysql 错误 ERROR 1030 Got error 28 from
- H5 29-div和span标签
- Django之Form组件(一)
- LeanCloud云引擎相关问题
- IOS-整体框架类图
- [EffectiveC++]item07:declare destructors virtual in polymorphic base class
- CF709A Juicer 模拟
- 自动更新GeoIP数据库
- 如何将Windows8系统的磁盘格式(GPT格式)转换成Windows 7系统的磁盘格式(MBR格式)
- 华为S3700交换机DHCP 配置