网站定位分析,网店运营与管理,余姚网站推广,wordpress 跳转适配关卡名 理解与贪心有关的高频问题 我会了✔️ 内容 1.理解跳跃游戏问题如何判断是否能到达终点 ✔️ 2.如果能到终点#xff0c;如何确定最少跳跃次数 ✔️
1. 跳跃游戏
leetCode 55 给定一个非负整数数组#xff0c;你最初位于数组的第一个位置。数组中的每个元素代表… 关卡名 理解与贪心有关的高频问题 我会了✔️ 内容 1.理解跳跃游戏问题如何判断是否能到达终点 ✔️ 2.如果能到终点如何确定最少跳跃次数 ✔️
1. 跳跃游戏
leetCode 55 给定一个非负整数数组你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度判断你是否能够到达最后一个位置。 示例1 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例2 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 所以你永远不可能到达最后一个位置。 如果当前位置元素如果是3我究竟是跳几步呢一步两步还是三步这里的关键是判断能否到达终点不用每一步跳跃到哪个位置而是尽可能的跳跃到最远的位置看最多能覆盖到哪里只要不断更新能覆盖的距离最后能覆盖到末尾就行了。 例如上面的第一个例子3能覆盖的范围是后面的{2,1,0}2接下来能覆盖后面的{1,0},而1只能覆盖到{0}所以无法到达4。 而第二组序列2能覆盖{3,1}3可以覆盖后面的{1,1,4},已经找到一条路了。1只能到下一个1下一个1能到4所以这里有{2,1,1,4}和{2,3,1,1,4}两种走法加起来有3种跳法。 我们可以定义一个cover表示最远能够到达的方位也就是i每次移动只能在其cover的范围内移动每移动一次cover得到该元素数值新的覆盖范围的补充让i继续移动下去。而cover每次按照下面的结果判断。如果cover大于等于了终点下标直接return true就可以了 cover max(该元素数值补充后的范围, cover本身范围) 针对上图的两个序列再解释一下 1.在第二个图中第一个元素nums[0]2此时conver2能覆盖到{3,1}两个元素。 2.继续第二个元素nums[1]3此时能继续覆盖的范围就是13能覆盖{114}三个位置。此时cover2而”该元素数值补充后的范围“是134所以新的convermax{4,2}此时就是covernums.length-1。 其他情况都可以使用类似的方式来判断 所以代码就是
public boolean canJump(int[] nums) {if (nums.length 1) {return true;}//覆盖范围, 初始覆盖范围应该是0因为下面的迭代是从下标0开始的int cover 0;//在覆盖范围内更新最大的覆盖范围for (int i 0; i cover; i) {cover Math.max(cover, i nums[i]);if (cover nums.length - 1) {return true;}}return false;
}
这道题目的难点是要想到覆盖范围而不用拘泥于每次究竟跳几步覆盖范围是可以逐步扩展的只有能覆盖就一定是可以跳过来的不用管是怎么跳的。
2 最短跳跃游戏
在上题再进一步假设一定能到达末尾然后让你求最少到达的步数该怎么办呢这就是LeetCode45上面的例子。可以看到有三种走法{2,3,4}、{2,1,1,4}和{2,3,1,1,4}那这时候该怎么办呢 具体该怎么实现呢网上有很多解释代码也基本雷同而且也很明显是将上一题的代码修改了一下但是难在不好理解我现在给一个比较好理解的方式贪心双指针。 我们重新观察一下结构图为了便于分析我们修改一下元素序列我们需要四个变量
left用来一步步遍历数组steps用来记录到达当前位置的最少步数right表示当前步数下能够覆盖到的最大范围我们还需要一个临时变量conver假如left到达right时才更新right
在这个图中开始的元素是 2如果只走一步step1可跳的范围是{3,1}。也就是如果只走一步最远只能到达1此时convernums[0]2因此我们用rightnums[2]来保存这个位置这表示的就是走一步最远只能到nums[2]。 接下来我们必须再走一步step2如下图此时可选元素是{3,1} 3能让我们到达的距离是leftnums[left]134而1能让我们到达的位置是leftnums[left]213而所以我们获得最远覆盖距离conver4 。
然后用left和right将step2的范围标记一下 此时还没有到终点我们要继续走在这里我们可选择的元素是{2,4}如果选择2则可以到达leftnums[left]325,如果选择4则是leftnums[left]448已经超越边界了所以此时一定将末尾覆盖了。 这样我们就知道最少需要走3次。 这个过程怎么用代码表示呢看代码
public int jump(int[] nums) {int right 0;int maxPosition 0;int steps 0;for(int left0;inums.length;left){//找能跳的最远的maxPosition Math.max(maxPosition,nums[left]left);if(leftright){ //遇到边界就更新边界并且步数加一right maxPosition;steps;}//right指针到达末尾了。if (right nums.length - 1) {return steps;}}return steps;
}
