当前位置:首页 > 天道酬勤 > 正文内容

小游戏(贪心算法最短路径问题)

张世龙2021年12月20日 04:13天道酬勤1080

在github:https://github.com/young yangyang 04/leet代码- master中总结了有关算法学习的资料。 其中还有leet代码刷题攻略、各类型经典刷题顺序、思维导图。 如果对你有用的话一定会得到

55. 跳跃游戏

主题链接: https://leet代码- CN.com /问题/跳转- Game /

给定一个非负整数数组,你将首先位于数组的第一个位置。

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

判断是否能到达最后的位置。

例1:输入:3、1、1、4]输出: true说明:从位置0到达位置1,可以从位置1跳跃3步到达最后的位置。

示例2:输入:2、1、0、4]无论输出:假解释为什么,索引都将到达3的位置。 但是,由于这个位置的最大跳跃长度为0,所以无法到达最后的位置。

思路

刚看正题一开始可能觉得,如果现在位置的因素是3,我是跳一步,还是跳两步,跳三步,到底跳几步最好?

其实跳几步都没关系。 重要的是能跳的范围!

没有必要明确一次跳几步。 如果每次都取最大的跳跃步数,这就是可以跳跃的范围。

在这个范围内,不要在意是怎么跳的。 总之一定能跳过。

“那么,这个问题将转换为跳跃覆盖范围能否覆盖到终点! “”

每次移动最大跳跃步数(得到最大复盖范围)、每移动1个单位更新最大复盖范围。

“贪婪算法的局部最优解:每次最大跳跃步数(取最大覆盖范围)、整体最优解)最后得到整体最大覆盖范围,看能否进球”。

局部最优打出全局最优,找不到反例,试试贪婪吧!

图:

55 .跳跃游戏

每次I移动时只能在防护罩范围内移动。 每次移动一个要素时,cover都会补充该要素的数值(新的复盖范围),继续移动I。

另一方面,cover每次只取max (该元素的数值被补充的范围,cover自身的范围)。

如果cover在终点的后缀以上,则直接返回就可以了。

c代码如下所示。

类解决方案{2}

公共:

布尔坎Jump (向量序数) {

intcover=0;

if (数字大小(==1)返回真; //只有一个要素可以达成

for (英制=0; I=复盖; I )//注意这里是cover以下

复盖=最大(inums,复盖;

if (盖子=nums.size (-1 )返回真; //说明可以覆盖到终点

}

返回假;

}

(;

总结

这个主题的重点是,不管每次跳多少步,都要看涵盖范围。 复盖范围内已经可以跳过。 怎么跳都没关系。

我知道你有了一个想法,但是代码很简单。

有些同学在我讲贪婪系列的时候,可能觉得主题和主题之间没有任何联系?

真的没有任何联系。 因为贪得无厌。 没有整体的贪婪框架,解决一些问题的只有接触不同类型的主题来锻炼自己的贪婪思维!

小朋友,《代码随想录》推荐给身边的朋友和同学!

如果朋友一开始就打算打卡,可以在“算法总结”中找到历史文章。 很多朋友从一开始就剪卡。 你不是一个人。

我是程序员Carl,个人主页: https://Github.com/young yangyang 04

详情请点击下面。

扫描二维码推送至手机访问。

版权声明:本文由花开半夏のブログ发布,如需转载请注明出处。

本文链接:https://www.zhangshilong.cn/work/25372.html

标签: 贪心算法
分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。