37 | 贪心算法：如何用贪心算法实现Huffman压缩编码？

精选留言(122)

• 

  cirno

  1、由最高位开始，比较低一位数字，如高位大，移除，若高位小，则向右移一位继续比较两个数字，直到高位大于低位则移除，循环k次，如：
  4556847594546移除5位-》455647594546-》45547594546-》4547594546-》4447594546-》444594546
  
  2、由等待时间最短的开始服务

  2018-12-17

   9

   139
• 

  开心小毛

  找零问题不能用贪婪算法，即使有面值为一元的币值也不行：考虑币值为100，99和1的币种，每种各一百张，找396元。
   动态规划可求出四张99元，但贪心算法解出需三张一百和96张一元。

  作者回复: 是的 👍

  2018-12-31

   3

   71
• 

  Alexis何春光

  留言里feifei说的两种解决思路都是错的，给的链接也失效了.... 老师可以回复一下防止误导后来的同学呀！
  以及没有看出来霍夫曼算法和贪心算法有什么联系，求详细讲解

  2019-01-12

   5

   27
• 

  Jalyn

  想知道目前没掉队的有多少 哈哈

  作者回复: 慢慢学 不着急😄

  2018-12-17

   1

   26
• 

  qinggeouye

  1、在一个非负整数 a 中，希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？
  
  整数 a，由若干位数字组成，移除 k 个数字后的值最小。从高位开始移除：移除高位数字比它低位数字大的那个；K 次循环。
  
  也可以用 Top K 排序，求出 K 个最大的数字，移除。
  
  2、假设有 n 个人等待被服务，但是窗口只有一个，每个需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时间最短？
  
  每个人需要被服务的时间不一样，但所有人加起来总的被服务时间是固定的。
  
  题意是求 n 个人总的等待时间，每个人在被服务之前，所经过的等待时间是不同的。
  
  而当前被服务的人所需的服务时间，会累加到剩下的那些等待被服务人的等待时间上。
  
  要使 n 个人总的等待时间最短，那么每次安排服务时间最短的那个人被服务：堆排序（小顶堆）。
  
  
  另外，@Alexis何春光 的留言，第一句话表示赞同。

  2019-01-19

  

   24
• 

  feifei

  1，在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？
  对于此题，我的求解思路是每次选择数据的最高位的数据值进行移除，这样我们每次选择的移除的数值都是最大的，剩下的数值也是最小的。
  比如，数据5892，将数据拆成5000,800,90,2，然后使用大顶堆来进行存储，然后每次移除大顶堆中堆顶最大的元素。
  
  2，假设有 n 个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时间最短？
  对于此问题，我的求解思路是让待时间最长的来安排先后顺序
  比如，现在有3个人，a、b、c,a等待了10分钟，b待待了20分钟，c待待了30分钟
  同样使用大顶堆来进行存储等待时间，堆顶的元素就是当前等待时间最长的人
  然后每次从堆拿出堆顶元素的人来进行服务，这样就可以让这n个人的总的等待时间最短。
  
  
  
  
  对于学习的贪心算法，老师虽然只进行了理论讲解，但我看完了老师所讲的，我对贪心算法的理解有了一定的认识，我就试着把贪心算法的内容中涉及的东西，都翻译成了代码，
  感觉收获良多，也把这个分享给童鞋，希望对他们有帮助。
  1，这是第一个示例，背包中豆子的最大价值的问题
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case1
  2，这是孩子分糖果的问题
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case2
  3，这是钱币支付的问题
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case3
  4，这是区间覆盖的问题
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case4
  5，这是霍夫漫编码的实现
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/huffman
  
  欢迎大家与我交流，也欢迎老师给我指正，谢谢

  2018-12-20

   9

   18
• 

  🐱您的好友William🐱

  给大家提个醒，货币找零问题如果没有C1货币的话得用动态规划去解，如果出现{C2，C7，C10}货币找零11块的时候使用greedy就会出现找不开的情况。。。。有C1就不会出现找不开的情况且多个C1可以构成任何面值，所以这种情况下使用greedy是对的！（leetcode322题调了一下午的路过。。。）

  2018-12-17

  

   11
• 

  luxinfeng

  老师能详细讲讲区间覆盖这个问题的选择过程么？

  2018-12-17

  

   11
• 

  睡痴儿😑

  第一个题，可以反着来想。给定另一个数组，怎么从中原本的中挑出n-k个，使其值最小。
  首先第一位必须要是最小的一个，但是因为有顺序，所以只能是从0到n-1-k个中挑一个最小的，下标为m。以后依次类推，从m到n-k中挑一个最小的。如果有相等的情况，以下标小的为准。
  第二个，就是从小到大排序即可。

  2019-01-22

  

   8
• 

  www.xnsms.com小鸟接码

  霍夫曼编码，用一个树来避免某个字符的编码是另一个字符编码的前缀，真的是好巧妙

  2019-01-06

  

   8
