【C++】算法集锦(14):贪心算法
发布日期:2021-06-30 19:47:36
浏览次数:2
分类:技术文章
本文共 1820 字,大约阅读时间需要 6 分钟。
文章目录
贪心算法
贪心算法可以理解为一种特殊的动态规划为题,拥有一些更加特殊的性质,可以进一步降低动态规划算法的时间复杂度。
来看几道题目熟悉一下这种“不断寻求局部最优”的算法。
跳跃游戏 I
输入一个非负整数数组nums,数组元素nums[i]表示的是:如果你站在位置 i ,最多能够往前跳几步。
现在你站在第一个位置nums[0],试问你能否跳到数组的最后一个位置?例:[1,2,3,4,5],可以
[1,2,0,0,4],不行思路分析
这题相对比较简单一些吧,当然不要去用回溯,用回溯的话时间复杂度太高。
成功的方式太多了,但是失败的方式只有一个:有足够多的0横亘在其中,导致不论怎么努力就是跳不过去。我们哪几个栗子来试一下吧:
[0,····] //点点点的意思是随便你填什么数字都无所谓了[1,2,1,0,···][2,0,0,···]//还有啥特例吗?
我们来分析一下上面的栗子(我们假设数组有-1格,nums[-1] = 1,我们从nums[-1]开始):
第一个栗子:在下标为0的时候遇到了绝望的0,从下标为-1的地方为此前能前进的最大步数1,无法跨越,终结。 第二个栗子:在下标为3的时候遇到了绝望的0,从下标为1的地方获得了此前能前进的最大步数2,无法跨越,失败。 第三个栗子:在下标为2的时候遇到了绝望的0,从下标为0的地方获得了此前能前进的最大步数2,无法跨越,失败。这三个栗子中,我们能提取出什么有效的信息?
0 -(-1) = 13 - 1 = 22 - 0 = 2
对吧。
还有呢?为什么不变通一下,比如说例2中,不通过下标为2的点去中转呢?因为中转也无效啊。那就是说我们要去尝试着中转。
这样讲可能会有点绕啊,我把例2改一下:[1,2,2,0],这不就活了吗!
拿两个例2来比对一下:
(以flag纪录当前能够到达的最远距离)[1,2,1,0,···] //下标0最多到下标1,flag = 1;下标1最多到下标3,flag = 3;下标2最多到下标3,flag = 3;下标3,flag = 3;卒[1,2,2,0] //下标0:flag = 1;下标1:flag = 3;下标2:flag = 4
可以看到,当flag == 下标 的时候,就凉凉了。
代码实现
所以,我们写出代码:
bool canJump(vector & nums){ int n = nums.size(); int farthest = 0; for(int i = 0; i < n-1; i++){ //不断计算能够跳到的最远距离 farthest = max(farthest,i+nums[i]); //如果碰到0跳不动了 if(farthest <= i) return false; } return farthest >= n-1;}
跳跃游戏 II
跟上面差不多,但是这次保证你能跳到最后,问你最少跳几次。
看着好眼熟啊,好像前面写过一道这样的题。换硬币是吧。
去递归选取后续跳法里面的最优,属于一种:从后向前的解法,可以理解为从底层开始层序遍历一棵树。只不过我们后来通过备忘录对这棵树进行了剪枝,不然真的不忍直视啊。
但是呢,我们今天讲的是贪心算法,它可以想象成从上往下一条路走下去。让我们看看:
思路
贪心算法是什么?贪心算法会选择当下最有潜力的一步。
举个例子:[2,3,1,2,5,1] 当你现在在下标0的位置,你可以跳两步。动归的话会递归去算这两步到最终结果的最优步数,但是贪心算法不这样。 贪心算法是每次尽可能多跳吗?NoNoNo,选择当下最有潜力的:在坐标1的位置,你有三个选择;在坐标2的位置,你只有一个选择,所以贪心算法会让你选择跳到坐标1。这就是贪心算法的局部最优(不要奇思妙想啥反例,要用贪心算法,就要承担它的失误率)。接下来,我们来写代码:
int jump(vector & nums){ int n = nums.size(); //站在索引i,最多能跳到索引end int end = 0; //从索引【i···end】起跳,最远能到的距离 int farthest = 0; //纪录跳跃次数 int jumps = 0; for(int i = 0; i
右手中指都麻了。。
歇了歇了。转载地址:https://lion-wu.blog.csdn.net/article/details/114147353 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月11日 10时41分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Ubuntu 安装 NTP 服务
2019-04-30
NeoFetch - Linux 使用命令行查看系统信息
2019-04-30
Jenkins 控制台输出中的奇怪字符
2019-04-30
Linux添加系统调用
2019-04-30
ubuntu 18 CTF 环境搭建
2019-04-30
linux内存的寻址方式
2019-04-30
[off by null + tcache dup]lctf_easy_heap
2019-04-30
[pie+libc]national2021_pwny
2019-04-30
task_struct 结构分析
2019-04-30
Linux创建进程的源码分析
2019-04-30
ubunut16.04的pip3出现问题,重新安装pip3
2019-04-30
how2heap-double free
2019-04-30
how2heap-fastbin_dup_consolidate
2019-04-30
orw_shellcode_模板
2019-04-30
[fmt+shellcode]string
2019-04-30
fmt在bss段(neepusec_easy_format)
2019-04-30
[double free] 9447 CTF : Search Engine
2019-04-30
python 函数式编程
2019-04-30