一些能夠解決生活中一些具體問題的常用算法的整理集合

這是一篇八千字的長(zhǎng)文，是一些算法筆記的整理集合，希望能給你幫助。

曾經(jīng)有一個(gè)著名的騙局：

小明是一個(gè)賭馬愛好者，最近他連續(xù)幾次提前收到了預(yù)測(cè)賭馬結(jié)果的郵件，從一開始由于不屑而錯(cuò)失良機(jī)，到漸漸深信不疑，直到最后給郵件發(fā)送方匯了巨款才發(fā)現(xiàn)上當(dāng)。

看過(guò)這個(gè)的人應(yīng)該知道，騙子收集到一份郵件信息后，分組發(fā)送不同預(yù)測(cè)結(jié)果的郵件，賭馬結(jié)果公布后，再將篩選出來(lái)的那部分人分組，繼續(xù)發(fā)送下一輪預(yù)測(cè)郵件。幾輪過(guò)后，肯定能保證一部分人收到的預(yù)測(cè)結(jié)果是完全正確的。這也是最關(guān)鍵的部分。

那么騙子是如何從幾萬(wàn)或幾十萬(wàn)用戶中尋找這些“幸運(yùn)兒”的呢？這是一種二分法的思想。

假如要順序在100萬(wàn)人中尋找一個(gè)人，最多需要100萬(wàn)次，而二分法只需要18次。

下面講講一些能夠解決生活中一些具體問題的常用算法。

二分查找

對(duì)于一個(gè)長(zhǎng)度為N的數(shù)組，簡(jiǎn)單查找最多需要N步；二分查找最多只需要logN步（約定底數(shù)為2）。

二分查找相較于簡(jiǎn)單查找，極大地提高了效率，但是二分查找的前提是列表是有序的，這也導(dǎo)致了諸多限制。

下面使用二分法編寫一個(gè)查找算法。

Python實(shí)現(xiàn)

1def binary_search(list,target): 2 #查找的起點(diǎn)和終點(diǎn) 3 low=0 4 high=len(list)-1 5 # 6 while (low<=high): 7 ? ? ? ?#若low+high為奇數(shù)，則向下取整 8 ? ? ? ?mid=(low+high)//2 9 ? ? ? ?temp=list[mid]10 ? ? ? ?if target==temp:11 ? ? ? ? ? ?return mid12 ? ? ? ?elif temp>target:13 high=mid-114 else:15 low=mid+116 return None17if __name__ == '__main__':18 test_list=[1,2,4,5,12,32,43]19 print(binary_search(test_list,4))20 print(binary_search(test_list, 44))

輸出結(jié)果:

122None

遞歸

想象這么一個(gè)問題，在一個(gè)大盒子里，有若干個(gè)小盒子，在這些小盒子里也可能有更小的盒子。在所有盒子中，其中一個(gè)盒子內(nèi)有一把鑰匙，如何找到這把鑰匙?

有兩種思路：

第一種：

image.png

第二種

image.png

哪一種思路更加清晰呢？我們用代碼來(lái)實(shí)現(xiàn)一下：

第一種首先新建兩個(gè)類型盒子和鑰匙：

1class Box: 2 name=None 3 box=None 4 key=None 5 def __init__(self,name): 6 self.name=name 7 def set_box(self,box): 8 self.box=box 9 def set_key(self,key):10 self.key=key11class Key:12 name=None13 def __init__(self,name):14 self.name=name

查找算法：

1def look_for_key(box): 2 pile_box=box 3 i=0 4 while pile_box is not None: 5 #默認(rèn)取出盒子堆中的第一個(gè) 6 handle_box=pile_box[0] 7 print("取出了："+handle_box.name) 8 if handle_box.key is not None: 9 print("在"+handle_box.name+"中找到了鑰匙")10 return handle_box.key.name11 elif handle_box.box is not None:12 pile_box.append(handle_box.box)13 print("將"+handle_box.box.name+"放入盒子堆")14 pile_box.remove(handle_box)15 return "沒有找到鑰匙"

測(cè)試數(shù)據(jù)：

1if __name__ == '__main__': 2 #現(xiàn)在我創(chuàng)建一把鑰匙 3 key1=Key("我是鑰匙") 4 #現(xiàn)在我將鑰匙放在盒子1中 5 b1 = Box("1號(hào)盒子") 6 b1.set_key(key1) 7 # 創(chuàng)建多個(gè)盒子，互相放置 8 b2=Box("2號(hào)盒子") 9 b2.set_box(b1)10 b3=Box("3號(hào)盒子")11 b3.set_box(b2)12 b4=Box("4號(hào)盒子")13 b4.set_box(b3)14 b5=Box("5號(hào)盒子")15 #將這些盒子放入一個(gè)大盒子16 main_box=[b4,b5]17 print(look_for_key(main_box))

