您现在的位置是:首页 >技术交流 >贪心算法讲解网站首页技术交流
贪心算法讲解
文章目录
1. 贪心算法的概念
贪心算法是:用一种局部最功利的标准,总是做出当前看来是最好的选择。如果局部最优解可以得出全局最优解,说明贪心假设成立,否则就失败。
举个例子:
这里有一个矩形,里面放着0和1,我们想从左上角走到右下角,然后从右下角走到左上角,怎么走能取到最多的1。规定:左上->右下(只能往右边和下边走),右下->左上(只能往左边和上边走),走过的1都会变成0。
如果我们的贪心思想是:左上->右下局部最多1,右下->左上局部最多1。先左上->右下:
这里我们取到了最多的1,但是右下->左上走的时候,取左边的1就取不到右边的1,取右边的1就取不到左边的1。
那么我们可以这样去走:
这样才能得出最多的1,所以前面的贪心思想是错误的。
2. 讲解贪心
题目1:给定一个由字符串组成的数组strs,必须把所有的字符串拼接起来,返回所有可能的拼接结果中,拼接结果中最小的是什么?
首先,大家可能想到的方法是:如果前一个字符串比后一个字符串大,前面的就放在后面,后面的就放在前面。
举个例子:
首先可以看到:cks比abc大,所有我们就把abc放前面,cks放后面,就形成了abccks。abccks比ft小,abccks就放在前面,ft就放在后面。就是abccksft。那么这样的一个方法它行不行呢?我们可以找个反例:
b比ba小,那么b就放在前面,ba放在后面。结果就是bba,但是这个字符串不是最小的,bab比bba小。所有这个策略不正确。
正确的策略是:ab<ba,a就放前,否则b就放前。
为什么这个策略是对的,我们就需要去证明:ab<=ba,bc<=cb,那么ac<=ca。如果能证明出这个不等式就说明这个策略是对的,但是证明太复杂了,这里就不证明了。
代码实现:
题目2:一个项目要占用一个会议室宣,会议室不能同时容纳两个项目的宣讲。给你一个项目的开始时间和结束时间,你来安排宣讲的日程,要求会议室进行的宣讲场次最多。
举个例子:
有这么一组数据,如果说,我们按照开始时间最小的来选,那么先选择[1,10],但是如果选择了这个后面三个都不能选了,选择[2,3],[3,5],[6,7]这样选择的场次最多,所以这个贪心思想是错误的。
那么什么方法的贪心思想是正确的呢?
答案是:选择结束时间最早的。
假设有这么一组数据,我们先按照结束时间来排序:
我们从0时刻开始,那么第一个结束时间最早的是[1,2],选择了这个之后,[1,4]就不能选择了,后面的都能选,结束时间最短的是[2,9],选择这个[3,10]就不能选了,只能选[9,12],所以最多结果就是3个。
代码实现:
创建一个类,代表会议的开始时间和结束时间。
这是比较方法,按照会议结束早的往前排。
排完序之后,按照当前时间和会议的开始时间比较,如果小于等于会议的开始时间就说明可以进行宣讲。
题目3:
解决思路是:
1.创建一个小根堆。
这是一组数组,先从小到大排序,然后去构建它的小根堆:
我们每一次弹出两个数,然后把它们两加起来:
加起来之后,放入小根堆里:
再弹出两个数,然后加起来,放入小根堆里面:
再弹出两个数,然后加起来,放入小根堆里面:
重复上面的操作,当小根堆里只有一个数时停止:
我们把所有画圈的数加到一起就是最小值。
代码实现:
题目4:
举个例子:
这里初始资金是2,所以p2,p3都能做,但是p3的利润高,先选择p3。
现在的资金是7,所以p1,p2,p4都能做,p4的利润最高,先选择p4。
现在选出了2个,已经达到了k值,就不能再选择了,所以最大钱数是11。
解题思路:创建一个小根堆和一个大根堆,小根堆里按花费来排,大根堆里按利润来排。
初始资金是2,前面两个符合要求,我们就把前面两个弹出,放到大根组。
我们把大根堆的堆顶元素的利润弹出加到M上。然后弹出。
此时小根堆里面的元素都满足,弹出加到大根堆里。
再把大根堆的堆顶的利润加到M上,然后弹出。已经完成2个了,达到k值。
但是这里还存在一些问题,就是说我们的资金不能去做项目,并且大根堆里面也没有项目时,就直接返回。
代码实现:
项目的定义,有花费和利润两个成员函数。
这是两个比较方法,优先级队列的比较有点奇怪,如果要创建小根堆,父亲要比孩子大才会交换,创建小根堆,父亲要比孩子小才会交换。
题目5:
举个例子:
这里的x是墙:一定不能放灯,但是可以点亮,也可以不点亮。
这里点是居民:可以放灯,也可以不放灯,但是一定要点亮。
那么根据上面的条件,最优的放灯是这样的:
解题思路:一共有4种情况。
1.如果i位置是墙,直接i+1。
2.如果i位置是灯,i+1位置是墙,在i位置上放灯,然后直接去i+2位置上。
3.如果i位置是灯,i+1位置是灯,i+2位置是墙,在i位置上放灯,然后直接去i+3位置上。
4.如果i位置是灯,i+1位置是灯,i+2位置是灯,在i位置上放灯,然后直接去i+3位置上。
代码实现: