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

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]Output: falseExplanation: 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.

Constraints:

• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i][j] <= 10^5

题意：给出一个非负整数数组，最开始处于数组第一个位置，数组元素表示在该位置可以跳跃的最大长度。判断是否能够到达最后一个位置。

解法 从后往前

从后往前扫描数组，如果遇到零（表示到达这个位置后，无法跳跃），就继续往前查看数组，看是否存在某个位置可以跳过这个零，不存在这样的位置就返回 false ；存在则继续这一过程。显然，如果不存在零元素，就必然能够到达最后一个位置。

具体代码实现如下：

class Solution {
   public:    bool canJump(vector
   
    & nums) {
           if (nums.size() <= 1) return true;        for (int i = nums.size() - 2; i >= 0; --i) {
               if (nums[i] != 0) continue;             bool canJumpOverZero = false;            for (int j = i - 1; j >= 0; --j) {
                   if (j + nums[j] > i) {
                         canJumpOverZero = true;                    i = j; //不再扫描中间这一段                    break;                }            }            if (canJumpOverZero == false) return false;        }        return true; //全都不为0;或者有零但是可以越过-->可以到达;    }};
   

效率如下：

执行用时：24 ms, 在所有 C++ 提交中击败了65.15% 的用户内存消耗：13 MB, 在所有 C++ 提交中击败了8.43% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/109228008 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！