輸出：

1取出了：4號(hào)盒子 2將3號(hào)盒子放入盒子堆 3取出了：5號(hào)盒子 4取出了：3號(hào)盒子 5將2號(hào)盒子放入盒子堆 6取出了：2號(hào)盒子 7將1號(hào)盒子放入盒子堆 8取出了：1號(hào)盒子 9在1號(hào)盒子中找到了鑰匙10我是鑰匙

第二種（遞歸方式）

新建類型還是使用之前的，主要是重新寫一種查找算法：

1def look_for_key(box): 2 print("打開了"+box.name) 3 if box.key is not None: 4 print("在" + box.name + "中找到了鑰匙") 5 return 6 else: 7 look_for_key(box.box) 8if __name__ == '__main__': 9 #現(xiàn)在我創(chuàng)建一把鑰匙10 key1=Key("我是鑰匙")11 #現(xiàn)在我將鑰匙放在盒子1中12 b1 = Box("1號(hào)盒子")13 b1.set_key(key1)14 # 創(chuàng)建多個(gè)盒子，互相放置15 b2=Box("2號(hào)盒子")16 b2.set_box(b1)17 b3=Box("3號(hào)盒子")18 b3.set_box(b2)19 b4=Box("4號(hào)盒子")20 b4.set_box(b3)21 #將這些盒子放入一個(gè)大盒子22 main_box=Box("主盒子")23 main_box.set_box(b4)24 look_for_key(main_box)

輸出：

1打開了主盒子2打開了4號(hào)盒子3打開了3號(hào)盒子4打開了2號(hào)盒子5打開了1號(hào)盒子6在1號(hào)盒子中找到了鑰匙

總結(jié)以上兩種查找方式：使用循環(huán)可能使效率更高，使用遞歸使得代碼更易讀懂，如何選擇看哪一點(diǎn)對(duì)你更重要。

使用遞歸要注意基線條件和遞歸條件，否則很容易不小心陷入死循環(huán)。

快速排序

D&C

D&C(divide and conquer)分而治之是一種重要的解決問題思路。當(dāng)面對(duì)問題束手無(wú)策時(shí)，我們應(yīng)該考慮一下：分而治之可以解決嗎？

現(xiàn)在有一個(gè)問題，假如一塊土地（1680*640）需要均勻地分為正方形，而且正方形的邊長(zhǎng)要盡量的大。該怎么分？

這個(gè)問題本質(zhì)就是求兩條邊長(zhǎng)的最大公因數(shù)。可以使用歐幾里得算法（輾轉(zhuǎn)相除）

1def func(num1,num2): 2 temp=0 3 while(num1%num2): 4 temp=num1%num2 5 num1=num2 6 num2=temp 7 return temp 8if __name__ == '__main__': 9 num1=168010 num2=64011 print(func(num1,num2))

快速排序

快速排序是一種常用的排序算法，比選擇排序快得多（O(n^2)）,快速排序也使用了D&C。

選擇基準(zhǔn)值

將數(shù)組分成兩個(gè)子數(shù)組：基準(zhǔn)值左邊的數(shù)組和基準(zhǔn)值右邊的數(shù)組

對(duì)這兩個(gè)數(shù)組進(jìn)行快速排序

來(lái)寫一下代碼實(shí)現(xiàn)：

1def quicksort(list): 2 if len(list)<2: 3 ? ? ? ?return list 4 ? ?else: 5 ? ? ? ?#暫且取第一個(gè)值作為基準(zhǔn)值 6 ? ? ? ?pivot=list[0] 7 ? ? ? ?less=[] 8 ? ? ? ?greater=[] 9 ? ? ? ?for item in list:10 ? ? ? ? ? ?if itempivot:13 greater.append(item)14 return quicksort(less)+[pivot]+quicksort(greater)15if __name__ == '__main__':16 test_list=[2,43,53,12,542,3253]17 print(quicksort(test_list))

輸出結(jié)果：

1[2, 12, 43, 53, 542, 3253]

快速排序的最糟情況是O(n^2),O(n^2)已經(jīng)很慢了，為什么還要叫它快速排序呢?

快速排序的平均運(yùn)行時(shí)間為O（nlogn）,而合并排序的時(shí)間總是O（nlogn），合并排序似乎更有優(yōu)勢(shì)，那為什么不用合并排序呢？

因?yàn)榇驩表示法中的n是一個(gè)常量，當(dāng)兩種算法的時(shí)間復(fù)雜度不一樣時(shí)，即使n在數(shù)值上不同，對(duì)總時(shí)間的影響很小，所以通常不考慮。

