中国建设银行洛阳分行网站,自媒体账号申请,快递网站建设,做网站 广州题意理解#xff1a; 非负整数数组 nums, 最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 需要跳到nums最后一个元素即为成功。 目标#xff1a;是否能够跳到最后一个元素。 解题思路#xff1a; 使用贪心算法来解题#xff0c;需要理解… 题意理解 非负整数数组 nums, 最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 需要跳到nums最后一个元素即为成功。 目标是否能够跳到最后一个元素。 解题思路 使用贪心算法来解题需要理解局部解和最优解的关系。 这里引入一个覆盖区间的概念覆盖区间表示所有可达的位置。 覆盖区间覆盖到最后一个元素时即为最后一个位置可达。 局部最最优解当前位置尽可能到达足够远的位置逐步探索可到达的最远位置能否覆盖到最后一个元素。 结束的位置是能探索到的最远位置。 例1最开始的最远距离是nums[2], 在[0,2]之间探索最远到达nums[4],即能到达最远的位置。 1.贪心解题
我们用一个cover表示最远可到达的位置。cover随着探索会不断往后移直到最远可达位置。
注意 inums[i]表达当前可达的最远位置的下标。
public boolean canJump(int[] nums) {if(nums.length1) return true;//一个位置一定可达int cover0;for(int i0;icover;i){//inums[i]表示当前位置可达的最远距离的坐标coverMath.max(cover,inums[i]);//最后一个位置是否可达if(covernums.length-1) return true;}return false;}
2.分析 时间复杂度O(n) 空间复杂度O(n) n表示输入数组的长度。
