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

单源最短路径贪心算法(人为什么贪心)

张世龙2021年12月20日 04:14天道酬勤570

相对于贪婪算法:跳跃游戏变得相当难了。 请做好心理准备。

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

45.跳跃游戏II

主题地址: https://发光代码- CN.com /问题/跳转- Game-ii /

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

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

你的目标是以最小的跳跃次数到达数组的最后位置。

例:输入: 2、3、1、1、4]输出: 2说明3360跳到最后位置的最小跳跃数为2。 下标从0跳到下标1的位置,跳一步,跳三步到达数组的最后位置。

说明:假设你总是能到达数组的最后位置。

思路

正题相对于贪婪算法,跳跃游戏相当难。

但是,想法相似。 还是要看最大的涵盖范围。

这个问题必须计算最小手续费,但必须弄清楚什么时候要加手续费。

贪婪的想法,局部最优:现在的可移动距离尽量多走,在还没有到达终点的情况下,再增加一步。 整体最佳:一步一步尽量多走,达到最小步数。

想法是这样的,但是在写代码的时候,不知道实际能跳远到什么程度。 这样的话,我不知道下一步能不能跳到最远。

“所以,实际解决问题时,必须从涵盖范围出发。 无论怎么跳,复盖范围内一定能跳。 用最小的步数增加覆盖范围,覆盖范围覆盖到终点后,得到的就是最小的步数! “”

“这里需要统计两个涵盖范围。 目前,这一步的最大覆盖面和下一步的最大覆盖面”。

如果移动下标达到当前舞步的最大覆盖最远距离,但还没有到达终点,则必须再进一步增加覆盖范围,直到覆盖范围覆盖到终点。

图:

45 .跳跃游戏II

“图的涵盖范围的意思是,如果是红色区域,最多2步一定能去! “具体怎么不跳,反正一定能跳。”

方法一

图中可以看出,移动下标到达当前封面最远距离下标时,步数加1以增加封面距离。 最后的步数是最低步数。

这里也有需要考虑的特殊情况。 移动下标达到当前盖子的最远距离时

如果当前封面最远距离的下标不是集合的终点,则步数需要加1,继续走下去。 如果当前封面最远距离的下标是集合的终点,则步数不需要加1。 因为不能再往后走了。 c代码如下所示。 (详细评论) ) )。

//版本1

类解决方案{2}

公共:

int jump (向量序数) {

if(nums.size(==1)返回0;

intcurDistance=0; //现在复盖最远距离的下标

intans=0; //记录行走的最大步数

intnextDistance=0; //下一步涵盖最远距离的后缀

for (英制=0; inums.size (; I ) {2}

下一距离=最大(nums I,下一距离); //在下一步中更新涵盖最远距离的下标

if(I==curdistance ) (/遇到当前封面最远距离的下标

红外线距离!=nums.size((-1 ) ) /当前盖板最远距离不是下标到终点时

ans; //需要进入下一步

cur距离=下一距离; //更新当前盖板最远距离下标((就等于加油了) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。

if (下一距离=nums.size (-1 )中断; //下一步的复盖范围到达终点,结束循环

}elsebreak; //当前封面最远距离的后缀是集合的终点,即使不进行ans操作,也将直接结束

}

}

     return ans;     } };

方法二

依然是贪心,思路和方法一差不多,代码可以简洁一些。

「针对于方法一的特殊情况,可以统一处理」,即:移动下标只要遇到当前覆盖最远距离的下标,直接步数加一,不考虑是不是终点的情况。

想要达到这样的效果,只要让移动下标,最大只能移动到nums.size - 2的地方就可以了。

因为当移动下标指向nums.size - 2时:

如果移动下标等于当前覆盖最大距离下标, 需要再走一步(即ans++),因为最后一步一定是可以到的终点。(题目假设总是可以到达数组的最后一个位置),如图:

如果移动下标不等于当前覆盖最大距离下标,说明当前覆盖最远距离就可以直接达到终点了,不需要再走一步。如图:

代码如下:

// 版本二 class Solution { public:     int jump(vector<int>& nums) {         int curDistance = 0;    // 当前覆盖的最远距离下标         int ans = 0;            // 记录走的最大步数          int nextDistance = 0;   // 下一步覆盖的最远距离下标          for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1,这是关键所在             nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标             if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标                 curDistance = nextDistance;         // 更新当前覆盖的最远距离下标                 ans++;             }         }         return ans;     } };

可以看出版本二的代码相对于版本一简化了不少!

其精髓在于控制移动下标i只移动到nums.size() - 2的位置,所以移动下标只要遇到当前覆盖最远距离的下标,直接步数加一,不用考虑别的了。

总结

相信大家可以发现,这道题目相当于贪心算法:跳跃游戏 难了不止一点。

但代码又十分简单,贪心就是这么巧妙。

理解本题的关键在于:「以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖了终点」,这个范围内最小步数一定可以跳到,不用管具体是怎么跳的,不纠结于一步究竟跳一个单位还是两个单位。

就酱,如果感觉「代码随想录」很不错,就分享给身边的朋友同学吧!

打算从头开始打卡的录友,可以在「算法汇总」这里找到历史文章,很多录友都在从头打卡,你并不孤单!

-------end-------

我是程序员Carl,个人主页:https://github.com/youngyangyang04

更多精彩点击下方了解更多!

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

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

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

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

发表评论

访客

看不清,换一张

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