55. 跳跃游戏

佚名 6年前 (2019-05-16) 随笔 1521人围观抢沙发百度已收录

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路1：最死板的动态规划。从后往前记录从位置i开始能否到达最后一个位置。每次判断要基于之前的记录结果遍历1~nums[i]。

其实这里说的最大长度，就隐隐透露了这道题肯定有更好更玄的解法....

思路2：还是从后往前，如果从位置i能到达最后一个位置，就记录n=1，否则n+1。这里n=1可以理解为中间没有元素为0，一定可以到达；如果中间有1个0，就至少前面某个位置的数足够大来跳过这个0，即至少需要值为n来跳过0。

所以整个的逻辑就是，令n=1，如果nums[i]>=n，令n=1，否则n+1。遍历结束后看n是否为1，如果不为1，而已经是位置0，中间的0没法跳过，就到不了了。

思路3：从前往后。记录从位置i最远能到达的地方d。位置i+1最远能到达的地方=max(d, i+1 + nums[i+1])，进行这一步的前提是从i能到i+1.

总的来说从后往前比较容易想，但是不容易做好，思路2还是不好想明白。但从前往后的思路一旦想到了，就很简单了。

class Solution {
public:
    bool canJump3(vector<int>& nums) {
        if(nums.empty()) return false;
        int n = nums.size();
        vector<int> vis(n,0);
        
        vis[n-1] = 1;
        for(int i = n - 2;i>=0;--i){
            if(nums[i] == 0) continue;
            
            int j1 = i + 1;
            int j2 = i + nums[i];
            if(j2 >= n){
                vis[i] = 1;continue;
            }
            while(j1<=j2 && !vis[j1]){
                ++j1;
            }
            if(j1<=j2 && vis[j1]) vis[i] = 1;
        }
        
        return vis[0];
    }
    bool canJump2(vector<int>& nums) {
        if(nums.empty()) return false;
        
        int n = 1;
        for(int i = nums.size() - 2;i>=0;--i){
            if(nums[i] >= n) n = 1;
            else ++n;
        }
        
        return n==1;
    }
    
    bool canJump(vector<int>& nums) {
        if(nums.empty()) return false;
        
        int d = 0;
        for(int i = 0;i<nums.size() - 1 && d>=i;++i){
            d = max(d,i + nums[i]);
        }
        return d >= nums.size() - 1;
    }
};