37|貪心算法:如何用貪心算法實現(xiàn)Huffman壓縮編碼?
貪心、分治、回溯象对、動態(tài)規(guī)劃這4個算法思想书妻，原理解釋起來都很簡單，但是要真正掌握且靈活應 用兰伤，并不是件容易的事情
貪心算法有很多經典的應用，比如霍夫曼 編碼(Huffman Coding)、Prim和Kruskal最小生成樹算法戚长、還有Dijkstra單源最短路徑算法。最小 生成樹算法和最短路徑算法我們后面會講到怠苔，所以我們今天講下霍夫曼編碼同廉，看看它是如何利用貪 心算法來實現(xiàn)對數(shù)據(jù)壓縮編碼，有效節(jié)省數(shù)據(jù)存儲空間的嘀略。
如何理解“貪心算法”?
我總結一下貪心算 法解決問題的步驟恤溶，我們一起來看看。 第一步帜羊，當我們看到這類問題的時候咒程，首先要聯(lián)想到貪心算法:針對一組數(shù)據(jù)，我們定義了限制值 和期望值讼育，希望從中選出幾個數(shù)據(jù)帐姻，在滿足限制值的情況下，期望值最大奶段。 類比到剛剛的例子饥瓷，限制值就是重量不能超過100kg，期望值就是物品的總價值痹籍。這組數(shù)據(jù)就是5種 豆子呢铆。我們從中選出一部分，滿足重量不超過100kg蹲缠，并且總價值最大棺克。 第二步悠垛，我們嘗試看下這個問題是否可以用貪心算法解決:每次選擇當前情況下，在對限制值同等 貢獻量的情況下娜谊，對期望值貢獻最大的數(shù)據(jù)确买。 類比到剛剛的例子，我們每次都從剩下的豆子里面纱皆，選擇單價最高的湾趾，也就是重量相同的情況下， 對價值貢獻最大的豆子派草。 第三步搀缠，我們舉幾個例子看下貪心算法產生的結果是否是最優(yōu)的。大部分情況下澳眷，舉幾個例子驗證 一下就可以了胡嘿。嚴格地證明貪心算法的正確性，是非常復雜的钳踊，需要涉及比較多的數(shù)學推理衷敌。而 且，從實踐的?度來說拓瞪，大部分能用貪心算法解決的問題缴罗，貪心算法的正確性都是顯而易?的，也 不需要嚴格的數(shù)學推導證明祭埂。
實際上面氓，用貪心算法解決問題的思路，并不總能給出最優(yōu)解蛆橡。
3.區(qū)間覆蓋
假設我們有n個區(qū)間舌界，區(qū)間的起始端點和結束端點分別是[l1, r1]，[l2, r2]泰演，[l3, r3]呻拌，......，[ln, rn]睦焕。 我們從這n個區(qū)間中選出一部分區(qū)間藐握，這部分區(qū)間滿足兩兩不相交(端點相交的情況不算相交)， 最多能選出多少個區(qū)間呢?
這個問題的處理思路稍微不是那么好懂垃喊，不過猾普，我建議你最好能弄懂，因為這個處理思想在很多貪心算法問題中都有用到本谜，比如任務調度初家、教師排課等等問題。
這個問題的解決思路是這樣的：我們假設這 n 個區(qū)間中最左端點是 lmin，最右端點是 rmax笤成。這個問題就相當于评架，我們選擇幾個不相交的區(qū)間眷茁，從左到右將 [lmin, rmax] 覆蓋上炕泳。我們按照起始端點從小到大的順序對這 n 個區(qū)間排序。
我們每次選擇的時候上祈，左端點跟前面的已經覆蓋的區(qū)間不重合的培遵，右端點又盡量小的，這樣可以讓剩下的未覆蓋區(qū)間盡可能的大登刺，就可以放置更多的區(qū)間籽腕。這實際上就是一種貪心的選擇方法。
貪心算法：N位數(shù)刪除K個數(shù)字纸俭，使剩下的數(shù)字串最小
題目：一個n位的數(shù)皇耗，去掉其中的k位，問怎樣去掉使得留下來的那個（n-k）位的數(shù)最凶岷堋郎楼？
分析：（刪數(shù)問題，可用貪心算法求解）窒悔，方法就是從簡單入手呜袁，慢慢復雜。從n=1開始推導就會發(fā)現(xiàn)規(guī)律简珠，
現(xiàn)在假設有一個數(shù)阶界，124682385，
假如k = 1聋庵，則結果為12462385,k = 2膘融，結果為1242385……
可以知道：最優(yōu)解是刪除出現(xiàn)的第一個左邊>右邊的數(shù)，因為刪除之后高位減小祭玉，很容易想...那全局最優(yōu)解也就是這個了氧映，因為刪除S個數(shù)字就相當于執(zhí)行了S次刪除一個數(shù)，因為留下的數(shù)總是當前最優(yōu)解...
def solution(num, k):
s = str(num)
flag = True
while k:
for i in range(len(s)-1):
#每次刪除第一個比下一個數(shù)字大的數(shù)
if s[i] > s[i+1]:
s = s.replace(s[i],'',1)
flag = False
break
#如果所有數(shù)字遞增攘宙，則刪除最后幾個數(shù)字直接返回
if flag:
s = s[:len(s)-k]
k -= 1
return int(s)
- 假設有 n 個人等待被服務屯耸，但是服務窗口只有一個，每個人需要被服務的時間長度是不同的蹭劈，如何安排被服務的先后順序疗绣，才能讓這 n 個人總的等待時間最短？
一直時間最短的先服務（堆）
