二叉树的递归套路暂时告一段落，今天来说说贪心算法。一、什么是贪心算法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在前。按照这个策略，整个字符串数组先排序一次，然后把排序好的数组一个一个拼接，得到最后的结果。这时候就有问题了。对于任何使用贪心策略解决的问题，提出贪心策略都相对容易，但要证明其正确性则比较困难。别忘了，我们有一个对数，我们可以用最暴力的解法得到正确的答案，然后和我们的贪心策略得到的结果进行比较。如果不相等，说明我们的贪心策略有问题。然后，迅速换成另一种Greedy策略。总结：任何贪心策略都是先提出再证明。既然我们有了对数，为什么还需要花费大量的精力通过证明的方式来确认贪心策略的正确性呢？证明还是留给做学术研究的人吧。3.笔试面试出现的概率贪心算法在笔试出现的概率较高，但是在面试官的直接面试中出现的概率不高。为什么？因为贪心策略的代码很简单，定义比较标准，也就是定义比较器，按照这个标准排序或者使用堆，最后得到结果。也就是说（1）不能起到检查Coding的作用，只要定义好标准，然后用排序或者堆就可以得到结果；（2）贪心策略区分度不够，想对了就是满分，想不对就是0分，无法区分各个层级；4.代码/***@authorJava与算法学习：星期一*/publicstaticclassMyComparatorimplementsComparator{@Overridepublicintcompare(Stringo1,Stringo2){return(o1+o2).compareTo(o2+o1);}}publicstaticStringlowestDictionary(String[]str){if(str==null||str.length<1){returnnull;}。数组排序(str,newMyComparator());StringBuilder结果=newStringBuilder();for(Strings:str){result.append(s);}返回结果.toString();是的，代码非常简单。包含对数所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/LowestDictionary.java3.会议室问题1.题目描述一些会议要求占一个用于演示的会议室，该会议室不能同时容纳两个会议演示。给你每个项目的开始时间和结束时间，你安排演示的日程，要求会议室能举行最多的演示。返回最大讲座数。2.贪心策略我们可能会有以下贪心的想法：(1)哪个会议开始得早，我就安排这个会议。这个想法对吗？反例：[8,21],[9,10],[10,12],[15,20]，明明最早开始时间的会议是[8,21]，但是安排好这个会议之后，其他meetings是安排不了的，但是此时的最优方案是安排三个会议[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的值**@authorJava与算法学习：Monday*/publicstaticintbestArrange(Meeting[]meetings){//Allmeetingsendfirst时间从小到大排序Arrays.sort(meetings,(o1,o2)->o1.end-o2.end);//预定会议数intresult=0;//当前时间点inttimeLine=0;//遍历所有会议，结束时间早的为earlyfor(Meetingmeeting:meetings){//如果剩余会议的开始时间在本次会议结束时间之后，则将第一个会议安排在剩余会议中if(meeting.start>=timeLine){结果++;timeLine=meeting.end;}}returnresult;}所有代码地址包括对数：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/BestArrange.java
