共计 3134 个字符，预计需要花费 8 分钟才能阅读完成。
二叉树的递归套路临时先告一段落了，明天来聊聊贪婪算法。
一、什么是贪婪算法
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