但有些時(shí)候，常量的影響很大，對(duì)快速排序和合并排序就是這樣，快速排序的常量小得多，所以當(dāng)這兩種算法的時(shí)間復(fù)雜度都為O（nlogn）時(shí)，快速排序要快得多。而相較于最糟的情況，快速排序遇上平均情況的可能性更大，所以可以稍稍忽視這個(gè)問題。（快速排序最糟的情況下調(diào)用棧為O(n),在最佳情況下，調(diào)用棧長(zhǎng)O(logn)）

散列表

使用散列函數(shù)和數(shù)組可以構(gòu)建散列表，散列表是包含額外邏輯的數(shù)據(jù)結(jié)構(gòu)。

但是要編寫出完美的散列函數(shù)幾乎不可能，假如給兩個(gè)鍵分配的空間相同的話就會(huì)出現(xiàn)沖突。如何處理沖突呢?最簡(jiǎn)單的辦法是：假如在某一空間上產(chǎn)生沖突，就在這一空間后再加上一個(gè)鏈表。但是假如這個(gè)鏈表很長(zhǎng)，會(huì)很影響查找的速度（鏈表只能順序查找，查找時(shí)間為O(n)）

所以一個(gè)能盡量避免沖突的散列函數(shù)是多么重要，那么怎么編寫一個(gè)性能較高的散列表呢？

較低的填裝因子（一旦填裝因子大于0.7，就需要調(diào)整長(zhǎng)度）

良好的散列函數(shù)（讓數(shù)組中的值呈均勻分布，可以了解下SHA函數(shù)）

廣度優(yōu)先搜索

廣度優(yōu)先搜索能夠解決兩個(gè)問題：

兩個(gè)節(jié)點(diǎn)之間是否存在相連的路徑

最短的距離是多少？這個(gè)“最短距離”的含義有很多種。

想象這么一個(gè)問題：你想在你的微信好友和好友的好友中尋找是否有人是一名消防員，該如何查找？并且盡可能這人和你的關(guān)系更近些。

實(shí)現(xiàn)：

1from collections import deque 2def is_fireman(person): 3 #假設(shè)一個(gè)很簡(jiǎn)單的判斷，假設(shè)消防員的名字尾部為f 4 return person[-1]=='f' 5def search_fireman(search_graph): 6 search_queue=deque() 7 search_queue+=search_graph["i"] 8 while search_queue: 9 person=search_queue.popleft()10 if is_fireman(person):11 return person12 else:13 if search_graph.__contains__(person):14 #假如這個(gè)人不是消防員，就將這個(gè)人的朋友全加入隊(duì)列15 search_queue+=search_graph[person]16 return "你的圈子里沒有消防員"17if __name__ == '__main__':18 test_graph={}19 test_graph["i"]=["Alice","Abby","Barry"]20 test_graph["Alice"]=["Bob","Tom"]21 test_graph["Abby"]=["Cart","Jay"]22 test_graph["Barry"]=["Welf","Zos"]23 print(search_fireman(test_graph))

輸出結(jié)果:

1Welf

迪克斯特拉算法

在圖中，搜索最小的“段”數(shù)可以用廣度優(yōu)先算法，這就相當(dāng)于默認(rèn)每條邊的權(quán)重是相同的，如果每條邊的權(quán)重不同呢？那就需要用到迪克斯特拉算法。

概括來(lái)說(shuō)，迪克斯特拉算法就是從起點(diǎn)開始，首先尋找最廉價(jià)的節(jié)點(diǎn)，更新其開銷并標(biāo)記為已處理，然然后在未處理的節(jié)點(diǎn)中尋找開銷最小的節(jié)點(diǎn)，然后以此往復(fù)下去。

針對(duì)書中的這樣一個(gè)問題，我把題干提取出來(lái)：目標(biāo)是用樂譜換鋼琴?，F(xiàn)在樂譜可以免費(fèi)換海報(bào)；海報(bào)加30元換吉他；海報(bào)加35元換架子鼓；樂譜加5元可以換唱片；唱片加15元換吉他；唱片加20元換架子鼓；吉他加20元換鋼琴；架子鼓加10元換鋼琴。

現(xiàn)在我用圖把這個(gè)關(guān)系表示出來(lái)：

可以看出這是一個(gè)加權(quán)圖，現(xiàn)在我們要使用迪克斯特拉算法尋找最短路徑。

代碼實(shí)現(xiàn)：

1#檢索圖 2def dijkstra_find(costs,parent,processed): 3 #找到當(dāng)前最廉價(jià)的節(jié)點(diǎn) 4 node =lowest_cost_node(costs,processed) 5 while node is not None: 6 cost=costs[node] 7 if not graph.__contains__(node): 8 break 9 neighbours=graph[node]10 for key in neighbours.keys():11 new_cost=cost+neighbours[key]12 if costs.__contains__(key):13 if costs[key] > new_cost:14 costs[key] = new_cost15 parent[key] = node16 else:17 costs[key]=new_cost18 parent[key] = node19 processed.append(node)20 node = lowest_cost_node(costs,processed)21#在開銷表中尋找最廉價(jià)的節(jié)點(diǎn)22def lowest_cost_node(costs,processed):23 lowest_cost=float("inf")24 lowest_node=None25 for node in costs:26 cost=costs[node]27 if cost

