贪心算法讲解

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位置上。

代码实现：