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题解
|