本文共 1528 字，大约阅读时间需要 5 分钟。

解法 1

从左到右遍历数组，假设当 index = x1 时，nums[x1] = 0，则继续向右遍历，直接遇到不为 0 的元素，假设此时 index = x2。

且在遍历的时候，记录 index 在 x1 之前的元素，有 maxIndex = index+nums[index]（maxIndex 表示下标为 index 对应的元素值所能跨到最远位置）。

如果 maxIndex < x2，则表示从 x1 之前的任一元素位置跳跃，都无法跨过 x2 位置时的 0，因此返回 false。

但是要记住一种特殊情况，假设 maxIndex >= nums.length - 1，则表示已经跳跃到末尾了，此时可以直接返回 true。

public boolean canJump(int[] nums) {
       if (nums == null || nums.length == 0) {
           return false;    }    int len = nums.length;    // 注意 nums[0] 为 0 的特殊情况    if (nums[0] == 0) {
           return len == 1;    }        int index = 0;    int lastMax = 0;    while (index < len) {
           if (nums[index] == 0) {
               ++index;            // 防止越界            while (index < len && nums[index] == 0) {
                   ++index;            }            if (lastMax < index) {
                   return false;            }        } else {
               if (index + nums[index] > lastMax) {
                   lastMax = index + nums[index];                if (lastMax >= len - 1) {
                       return true;                }            }            ++index;        }    }    return true;}

解法 2

引用自该题目前为止通过的最快解法。

从右到左返回来遍历。

如果有 index = y1，假定 y1 对应的位置能够跳跃到末尾，则只要在 index < y1 的元素中，找到能够跳跃到 y1 位置，或者超越 y1 位置的元素即可。

如果最后能够逆着来到起始位置，则表示成立。

public boolean canJump(int[] nums) {
       int leftGood = nums.length - 1;    for (int i = nums.length - 2; i >= 0; i--) {
           if (i + nums[i] >= leftGood) {
               leftGood = i;        }    }    return leftGood == 0;}

上述即贪心算法的实现，具体可以参考 。

转载地址：http://wrerj.baihongyu.com/