题目描述
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
样例
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
算法1
(动态规划) $O(n^2)$
dp的角度有很多,这里采用从前往后,逐步拓展的方式,采用染色法, 在每个染色的点,把下一步可到达的点都染色,当遍历到没染色点时,跳过,判断最后一个点是否染色。
时间复杂度
参考文献
C++ 代码
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<bool> f(n,false);
f[0] = true;
for(int i=0;i<n;i++){
if(!f[i]) continue;
int v = min(n-1,i+nums[i]);
for(int j=i+1;j<=v;j++)
f[j]=true;
}
return f[n-1];
}
};
算法2
(贪心) $O(n)$
为什么能用贪心来做呢,因为可以发现前i个点染色后的都是一个连续区间,左端点是0,右端点不妨记为k,也就是说不会出现中间是没染色的点,所以只需要记录最大的位置k(右端点),判断新的位置是否不大于k,能不能继续形成一个新的区间。
时间复杂度
参考文献
C++ 代码
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int maxv = 0;
for(int i=0;i<n;i++){
if(i>maxv) return false; //maxv和i之间有未染色的点,存在不连续点
maxv = max(maxv, i+nums[i]);
}
return true;
}
};