数据结构与算法-24.跳跃游戏
目录
数据结构与算法-24.跳跃游戏
关键词由CSDN通过智能技术生成
24、跳跃游戏
题目
24.0、贪心算法
对于序列【2，3，1，1，4】，维护一个rightMost，表示能够到达的最右端的坐标
rightMost = max（rightMost， nums[i] + i）
在遍历的过程中注意当rightMost < i时，返回false
bool canJump0(vector<int>& nums)
{
int size = nums.size();
int rightMost = 0;
for (int i = 0; i < size; i++)
{
if (rightMost < i)return false;
rightMost = max(rightMost, i + nums[i]);
if (rightMost >= size - 1)return true;
}
return false;
}时间复杂度：O（n）
空间复杂度：O（1）
24.1、动态规划
对于序列【2，3，1，1，4】
f（x）表示从下标x处，还能向右走几步
例如f（2） = 3，代表在下标为2的地方，还能向右走3步（小于0，则说明走不到这里）
状态转移公式f（x） = max【f（x - 1）- 1，nums[i]】
道理是这个道理，但是专门为了这个建一个数组来记录状态太亏了，所以用一个maxStep来代表f（x）
现在只需要维护maxStep即可
maxStep = max【maxStep ，nums[i]】 - 1
bool canJump1(vector<int>& nums)
{
int maxStep = 0; //维护在该位置上最多能走几步
for (size_t i = 0; i < nums.size(); i++)
{
if (maxStep < 0)return false;
maxStep = max(maxStep, nums[i]) - 1;
}
return true;
}时间复杂度：O（n）
空间复杂度：O（1）
在性能方面，两种基本差不多，只是下面这种代码比较简洁（就简洁了一行。。。）