【leetcode】55 Jump Game

发表于 | 分类于 ，


描述

给定一个非负整数数组，您最初定位在数组的第一个索引处。

数组中的每个元素表示该位置的最大跳转长度。

确定您是否能够到达最后一个索引。

样例

样例1

1
2
3
输入: [2,3,1,1,4]
输出: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

样例2

1
2
3
4
输入: [3,2,1,0,4]
输出:  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.

思路

  • 动态规划，dp[i] = 2 表示当前在索引下标为 i 的石头上，并且还可以移动 2 步
  • 求能移动到最大的距离，如果这个地方 nums[maxPos] == 0 表示不能到达最后一个石头
  • 回溯，比较慢

代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i - 1], nums[i - 1]) - 1;
            if(dp[i]<0){
                return false;
            }
        }
        return true;
    }
};

找最远的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxPos = 0;
        for(int i=0;i<nums.size();i++){
            maxPos = std::max(maxPos,nums[i]+i);
            if(nums[maxPos] == 0 && i>=maxPos && i !=nums.size()-1){
                return false;
            }
        }
        return maxPos >= nums.size() -1;
    }
};

下面这个是上面想法的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxPos = 0;
        for(int i=0;i<nums.size();i++){
            maxPos = std::max(maxPos,nums[i]+i);
            if(maxPos >= nums.size()-1){
                return true;
            }
        }
        return false;
    }
};

参考

原题链接