给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
- 方法一：正向遍历，计算每个位置开始能到达的最高处
class Solution {
public:
bool canJump(vector& nums) {
int reach=0;//记录当前能到达的最远处
//i遍历数组，i要始终处于能到达的位置，如果reach已经大于nums边界已经可以退出循环
for(int i=0;i<=reach&&reach
reach=max(reach,i+nums[i]);//当前位置的最远边界为当前位置能加最大步数和最远边界，二者取较大
}
return reach+1>=nums.size();//边界是数组下标，从0开始，所以要加1
}
};
-
时间复杂度O(n)
-
空间复杂度O(1)
-
思路
- 对于数组中的任意一个位置y，只要当前位置x加上x处可走的最大步数，二者之和大于y，则可以到达y
- 一次遍历数组，维护当前的最远边界
- 最后比较最远边界是否可以到达数组大小，如果是则返回true
-
法二：逆向遍历数组，从末尾看能不能下降到0
class Solution {
public:
bool canJump(vector& nums) {
int left=nums.size()-1;//左边界
//从后往前遍历数组，如果i所指的位置加上当前数组值大于lef，则当前的左边界为i
for(int i=nums.size()-2;i>=0;i--)
{
if(nums[i]+i>=left) left=i;
}
//最后判断左边界能否小于0，即从终点能否回到起点
return left<=0;
}
};
- 法三：动态规划
class Solution {
public:
bool canJump(vector& nums) {
vector f(nums.size(),0);
f[0]=nums[0]-1;//初始位置可以到达的最远距离就是0加上当前可以走的步数
//依次确定经过每一个位置的最远距离
for(int i=1;i
f[i]=max(f[i-1],i+nums[i-1]);
if(f[i]==i) return false;//表示不能往后走了，返回false
}
return true;
}
};
- 时间复杂度O(n)
- 空间复杂度O(n)
- 思路
- f[i]表示当前位置可以到达的最远位置
- 状态转移方程：f[i]=max(f[i-1],i+nums[i-1])
- 当前位置可以到达的最远位置有两种情况，如果不到达当前位置则是前一个位置可以到达的最远位置即f[i-1]，如果从当前位置出发则是i+nums[i]，二者取最大值
- 每次比较当前位置可以到达的最远位置是否与当前位置相同，如果相同则表示无法继续向后走，返回false
- 如果for循环正常退出则表示可以走到末尾，返回true