• 

  bingo

  @吴：wiki上的哈夫曼树是标准的生成步骤，老师这里举的例子是一种特殊情况，哈夫曼树构建的一般性方法在本科的教程上就写的很通俗了。
  我用wiki里的值举个例子吧：原始集合的值是[2,3,4,4,5,7]
  第一步：从原始集合中取出最小的两个值并将这两个值从原始集合中剔除，这两个最小的值相加得到一个新的值并加入原始集合，这两个小值作为这个新值的树叶，新值当然就是树根了。这一步执行之后原始集合就变成了这样：
         [ ⑤, 4,4,5,7]
  / \
        2 3
  
  第二步：从更新后的集合中再取最小的两个值并剔除，同样相加得到新值加入到集合。这一步执行之后集合就变成了
         [⑤, ⑧ ,5,7]
  / \ /\
        2 3 4 4
  
  第三步，重复以上步骤，你懂得。结果是：
         [ ⑩, ⑧, 7]
  / \ / \
          5 ⑤ 4 4
  / \
  2 3
  第四步，结果是：
         [ ⑩, 15,]
  / \ / \
        5 ⑤ 7 ⑧
  /\ / \
  2 3 4 4
  最后一步，结果是：
                 (25) (打不出圆圈了，用这个代替，应该不难理解，嗯)
                / \
           ⑩ 15
  / \ / \
        5 ⑤ 7 ⑧
  /\ / \
  2 3 4 4
  
  wiki哈夫曼树链接：https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
  ps:大半夜手打，排版扎心

  作者回复: 👍啊 就喜欢你这么极致的人！

  2019-02-22

  

   6
• 

  Jerry银银

  打个卡，我还在

  2018-12-19

  

   6
• 

  小美

  老师 区间覆盖的问题， (1-5) 和 (2-4) 中为什么选(2-4) 方便老师解释下吗， 贪心不能全局最优 用贪心 如何在这个问题上全局最优呢

  作者回复: 24让剩下的没有被覆盖的区间最大 如果你选15 那我完全可以用24替代15 这样子 只有更好 不会更差

  2018-12-17

  

   6
• 

  CathyLin

  课后思考：
  1. 第一道题一开始没有想到...以为直接删除最大的那 k 个数字就好了，后来举了几个样例发现是错的。然后看了评论区小伙伴们的留言，太奇妙了！！！我是真的没有想到这种思路😫
  1) 从高位往低位走，删掉高位比低位大的数；为什么这样子是好的呢？试想:
  4596743 如果我们只能删一位，我们会删第三位的 9，因为这样就相当于是把高位给减少了，变成了456743，但是如果删 6，变成了 459743 则没有之前那个优。删后面的数更起不到高位的那种作用。
  2) 如果所有数字都是递增的，那么我们删除倒数
  k 个数字就好了。
  
  2. 想让所有人的等待时间最短，那么我们得先处理服务时间短的，尽快把他们处理完了才能够处理后面的人！
  
  贪心反思：有些时候思路还是难以打开，可能还是跟老师说的那样，多练习、多积累才是最好的学习方法！

  2019-07-31

  

   4
• 

  coder

  区间覆盖问题，把区间按照结束时刻排序，每次选择最早结束且没有冲突的区间即可

  2019-04-15

  

   4
• 

  Ying

  经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了------- ,这个位置 我算了一下各个和相加，结果是1910bits吧， 是我算的不对吗 ？

  2019-01-11

  

   3
• 

  白若

  思考题(自己的想法，不知道对不对，希望老师能给我评论。)
  
  1.从前往后两两比较，若前数大于等于后数，选择移除。如果一轮下来没达到k个数，就移除最后的m个数，m为k-已选出个数。
  2.时间越短位置越靠前。

  2018-12-17

  

   3
• 

  蒋礼锐

  第一个问题不知道0可不可以被保留在最高位，如果可以的话那么应该每次移除该整数的非零最高位，比如909090，k为2的话，最小的值应该是0090，如果0不能在最高位，就贪心算法就不能得到最优解了，跟之前的加权图一样，因为决策会相互影响。
  
  第二个问题假设5个人，时间分别是1-5-3-4-2分钟，等待的时间是每个人等待时间的总和即单个服务时间*剩余等待人数。不管现在服务的是谁，剩余等待的人数是不会变的，所以只需要找单个服务时间最小的，即按服务时间数升序服务即1-2-3-4-5，总的时间为1*4+2*3+3*2+4*1=20
  
  就像春运取票，你如果是去取售票机上买票的话，后面排队着急的人会说，让我先取吧，我直接取很快。这样集体时间效率最高，但是对单个个体来说就不一定了，比如之前那个要买票的。

  2018-12-17

   1

   3
• 

  天，很蓝 ～

  如果文档中只有4个字符，分别是a，b，c，d出现的频率相等，都是100次。如果用00，01，10，11分别表示a，b，c，d的话，总共需要800bit就可以了。但是如果用霍夫曼编码的话，用1，01，001，000分别表示a，b，c，d的话反而需要900bit。这个是不是说明霍夫曼编码有时候是起不到压缩作用的？望老师解答

  作者回复: 用霍夫曼编码也是00、01、10、11的，你再看下霍夫曼编码的原理吧

  2019-06-20

   3

   2
• 

  乐凡

  老师，我觉得那个霍夫曼编码可能有点缺陷，就是不同字符在字符串中出现的频率很接近，那如果还是按照给每个字符用不同长度的二进制码表示，很有可能会比前面用相同二进制码表示耗费的空间多（亲自测过）。我觉得每一个字符在字符串中出现的频率需要满足一定的大小差距，这样使用空间才会比使用相同数量的二进制码更少。这个大小差距点的公式不太好算，笨一点的办法就是用两种方式比较下占用空间大小。

  作者回复: 给个你的测试用例我看看

  2019-03-21

  

   2