龙川网站建设,灵宝seo公司,建站工具介绍,想做视频06贪心#xff1a;跳跃游戏
55. 跳跃游戏
刚看到本题一开始可能想#xff1a;当前位置元素如果是 3#xff0c;我究竟是跳一步呢#xff0c;还是两步呢#xff0c;还是三步呢#xff0c;究竟跳几步才是最优呢#xff1f;
其实跳几步无所谓#xff0c;关键在于可跳的…06贪心跳跃游戏
55. 跳跃游戏
刚看到本题一开始可能想当前位置元素如果是 3我究竟是跳一步呢还是两步呢还是三步呢究竟跳几步才是最优呢
其实跳几步无所谓关键在于可跳的覆盖范围
不一定非要明确一次究竟跳几步每次取最大的跳跃步数这个就是可以跳跃的覆盖范围。
这个范围内别管是怎么跳的反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点
每次移动取最大跳跃步数得到最大的覆盖范围每移动一个单位就更新最大覆盖范围。
贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。
局部最优推出全局最优找不出反例试试贪心
i 每次移动只能在 cover 的范围内移动每移动一个元素cover 得到该元素数值新的覆盖范围的补充让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标直接 return true 就可以了。
class Solution {public boolean canJump(int[] nums) {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;}
}总结
这道题目关键点在于不用拘泥于每次究竟跳几步而是看覆盖范围覆盖范围内一定是可以跳过来的不用管是怎么跳的。
可以看出思路想出来了代码还是非常简单的。
感觉贪心系列题目和题目之间貌似没有什么联系
是真的就是没什么联系因为贪心无套路没有个整体的贪心框架解决一系列问题只能是接触各种类型的题目锻炼自己的贪心思维
