二叉树的递归套路临时先告一段落了，明天来聊聊贪婪算法。

一、什么是贪婪算法

1、最具天然智慧的算法

用最一般的思维就能想到的解决办法。

2、用一种部分最功利的规范，总是做出在以后看来是最好的抉择

3、难点在于证实部分最功利的规范能够失去全局最优解

4、对于贪婪算法的学习次要以减少经历和教训为主

对于每一个利用贪婪算法求解的题目，理论采取的贪婪策略都是不同的，也就是说以后的贪婪策略并不能帮忙你解决另外的贪婪题目，然而可能减少你的教训，让你学会如何尝试。

5、只有可能应用对数器校验策略是对的即可

对于每一个贪婪策略，在提出之初，不能举出显著的反例，咱们就能够尝试按此写出代码来，而后用最暴力的形式写出对数器来校验，校验通过则阐明咱们的贪婪策略是对的，否则就须要换一个贪婪策略了。

至于如何去证实验证通过的贪婪策略真的就是对的，这不是咱们须要关怀的事件，把证实留给做学术研究的就能够了。

二、从头到尾讲一道贪婪算法的题目

1、题目形容

给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有拼接后果中，字典序最小的后果。

字典序定义：Java中字符串的排序形式，比方 “abc” 和 “bce”相比，“abc” 第一位a的ASCII码小于 “bce” 第一位b的ASCII码，所以 “abc” < “bce”，所以“abc”的字典序更小。对于位数不等的字符串，“abc” 和 “be”，从各自的第一位开始比拟，“abc”的a小于“be”的b，所以“abc” < "be"。

2、思路

（1）谬误的

可能最直观的解法就是，所有字符串按字典序先排序，将排序后的字符串顺次拼接起来就是最初的后果。

反例：["b", "ba"]，各字符串按字典序先排序的后果是["b", "ba"]，最初拼接的字符串是"bba"，然而本例的最终后果是"bab"，因为"bab" < "bba"。所以这样的贪婪策略是错的。

（2）正确的

对于任意两个字符串 A和B，如果 A与B 的拼接后果小于 B与A 的拼接后果则A排在后面，否则B排在后面，依照这样的策略将整个字符串数组先排序一遍，再将排序后的数组挨个拼接起来失去的后果就是最终的后果。

这时候就存在一个问题了，对于任意的应用贪婪策略求解的题，贪婪策略的提出是比拟容易的，然而如何证实它是正确的就比拟难了。

不要忘了，咱们有对数器啊，咱们能够应用最暴力的解法获取正确答案，再和咱们贪婪策略取得的后果进行比拟，不等则阐明咱们的贪婪策略存在问题，那么，连忙换另外的贪婪策略。

总结：任何贪婪策略都是先提出再证实，既然咱们有对数器，咱们何必再花大力量去用证实的形式来确定贪婪策略的正确性呢？证实还是留给做学术研究的人来做吧。

3、口试面试中呈现的概率

贪婪算法在口试中呈现的概率更高，在和面试官间接面试时，呈现的概率反而不高。为啥？

因为贪婪策略的代码都很简略，定义好比拟的规范，也就是定义好比拟器，依照此规范排序或应用堆，最初就失去后果了。也就是说

（1）起不到考查Coding的作用，只有定义好规范，而后应用排序或堆就能失去后果了；

（2）贪婪策略的区分度不够，想对了策略就是满分，没有想对就是0分，分不出各种档次来；

4、代码

/** * @author Java和算法学习：周一 */public static class MyComparator implements Comparator<String> {    @Override    public int compare(String o1, String o2) {        return (o1 + o2).compareTo(o2 + o1);    }}public static String lowestDictionary(String[] str) {    if (str == null || str.length < 1) {        return null;    }    Arrays.sort(str, new MyComparator());    StringBuilder result = new StringBuilder();    for (String s : str) {        result.append(s);    }    return result.toString();}

是不是发现只有贪婪策略想好了，代码是及其的简略。

蕴含对数器的所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/LowestDictionary.java

三、会议室问题

1、题目形容

一些会议要占用一个会议室宣讲，会议室不能同时包容两个会议的宣讲。给你每个我的项目的开始工夫和完结工夫，你来安顿宣讲的日程，要求会议室进行宣讲的场次最多。返回最多的宣讲场次数量。

2、贪婪策略

可能咱们会有以下的一些贪婪想法：

（1）哪个会议开始工夫早，我就安顿这个会议。那这个想法对不对呢？

反例：[8, 21]，[9, 10]，[10, 12]，[15, 20]，很显著开始工夫最早的会议是[8, 21]，然而安顿了这个会议后，其余的会议就安顿不了了，然而此时的最优解是安顿[9, 10]，[10, 12]，[15, 20]三个会议，所以这个想法不成立。

（2）哪个会议持续时间短，我就安顿这个会议。那这个想法对不对呢？

反例：[8, 15]，[14, 18]，[17, 24]，很显著会议持续时间最短的是[14, 18]，然而选了这个会议其余两个就不能选了，然而此时的最优解是安顿[8, 15]，[17, 24]两个会议，所以这个想法不成立。

（3）哪个会议完结工夫早，我就安顿这个会议。那这个想法对不对呢？

对（至多目前看来是对的）。因为以后不能显著举出反例来，然而咱们还得拿对数器来校验是否真的对。至于证实，留给做学术研究的来做吧。

3、思路

所有会议先依据完结工夫按从小到大排序。

安顿第一个会议A，将剩下会议的开始工夫小于A会议完结工夫的会议剔除，

剩下的再安顿第一个会议B，将剩下会议的开始工夫小于B会议完结工夫的会议剔除，直到没有能够安顿的会议。

4、代码

/** * 假如会议开始工夫和完结工夫都是 大于0 的数值 *  * @author Java和算法学习：周一 */public static int bestArrange(Meeting[] meetings) {    // 所有会议先依据完结工夫按从小到大排序    Arrays.sort(meetings, (o1, o2) -> o1.end - o2.end);    // 曾经安顿的会议数量    int result = 0;    // 以后所处工夫点    int timeLine = 0;    // 遍历所有会议，完结工夫早的曾经在前    for (Meeting meeting : meetings) {        // 剩下会议的开始工夫在此时会议完结工夫之后，则安顿剩下会议中的第一个会议        if (meeting.start >= timeLine) {            result++;            timeLine = meeting.end;        }    }    return result;}

蕴含对数器的所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/BestArrange.java