跳跃游戏（Java）

跳跃游戏（Java） leetCode第55题：

力扣

---

题解思路（一）

题目描述的是能不能到达最后一个位置，中间跳几步，跳多少次其实不重要，可能很容易陷入到我接下来要跳多少步的误区，只要能达到目的就好。当前位置的元素就代表了你最大能一次跳多远，其中比较特殊的是0，如果你站在了0位置上，那么就不能动了，所以我们要尽可能避开0，只要能够把每个0都跳过去，那么我们肯定能到达最后一个位置，所以这样想，遍历找到第一个0位置，然后从数组头看看每个之前的数最大值能不能跳过这个0，如果能跳过，那么我们再找下一个0，再看能不能跳过去，如果其中有一个0位置，他之前的元素中每个的最大值都不能越过这个0，那么说明这个0是不可越过的，即不可能到达最后一个位置。按这种思路去解的话，时间复杂度最好为o（n）,而最差情况跟0个数以及数据元素分布有关，会大于o（n）。可以看看思路二，是参考的别人的（程序员carl），是比较精妙的另一种思路。而且最差情况下的时间复杂度也仅为o(n)。

代码实现：

class Solution {
    public boolean canJump(int[] nums) {
        int location = 0;
        int check = 0;
        boolean flag = true;
        while(location < nums.length - 1){
            while(location < nums.length - 1 && nums[location] != 0)  location++;
            if(location == nums.length - 1) return true;
            for(int i = 0; i <= location; i++){
                if(nums[i] > location - i )  break;
                if(i == location)   return false;
            }
            location++;
        }
        return true;
    }
}

---

解题思路（二）

用跳跃覆盖范围去求解，设一个数组[1,4,2,1,0,2]，每一步规定好了你最大能跨多远，我们把每个位置跨的范围结合起来，看图：

 

例子中可以看出，每个位置下最大跳跃范围能够全覆盖整个数组的话，是能够到达最后的位置的（中间通过调整跳跃长度，肯定能到达终点），那么在这样的思路下，我们取一个变量cover，记录当前可覆盖的最大范围，一个迭代变量location迭代数组不断更新最大覆盖范围，这里就有几种情况，如果迭代变量location超过了cover的覆盖范围，说明当前记录下，以及无法得出更大范围，此时已经不可能再到达最终位置，如果cover大于了数组长度，说明覆盖范围完全可以超过数组，那么肯定可以到达最终位置。

代码实现：

class Solution {
    public boolean canJump(int[] nums) {
        int location = 0;
        int cover = 0;
        if(nums.length <= 1) return true;
        for(;location < nums.length - 1; location++){
            cover = Math.max(nums[location] + location, cover);
            if(location >= cover) return false;
            if(cover >= nums.length - 1) return true;
        }
        return false;
    }
}

---

思路二参考了 程序员carl 的代码随想录，很厉害一老哥。