题目描述（中等难度）

55. Jump Game - 图1

45题的时候已经见过这道题了，只不过之前是返回从第 0 个位置能跳到最后一个位置的最小步数，这道题是返回是否能跳过去。

leetCode Solution 中给出的是动态规划的解法，进行了一步一步的优化，但都也比较慢。不过，思路还是值得参考的，上边说的比较详细，这里就不啰嗦了。这里，由于受到 45 题的影响，自己对 45 题的解法改写了一下，从而解决了这个问题。

下边的解法都是基于45题 的想法，大家可以先过去看一下，懂了之后再回到下边来看。

解法一 顺藤摸瓜

45 题的代码。

  1. public int jump(int[] nums) {
  2.     int end = 0;
  3.     int maxPosition = 0; 
  4.     int steps = 0;
  5.     for(int i = 0; i < nums.length - 1; i++){
  6.         //找能跳的最远的
  7.         maxPosition = Math.max(maxPosition, nums[i] + i); 
  8.         if( i == end){ //遇到边界，就更新边界，并且步数加一
  9.             end = maxPosition;
  10.             steps++;
  11.         }
  12.     }
  13.     return steps;
  14. }

这里的话，我们完全可以把 step 去掉，并且考虑下当前更新的 i 是不是已经超过了边界。

  1. public boolean canJump(int[] nums) { 
  2.     int end = 0;
  3.     int maxPosition = 0;  
  4.     for(int i = 0; i < nums.length - 1; i++){
  5.         //当前更新超过了边界，那么意味着出现了 0 ，直接返回 false
  6.         if(end < i){
  7.             return false;
  8.         }
  9.         //找能跳的最远的 
  10.         maxPosition = Math.max(maxPosition, nums[i] + i); 
  12.         if( i == end){ //遇到边界，就更新边界，并且步数加一
  13.             end = maxPosition; 
  14.         }
  15.     }
  16.     //最远的距离是否到答末尾
  17.     return maxPosition>=nums.length-1;
  18. }

时间复杂度：O（n）。

空间复杂度：O（1）。

解法二 顺瓜摸藤

每次找最左边的能跳到当前位置的下标，之前的代码如下。

  1. public int jump(int[] nums) {
  2.     int position = nums.length - 1; //要找的位置
  3.     int steps = 0;
  4.     while (position != 0) { //是否到了第 0 个位置
  5.         for (int i = 0; i < position; i++) {
  6.             if (nums[i] >= position - i) {
  7.                 position = i; //更新要找的位置
  8.                 steps++;
  9.                 break;
  10.             }
  11.         }
  12.     }
  13.     return steps;
  14. }

这里修改的话，只需要判断最后回没回到 0 ，并且如果 while 里的 for 循环没有进入 if ，就意味着一个位置都没找到，就要返回 false。

  1. public boolean canJump(int[] nums) { 
  2.     int position = nums.length - 1; //要找的位置
  3.     boolean isUpdate = false; 
  4.     while (position != 0) { //是否到了第 0 个位置
  5.         isUpdate = false;
  6.         for (int i = 0; i < position; i++) {
  7.             if (nums[i] >= position - i) {
  8.                 position = i; //更新要找的位置 
  9.                 isUpdate = true;
  10.                 break;
  11.             }
  12.         }
  13.         //如果没有进入 for 循环中的 if 语句，就返回 false
  14.         if(!isUpdate){
  15.             return false;
  16.         }
  17.     }
  18.     return true;
  19. }

时间复杂度：O（n²）。

空间复杂度：O（1）。

解法三

让我们直击问题的本质，与 45 题不同，我们并不需要知道最小的步数，所以我们对跳的过程并不感兴趣。并且如果数组里边没有 0，那么无论怎么跳，一定可以从第 0 个跳到最后一个位置。

所以我们只需要看 0 的位置，如果有 0 的话，我们只需要看 0 前边的位置，能不能跳过当前的 0 ，如果 0 前边的位置都不能跳过当前 0，那么直接返回 false。如果能的话，就看后边的 0 的情况。

  1. public boolean canJump(int[] nums) {
  2.     for (int i = 0; i < nums.length - 1; i++) {
  3.         //找到 0 的位置
  4.         if (nums[i] == 0) {
  5.             int j = i - 1;
  6.             boolean isCanSkipZero = false;
  7.             while (j >= 0) {
  8.                 //判断 0 前边的元素能否跳过 0 
  9.                 if (j + nums[j] > i) {
  10.                     isCanSkipZero = true;
  11.                     break;
  12.                 }
  13.                 j--;
  14.             }
  15.             if (!isCanSkipZero) {
  16.                 return false;
  17.             }
  18.         }
  19.     }
  20.     return true;
  21. }

但这样时间复杂度没有提高， 在 @Zhengwen 的提醒下，可以用下边的方法。

我们判断 0 前边的元素能否跳过 0 ，不需要每次都向前查找，我们只需要用一个变量保存当前能跳的最远的距离，然后判断最远距离和当前 0 的位置就可以了。

  1. public boolean canJump(int[] nums) {
  2.     int max = 0;
  3.     for (int i = 0; i < nums.length - 1; i++) {
  4.         if (nums[i] == 0 && i >= max) {
  5.             return false;
  6.         }
  7.         max = Math.max(max, nums[i] + i);
  8.     }
  9.     return true;
  10. }

时间复杂度：O（n）。

空间复杂度：O（1）。

参考这里，我们甚至不需要考虑 0 的位置，只需要判断最大距离有没有超过当前的 i 。

  1. public boolean canJump(int[] nums) {
  2.     int max = 0; 
  3.     for (int i = 0; i < nums.length; i++) {
  4.         if (i > max) {
  5.             return false;
  6.         }
  7.         max = Math.max(max, nums[i] + i);
  8.     }
  9.     return true;
  10. }

总

当自己按照 45 题的思路写完的时候，看 Solution 的时候都懵逼了，这道题竟然这么复杂？不过 Solution 把问题抽象成动态规划的思想，以及优化的过程还是非常值得学习的。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情