文章目录
- 1. 贪心算法的概念
- 2. 讲解贪心
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
为什么这个策略是对的，我们就需要去证明：ab。
代码实现：
题目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位置上。
代码实现：
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
