55跳跃游戏

题目

给定一个非负整数数组 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<int>& nums) {
        int reach=0;//记录当前能到达的最远处
        //i遍历数组，i要始终处于能到达的位置，如果reach已经大于nums边界已经可以退出循环
        for(int i=0;i<=reach&&reach<nums.size();i++)
        {
            reach=max(reach,i+nums[i]);//当前位置的最远边界为当前位置能加最大步数和最远边界，二者取较大
        }
        return reach+1>=nums.size();//边界是数组下标，从0开始，所以要加1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

• 时间复杂度O(n)

• 空间复杂度O(1)

• 思路

  • 对于数组中的任意一个位置y，只要当前位置x加上x处可走的最大步数，二者之和大于y，则可以到达y
  • 一次遍历数组，维护当前的最远边界
  • 最后比较最远边界是否可以到达数组大小，如果是则返回true

• 法二：逆向遍历数组，从末尾看能不能下降到0

class Solution {
public:
    bool canJump(vector<int>& 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 法三：动态规划

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> f(nums.size(),0);
        f[0]=nums[0]-1;//初始位置可以到达的最远距离就是0加上当前可以走的步数
        //依次确定经过每一个位置的最远距离
        for(int i=1;i<nums.size();i++)
        {
            f[i]=max(f[i-1],i+nums[i-1]);
            if(f[i]==i) return false;//表示不能往后走了，返回false
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度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