题目主要信息

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则返回true，否则返回false。

方法一：BFS

具体方法

本方法会超时，但当数据量小的时候也是一种思路。

将每一个位置$ii$存入队列中，依次遍历从$0num[i]0~num[i]$的可以跳跃的最远距离是否等于数组长度，如果是就返回$truetrue$，如果遍历完都不能跳到，就返回$falsefalse$。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        // write code here
                // 本题只可以向前跳 了，两种特殊情况
        if(nums[0]==0 && 1 == nums.length) 
            return true; 
        if(nums[0]==1 && 1 == nums.length) 
            return true; 
        // 是否已经访问
        boolean []visit = new boolean[nums.length];
        // 队列
        Queue<Integer> queue = new LinkedList<>();
        // 第一个位置入队
        queue.offer(0);
        visit[0] = true;
        while(!queue.isEmpty()){
            // 出队 
            int temp = queue.poll();
            int step = nums[temp];
            for(int i=1;i<=step;i++){
                // 说明找到了，直接返回true 
                if(i+temp == nums.length-1)
                   return true;
                // 判断下一个位置是否超过数组长度或者是否访问过
                if (temp + i < nums.length && visit[temp + i] == false) {
                    visit[temp+i] =true;
                    queue.offer(temp+i);
                }
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，需要两层遍历
• 空间复杂度：$O(n)O(n)$，队列的大小。

方法二：贪心

具体方法

对于数组中的任何一个位置y，如何判断其是否可以达到呢？只要存在一个位置$xx$，从$xx$可以跳到$yy$位置，即满足$x+num[x]>yx+num[x]>y$,那么y就是可以到达的。

因此，可以遍历数组，记录可以跳到的最远位置，如果当前遍历的位置x，如果它在可以达到的位置范围内，那么可以从起点跳若干次到该位置，因此，可以用$x+num[x]x+num[x]$更新可以跳跃的最远位置。如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 $truetrue$作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回$falsefalse$ 作为答案。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        int y = 0;
        for (int x = 0; x < nums.length; x++) {
            //如果当前索引位置大于可以跳跃的最大长度 说明不可能到最后一个位置
            if (x > y) return false;
            // 更新最大可以跳跃位置
            y = Math.max(y, x + nums[x]);
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$,遍历一遍数组。
• 空间复杂度：$O(1)O(1)$，一个记录结果的变量