輸出：

最后的最低開銷表為：

父子節(jié)點(diǎn)表為：

可以看出，最優(yōu)的交換的路徑為：piano-drum-record-music

最低開銷為：35元

貝爾曼-福德算法

在迪克特拉斯算法的基礎(chǔ)上，我們考慮這樣一種情況，假如邊的權(quán)重存在負(fù)值。

在迪克特拉斯算法中，我們首先尋找最廉價(jià)的節(jié)點(diǎn)，更新其開銷，再尋找未處理節(jié)點(diǎn)中最廉價(jià)的節(jié)點(diǎn)，以此往復(fù)。

可能出現(xiàn)這樣一個(gè)情況：

在將海報(bào)標(biāo)記為已處理后，開始處理唱片，但是唱片到海報(bào)的路徑使得海報(bào)的開銷更小，又將更新海報(bào)的開銷，但是海報(bào)已經(jīng)標(biāo)記為已處理。那么就會(huì)出現(xiàn)一些問題。假如繼續(xù)使用迪克特拉斯算法，最后的結(jié)果肯定是錯(cuò)的，大家可以更改參數(shù)試一下。為了正確解決問題，這時(shí)需要使用貝爾曼-福德算法。

貪心算法

對(duì)于一些比較復(fù)雜的問題，使用一些算法不能簡(jiǎn)單有效地解決，這時(shí)候往往會(huì)使用貪心算法：每步操作都選擇局部最優(yōu)解，最終得到的往往就是全局最優(yōu)解。這似乎是想當(dāng)然的做法，但是很多情況下真的行之有效。當(dāng)然，貪心算法不適用于所有場(chǎng)景，但是他簡(jiǎn)單高效。因?yàn)楹芏嗲闆r并不需要追求完美，只要能找到大致解決問題的辦法就行了。

假如我們面對(duì)這么一個(gè)問題：假設(shè)我開了一家網(wǎng)店，在全國(guó)各省都有生意，現(xiàn)在面臨發(fā)快遞的問題，假設(shè)現(xiàn)在的基礎(chǔ)物流不是很完善，每家快運(yùn)公司只能覆蓋很少幾個(gè)省，那么我該如何在覆蓋全國(guó)34個(gè)省級(jí)行政區(qū)的情況下，選擇最少的快運(yùn)公司？

這個(gè)問題看似不難，其實(shí)很復(fù)雜。

現(xiàn)在假設(shè)有n家快運(yùn)公司，那么全部的組合有2^n種可能。

可以看到，假如有50家快遞公司，我將要考慮1125千億種可能。可以看到，沒有算法能很快的計(jì)算出這個(gè)問題，那么我們可以使用貪心算法，求局部最優(yōu)解，然后將最終得到的視為全局最優(yōu)解。

那么在這個(gè)問題下如何使用貪心算法？核心在于什么是局部最優(yōu)條件？可以這樣：

選擇一家覆蓋了最多未覆蓋省的公司。

重復(fù)第一步。

我們?cè)谶M(jìn)行測(cè)試的時(shí)候稍稍簡(jiǎn)化一下問題，將34個(gè)省改為10個(gè)省。代碼實(shí)現(xiàn)：

1def func(company,province): 2 result = set() 3 province_need=province 4 #當(dāng)存在未覆蓋的省時(shí)，循環(huán)一直繼續(xù) 5 while province_need: 6 best_company=None 7 province_coverd=set() 8 #查找局部最好的選擇 9 for temp_company,temp_province in company.items():10 coverd=province_need & temp_province11 if len(coverd)>len(province_coverd):12 best_company=temp_company13 province_coverd=coverd14 province_need-=province_coverd15 result.add(best_company)16 return result17if __name__ == '__main__':18 province=set(["河北","山西","遼寧","吉林","黑龍江","江蘇","浙江","安徽","福建","江西"])19 company={}20 company["順豐"]=set(["河北","山西","遼寧","江蘇","浙江"])21 company["圓通"]=set(["吉林","浙江"])22 company["中通"]=set(["黑龍江","江西"])23 company["韻達(dá)"]=set(["江蘇","浙江","江蘇"])24 company["EMS"]=set(["浙江","安徽","河北","山西"])25 company["德邦"]=set(["福建","江西","安徽"])26 select_company=func(company,province)27 print(select_company)

輸出結(jié)果：

需要選擇這幾家快遞公司。