Leetcode 55 跳跃游戏

题意理解：

? ? ? ? ?非负整数数组?nums,

? ?最初位于数组的?第一个下标?。

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

? ? ? ? 需要跳到nums最后一个元素即为成功。

? ? ? ? 目标：是否能够跳到最后一个元素。

解题思路：

? ? ? ? 使用贪心算法来解题，需要理解局部解和最优解的关系。

? ? ? ? 这里引入一个覆盖区间的概念，覆盖区间表示所有可达的位置。

? ? ? ? 覆盖区间覆盖到最后一个元素时，即为最后一个位置可达。

????????

? ? ? ? 局部最最优解：当前位置尽可能到达足够远的位置，逐步探索可到达的最远位置能否覆盖到最后一个元素。

????????

结束的位置是能探索到的最远位置。

例1：最开始的最远距离是nums[2], 在[0,2]之间探索，最远到达nums[4],即能到达最远的位置。

1.贪心解题

我们用一个cover表示最远可到达的位置。cover随着探索会不断往后移，直到最远可达位置。

注意： i+nums[i]表达当前可达的最远位置的下标。

public boolean canJump(int[] nums) {
        if(nums.length==1) return true;//一个位置一定可达
        int cover=0;
        for(int i=0;i<=cover;i++){
            //i+nums[i]表示当前位置可达的最远距离的坐标
            cover=Math.max(cover,i+nums[i]);
            //最后一个位置是否可达
            if(cover>=nums.length-1) return true;
        }
        return false;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(n)

n表示输入数组的长度。