79 lines
2.1 KiB
Markdown
79 lines
2.1 KiB
Markdown
|
||
## 题目地址
|
||
https://leetcode.com/problems/jump-game/description/
|
||
|
||
## 题目描述
|
||
```
|
||
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.
|
||
|
||
Example 1:
|
||
|
||
Input: [2,3,1,1,4]
|
||
Output: true
|
||
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
|
||
Example 2:
|
||
|
||
Input: [3,2,1,0,4]
|
||
Output: false
|
||
Explanation: You will always arrive at index 3 no matter what. Its maximum
|
||
jump length is 0, which makes it impossible to reach the last index.
|
||
|
||
```
|
||
|
||
## 思路
|
||
|
||
这道题目是一道典型的`贪心`类型题目。思路就是用一个变量记录当前能够到达的最大的索引，我们逐个遍历数组中的元素去更新这个索引。变量完成判断这个索引是否大于数组下表即可。
|
||
## 关键点解析
|
||
|
||
- 建模 (记录和更新当前位置能够到达的最大的索引即可)
|
||
|
||
## 代码
|
||
|
||
* 语言支持: Javascript，Python3
|
||
|
||
```js
|
||
/**
|
||
* @param {number[]} nums
|
||
* @return {boolean}
|
||
*/
|
||
var canJump = function(nums) {
|
||
let max = 0; // 能够走到的数组下标
|
||
|
||
for(let i = 0; i < nums.length; i++) {
|
||
if (max < i) return false; // 当前这一步都走不到，后面更走不到了
|
||
max = Math.max(nums[i] + i, max);
|
||
}
|
||
|
||
return max >= nums.length - 1
|
||
};
|
||
|
||
```
|
||
Python3 Code:
|
||
```Python
|
||
class Solution:
|
||
def canJump(self, nums: List[int]) -> bool:
|
||
"""思路同上"""
|
||
_max = 0
|
||
_len = len(nums)
|
||
for i in range(_len-1):
|
||
if _max < i:
|
||
return False
|
||
_max = max(_max, nums[i] + i)
|
||
# 下面这个判断可有可无，但提交的时候数据会好看点
|
||
if _max >= _len - 1:
|
||
return True
|
||
return _max >= _len - 1
|
||
```
|
||
|
||
***复杂度分析***
|
||
- 时间复杂度：$O(N)$
|
||
- 空间复杂度：$O(1)$
|
||
|
||
更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经30K star啦。
|
||
|
||
大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
|