REST

贪心算法

1. 基本概念
   1. 最自然智慧的算法
   2. 用一种局部最功利的标准，总是能做出在当前看来是最好的选择
   3. 难点在于证明局部最优解最功利的标准可以得到全局最优解
   4. 对于贪心算法的学习主要是以增加阅历和经验为主
2. 解释
   1. 正例：通过一个例子来解释，假设一个数组中N个正数，第一个挑选出来的数乘以1，第二个挑选出来的数乘以2，同理，第N次挑选出来的数乘以N，总的加起来是我们的分数。怎么挑选数字使我们达到最大分数？
   2. 数组按从小到大的顺序排序，我们按顺序依次挑选，最终结果就是最大的。
   3. 本质思想是因子随着挑选次数的增加会增大，我们尽量让大数去结合大的因子。
3. 贪心算法有时是无效的，后面会贪心算法无效的例子
4. 贪心算法的证明问题:如何证明贪心算法的有效性？
   1. 一般来说，贪心算法不推荐证明，很多时候证明是非常复杂的。
   2. 通过下面例子来说明贪心算法证明的复杂性，从头到尾讲一道利用贪心算法求解的题目。

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

1. 题目解释:
   1. 字典序概念：直观理解，两个单词放到字典中，从头开始查找这个单词，哪个先被查找到，哪个字典序小。
   2. 字典序严格定义，我们把字符串当成k进制的数，a-z当成26进制的正数，字符长度一样，abk>abc，那么我们说abk的字典序更大。字符长度不一样ac和b，那么我们要把短的用0补齐，0小于a的accil，那么ac<b0，高位b>a即可比较出来大小。
   3. Java中字符串的ComparTo方法，就是比较字典序。
2. 本题思路1：
   1. 按照单个元素字典序贪心
      1. 例如在[ac,bk,sc,ket]字符串数组中，我们拼接出来最终的字符串字典序最小，那么我们依次挑选字典序最小的进行拼接的贪心策略得到acbkketsc。
      2. 但是这样的贪心不一定是正确的，例如[ba,b]按照上述思路的贪心结果是bba，但是bab明显是最小的结果
3. 本题思路2：
   1. 两个元素x和y，
      1. 如果x拼接y小于等于x拼接y，那么x放前，否则y放前面。
      2. 例如x=b,y=ba。bba大于bab的字典序，那么ba放前面
   2. 证明：
      1. 我们把拼接当成k进制数的数学运算，把a-z的数当成26进制的数，ks拼接ts实质是ks * 26^2 + te。
      2. 目标先证明我们比较的传递性：证明a拼接b小于b拼接a，b拼接c小于等于c拼接b，推出a拼接c小于等于c拼接a。
      3. a拼接b等于a乘以k的b长度次方 + b。m(x)函数:k的x长度次方

         a * m(b) + b <= b * m(a) + a  
         b * m(c) + c <= c * m(b) + b 
         => 两边×c,移项
         a * m(b) * c <= b * m(a) * c + ac - bc
         b * m(c) * a + ca - ba <= c * m(b) * a 
         =>
         b * m(c) * a + ca - ba <= b * m(a) * c + ac - bc
         => 
         m(c) * a + c <= m(a) * c + a
         

      4. 证毕
      5. 至此，我们证明出我们的排序具有传递性质。
      6. 根据我们排序策略得到的一组序列，证明我们任意交换两个字符的位置，都会得到更大的字典序。
      7. 例如按照思路二得到的amnb序列，我们交换a和b。
         1. 我们先把a和m交换，由于按照思路二得到的序列，满足a.m <= m.a 那么所以manb > amnb，同理得到amnb < bmna。
      8. 再证明任意三个交换都会变为更大的字典序，那么最终数学归纳法，得到思路二的正确性
      9. 所以贪心算法的证明实质是比较复杂的，我们大可不必每次去证明贪心的正确性
   3. 全排列的时间复杂度为：O(N!)
   4. 每一种贪心算法有可能都有属于他自身的特有证明，例如哈夫曼树算法，证明千变万化

贪心算法求解思路

1. 标准求解过程

   1. 分析业务
   2. 根据业务逻辑找到不同的贪心策略
   3. 对于能举出反例的策略，直接跳过，不能举出反例的策略要证明有效性，这往往是比较困难的，要求数学能力很高且不具有统一的技巧性

2. 贪心算法解题套路

   1. 实现一个不依靠贪心策略的解法X,可以用暴力尝试
   2. 脑补出贪心策略A,贪心策略B,贪心策略C…
   3. 用解法X和对数器，用实验的方式得知哪个贪心策略正确
   4. 不要去纠结贪心策略的证明
   5. 提醒:
      贪心类的题目在笔试中，出现的概率高达6到7成，而面试中出现贪心的概率不到2成。因为笔试要的是淘汰率，面试要的是区分度。由于贪心的解决完全取决于贪心策略有没有想对，有很高的淘汰率但是没有很好的区分度

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。