【LeetCode刷题笔记】55.跳跃游戏

• 题目：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

  数组中的每个元素代表你在该位置可以跳跃的最大长度。

  判断你是否能够到达最后一个下标。

示例：输入：nums = [2,3,1,1,4]

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

• 贪心算法

  我们想要知道能否从数组第一个位置开始跳跃到最后的位置上，那么我们采取一种贪心的思想，依次遍历数组，并且保存数组上每个元素上所能到达的最大值。比如数组nums[0]=2，那么0位置上最远可以跳到数组下标为2的位置上，我们保存当前最远距离为2。接着看nums[1]=2，那么此时最远可以跳到1+nums[1]=3，最大距离为3。依次遍历知道最大距离超过了数组长度，那么就跳到了最后一个位置。中间可能会发生无法到达的情况，即nums[i]的i下标超过了最大距离，也就是说当前数组下标是之前任何一个位置上都无法达到的，那么就直接返回false。

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

• 上面的方法实际借助了BFS的思想，下面将一种BFS的解法作为参考

public boolean canJump(int[] nums){
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[nums.length];
//        从下标0处开始
        queue.offer(0);
//        队列保存的是能到达的数组下标
        while (!queue.isEmpty()){
            int index = queue.poll();
//            数组下标大于等于数组长度-1返回true
            if (index >= nums.length - 1)
                return true;
//            把当前位置上能到达的所有数组下标全部加入队列中
            for (int i = index + 1; i < nums.length && i <= index + nums[index]; i++){
//                要检查当前下标是否被访问过了，防止额外的时间开销
                if (!visited[i]){
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
        return false;
    }