LC55. 跳跃游戏
题目描述
这是 LeetCode 上的(55. 跳跃游戏) ,难度为 中等。
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
示例 1:
1 |
|
示例 2:
1 |
|
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 105
题解
贪心
- 题目描述意思
- 如果下标为3,往后数三个格子都可以成为起跳点
- 每次都寻找能够跳到的最远距离(贪心)
- 当
i
指针能够追到k
指针的时候,说明k
指针原地不动
- 如若不能,说明
k
指针已经越过数组长度,即能达到最后一个下标
代码
1 |
|
复杂度
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
最后
- 本题题目及其具有误导性,很容易看不懂题目,难搞
LC55. 跳跃游戏
https://blog.daynoti.com/posts/33470/