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,C++,Java,Python3 Javascript Code:
/**
* @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;
};C++ Code:
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
int k=0;
for(int i=0;i<n;i++)
{
if(i>k){
return false;
}
// 能跳到最后一个位置
if(k>=n-1){
return true;
}
// 从当前位置能跳的最远的位置
k = max(k, i+nums[i]);
}
return k >= n-1;
}
};Java Code:
class Solution {
public boolean canJump(int[] nums) {
int n=nums.length;
int k=0;
for(int i=0;i<n;i++)
{
if(i>k){
return false;
}
// 能跳到最后一个位置
if(k>=n-1){
return true;
}
// 从当前位置能跳的最远的位置
k = Math.max(k, i+nums[i]);
}
return k >= n-1;
}
}Python3 Code:
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 题解