《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件 第2章常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用2

第2章工之利器—常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用2.1線性表—數(shù)組2.3字符串2.2線性表—鏈表2.4棧2.5隊(duì)列2.6雙端隊(duì)列2.7優(yōu)先隊(duì)列2.8樹和二叉樹2.9圖2.10并查集2.12哈希表2.11二叉排序樹和平衡二叉樹CONTENTS提綱1/572.9.1圖基礎(chǔ)1.圖的定義2.9圖G=(V，E)143012232(a)一個(gè)帶權(quán)有向圖G1(b)一個(gè)帶權(quán)無(wú)向圖G23385431210143521(c)一個(gè)不帶權(quán)無(wú)向圖G3012342/572.圖的存儲(chǔ)結(jié)構(gòu)1）鄰接矩陣1430122323/572）邊數(shù)組n=4edges=[[0，1，2]，[0，2，4]，[1，2，2]，[2，3，3]，[3，0，1]]1430122324/573）鄰接表用二維數(shù)組adj作為圖的鄰接表，對(duì)于不帶權(quán)圖，adj[i]表示頂點(diǎn)i的所有出邊。adj=[[1，2，3]，[0，2，4]，[0，1，3]，[0，2，4]，[1，3]]012345/57對(duì)于帶權(quán)圖，每一條邊用“[v，w]”表示，如adj[i]中包含該元素時(shí)表示有一條頂點(diǎn)i到頂點(diǎn)v的權(quán)為w的邊。adj=[ [[1,1],[2,5],[3,1]] [[0,1],[2,3],5,2]] [[0,5],[1,3],[3,3],[4,4],[5,3] [[0,1],[2,3],[4,8]] [[2,4],[3,8],[5,1]] [[1,2],[2,3],[4,1]] ]33854312101435216/573.圖的遍歷1）深度優(yōu)先遍歷DFS序列：0，1，2，3，4，533854312101435217/572）廣度優(yōu)先遍歷BFS序列：0，1，2，3，5，433854312101435218/57一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只包含構(gòu)成一棵樹的n-1條邊。一個(gè)帶權(quán)連通圖中權(quán)值和最小的生成樹稱為最小生成樹。Prim算法。Kruskal算法。4.生成樹和最小生成樹9/57對(duì)于帶權(quán)圖中兩個(gè)頂點(diǎn)之間的路徑可能有多條，把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度或者最短距離。Dijkstra算法。Floyd算法。5.最短路徑10/57在一個(gè)有向圖G中找一個(gè)拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判?。如果一個(gè)有向圖拓?fù)渑判虍a(chǎn)生包含全部頂點(diǎn)的拓?fù)湫蛄校瑒t該圖中不存在環(huán)，否則該圖中一定存在環(huán)。6.拓?fù)渑判?1/572.9.2實(shí)戰(zhàn)—課程表（LeetCode207★★）問(wèn)題描述：n門課程（編號(hào)為0到n-1）的選修關(guān)系用prerequisites數(shù)組表示，其中每個(gè)元素[b，a]表示課程a是課程b的先修課程即a→b。判斷是否可能完成所有課程的學(xué)習(xí)。

例如，n=2，prerequisites=[[1，0]]，表示共有2門課程，課程1的先修課程是課程0，這是可能的，結(jié)果為true。

要求設(shè)計(jì)如下方法：

def

canFinish(self,numCourses,prerequisites)

->

bool:12/57每門課程用一個(gè)頂點(diǎn)表示，兩門課程之間的先修關(guān)系用一條有向邊表示，這樣構(gòu)成一個(gè)有向圖，用鄰接表存儲(chǔ)。需要注意的是prerequisites中的元素[b，a]對(duì)應(yīng)的有向邊為<a，b>。采用拓?fù)渑判蛩悸?，用整?shù)n累計(jì)拓?fù)湫蛄兄械脑貍€(gè)數(shù)，拓?fù)渑判蛲戤?，若n=numCourses則說(shuō)明沒(méi)有環(huán)，能夠完成所有課程的學(xué)習(xí)，返回True，否則說(shuō)明存在環(huán)，不能完成所有課程的學(xué)習(xí)，返回False。解13/571 class

Solution:2

def

canFinish(self,numCourses,prerequisites)

->

bool:3

indegree=[0]*numCourses;

#入度數(shù)組4

adj=[[]

for

i

in

range(0,numCourses)]

#鄰接表5

for

e

in

prerequisites:

6

b,a=e[0],e[1]

#[b,a]表示a是b的先修課程7

adj[a].append(b)8

indegree[b]+=1

#存在邊<a,b>，b的入度增1b,…

a[b,a]ab14/579

st=deque()

#定義一個(gè)棧st10

for

i

in

range(0,numCourses):

#入度為0的頂點(diǎn)i進(jìn)棧11

if

indegree[i]==0:st.append(i)12

n=0

#累計(jì)拓?fù)湫蛄械捻旤c(diǎn)個(gè)數(shù)13

while

st:14

i=st.popleft()

#出棧頂點(diǎn)i15

n+=116

for

j

in

adj[i]:

#找到i的所有鄰接點(diǎn)j17

indegree[j]-=1

#頂點(diǎn)j的入度減少118

if

indegree[j]==0:st.append(j)

#入度為0的頂點(diǎn)j進(jìn)棧19

return

n==numCourses上述程序提交結(jié)果為通過(guò)，運(yùn)行時(shí)間為44ms，消耗空間為15.9MB。15/571.并查集的定義給定n個(gè)結(jié)點(diǎn)的集合U，結(jié)點(diǎn)編號(hào)為1～n，再給定一個(gè)等價(jià)關(guān)系R（滿足自反性、對(duì)稱性和傳遞性的關(guān)系稱為等價(jià)關(guān)系。像圖中頂點(diǎn)之間的連通性、親戚關(guān)系等都是等價(jià)關(guān)系），由等價(jià)關(guān)系產(chǎn)生所有結(jié)點(diǎn)的一個(gè)劃分，每個(gè)結(jié)點(diǎn)屬于一個(gè)等價(jià)類，所有等價(jià)類是不相交的。R2.10并查集2.10.1并查集基礎(chǔ)16/57基本運(yùn)算①Init()：初始化。②Find(x)：查找x（x∈U）結(jié)點(diǎn)所屬的等價(jià)類。③Union(x，y)：將x和y（x∈U，y∈U）所屬的兩個(gè)等價(jià)類合并。17/572.并查集的實(shí)現(xiàn)Axy并查集的基本存儲(chǔ)結(jié)構(gòu)self.parent=[0]*self.MAXN

#并查集存儲(chǔ)結(jié)構(gòu)self.rnk=[0]*self.MAXN

#存儲(chǔ)結(jié)點(diǎn)的秩(近似于高度)18/571 def

Init(self,n):

#并查集初始化2

for

i

in

range(0,n):3

self.parent[i]=i4

self.rnk[i]=0i19/571 def

Find(self,x):

#遞歸算法：并查集中查找x結(jié)點(diǎn)的根結(jié)點(diǎn)2

if

x!=self.parent[x]:3

self.parent[x]=self.Find(self.parent[x])

#路徑壓縮4

return

self.parent[x]ABxABx查找中路徑壓縮CC20/571 def

Find(self,x):

#非遞歸算法：并查集中查找x結(jié)點(diǎn)的根結(jié)點(diǎn)2

rx=x3

while

self.parent[rx]!=rx:

#找到x的根rx4

rx=self.parent[rx]5

y=x6

while

y!=rx:

#路徑壓縮7

tmp=self.parent[y]8

self.parent[y]=rx9

y=tmp10

return

rx

#返回根ABxABx查找中路徑壓縮21/571 def

Union(self,x,y):

#并查集中x和y的兩個(gè)集合的合并2

rx,ry=self.Find(x),self.Find(y)3

if

rx==ry:return

#x和y屬于同一棵樹時(shí)返回4

if

self.rnk[rx]<self.rnk[ry]:5

self.parent[rx]=ry

#rx結(jié)點(diǎn)作為ry的孩子6

else:7

if

self.rnk[rx]==self.rnk[ry]:

#秩相同，合并后rx的秩增18

self.rnk[rx]+=19

self.parent[ry]=rx

#ry結(jié)點(diǎn)作為rx的孩子22/572.10.2實(shí)戰(zhàn)—省份數(shù)量（LeetCode547★★）問(wèn)題描述：有n個(gè)城市，其中一些彼此相連，另一些沒(méi)有相連。如果城市a與城市b直接相連，且城市b與城市c直接相連，那么城市a與城市c間接相連。省份是一組直接或間接相連的城市，組內(nèi)不含其他沒(méi)有相連的城市。

給你一個(gè)n×n的矩陣isConnected，其中isConnected[i][j]=1表示第i個(gè)城市和第j個(gè)城市直接相連，而isConnected[i][j]=0

表示二者不直接相連。求矩陣中省份的數(shù)量。

例如，isConnected={{1，1，0}，{1，1，0}，{0，0，1}}，結(jié)果為2。

要求設(shè)計(jì)如下方法：

def

findCircleNum(self,

isConnected)

->

int:23/57城市之間的相連關(guān)系（含直接相連和間接相連）是一種等價(jià)關(guān)系（滿足自反性、對(duì)稱性和傳遞性）。采用并查集求解，按相連關(guān)系劃分產(chǎn)生若干子集樹，每棵子集樹對(duì)應(yīng)一個(gè)省份。首先初始化并查集（這里n個(gè)城市的編號(hào)為0～n-1），由于isConnected是對(duì)稱矩陣，遍歷其上三角部分，對(duì)于直接相連的城市對(duì)（i，j），調(diào)用并查集的合并運(yùn)算Union(i，j)將i和j所在的子集樹合并。最后求并查集中子集樹棵數(shù)（即滿足parent[i]=i的子集樹棵數(shù)）ans，最后返回ans。解24/571 class

UFS(): #并查集類2

MAXN=20053

def

__init__(self):

4

self.parent=[0]*self.MAXN

#并查集存儲(chǔ)結(jié)構(gòu)5

self.rnk=[-1]*self.MAXN;

#存儲(chǔ)結(jié)點(diǎn)的秩(近似于高度)6

def

Init(self,n):

#并查集初始化7

for

i

in

range(0,n):8

self.parent[i]=i9

self.rnk[i]=025/5710

def

Find(self,x):

#遞歸算法：并查集中查找x結(jié)點(diǎn)的根結(jié)點(diǎn)11

if

x!=self.parent[x]:12

self.parent[x]=self.Find(self.parent[x])

#路徑壓縮13

return

self.parent[x]ABxACxCB26/5714

def

Union(self,x,y):

#并查集中x和y的兩個(gè)集合的合并15

rx,ry=self.Find(x),self.Find(y)16

if

rx==ry:

#x和y屬于同一棵樹時(shí)返回17

return18

if

self.rnk[rx]<self.rnk[ry]:19

self.parent[rx]=ry

#rx結(jié)點(diǎn)作為ry的孩子rxxryyrxxryyry的秩不變27/5720

else:21

if

self.rnk[rx]==self.rnk[ry]:

#秩相同，rx的秩增122

self.rnk[rx]+=1ryyrxxryyrxxrx的秩增128/5723

self.parent[ry]=rx

#ry結(jié)點(diǎn)作為rx的孩子24ryyrxxryyrxxrx的秩不變29/5725 class

Solution:26

def

findCircleNum(self,

isConnected)

->

int:27

n=len(isConnected)28

ufs=UFS() #定義并查集類對(duì)象ufs29

ufs.Init(n)30

for

i

in

range(0,n):

#讀取矩陣上三角部分31

for

j

in

range(i+1,n):32

if

isConnected[i][j]==1:ufs.Union(i,j)33

ans=034

for

i

in

range(0,n):35

if

ufs.parent[i]==i:ans+=136

return

ans上述程序提交結(jié)果為通過(guò)，運(yùn)行時(shí)間為48ms，消耗空間為15.4MB。30/572.11.1二叉排序樹1.二叉排序樹的定義2.11二叉排序樹和平衡二叉樹538167中序序列：135678

遞增有序31/572.二叉排序樹的插入和生成3.二叉排序樹的刪除4.二叉排序樹的查找538167查找632/572.11.2平衡二叉樹通過(guò)一些平衡規(guī)則和調(diào)整操作讓一棵二叉排序樹既保持BST性質(zhì)又保證高度較小，即接近O(log2n)的高度，稱為平衡二叉樹。平衡二叉樹：AVL樹和紅黑樹。AVL樹的平衡規(guī)則是樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差1。33/57紅黑樹中每個(gè)結(jié)點(diǎn)有一個(gè)表示顏色的標(biāo)志，增加外部結(jié)點(diǎn)（通常用NIL表示），同時(shí)滿足以下性質(zhì)：

（1）每個(gè)結(jié)點(diǎn)的顏色為紅色或者黑色。

（2）根結(jié)點(diǎn)的顏色為黑色。

（3）所有外部結(jié)點(diǎn)的顏色為黑色。

（4）如果一個(gè)結(jié)點(diǎn)是紅色，則它的所有孩子結(jié)點(diǎn)為黑色。

（5）對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)出發(fā)的所有路徑上包含相同個(gè)數(shù)的黑色結(jié)點(diǎn)。這里的路徑特指從一個(gè)結(jié)點(diǎn)到其子孫結(jié)點(diǎn)中某個(gè)外部結(jié)點(diǎn)的路徑。盡管紅黑樹并不是完全平衡二叉樹，但接近于平衡狀態(tài)即近似于平衡二叉樹，其高度接近O(log2n)。2.11.3紅黑樹34/572.11.4Python中的有序類目前Python中沒(méi)有提供類似于C++中set和map（均采用紅黑樹實(shí)現(xiàn)）的數(shù)據(jù)結(jié)構(gòu)，但有一個(gè)第三方拓展庫(kù)sortedcontainers，它是用pure-python實(shí)現(xiàn)的，內(nèi)有SortedList（有序列表）、SortedDict（有序字典）和SortedSet（有序集合）等，默認(rèn)按關(guān)鍵字遞增排列。SortedList用于存儲(chǔ)一個(gè)含重復(fù)元素的有序序列，采用平衡樹實(shí)現(xiàn)，查找性能較好。其使用方式與列表類似。35/57tset.add(val)：添加新元素并排序。tset.update(iterable)：對(duì)添加的可迭代的所有元素排序。tset.clear()：移除所有元素。tset.discard(val)：移除一個(gè)值元素，如果元素不存在時(shí)不報(bào)錯(cuò)。時(shí)間復(fù)雜度為O(log2n)。tset.remove(val)：移除一個(gè)值元素，如果元素不存在則報(bào)錯(cuò)。時(shí)間復(fù)雜度為O(log2n)。例如定義一個(gè)空的有序列表tset：tset=SortedList()36/57tset.pop(i=-1)：移除一個(gè)指定下標(biāo)i的元素，如果有序序列為空或者下標(biāo)超限會(huì)報(bào)錯(cuò)。時(shí)間復(fù)雜度為O(log2n)。tset.bisect_left(val)：查找第一個(gè)大于等于val的索引。時(shí)間復(fù)雜度為O(log2n)。tset.bisect_right(val)：查找第一個(gè)大于val的索引。時(shí)間復(fù)雜度為O(log2n)。count(val)：返回有序列表中值val出現(xiàn)的次數(shù)。tset.index(val,start=None,Stop=None)：查找索引范圍[start，stop）范圍內(nèi)第一次出現(xiàn)val的索引，如果val不存在則報(bào)錯(cuò)。時(shí)間復(fù)雜度為O(log2n)。37/572.11.5實(shí)戰(zhàn)—前k個(gè)高頻詞（LeetCode692★★）問(wèn)題描述：給一非空的單詞列表words，返回前k個(gè)出現(xiàn)次數(shù)最多的單詞。返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率，按字母順序排序。

例如，words={"i"，"love"，"leetcode"，"i"，"love"，"coding"}，k=2，則返回結(jié)果是{"i"，"love"}，"i"和"love"為出現(xiàn)次數(shù)最多的兩個(gè)單詞，均為2次，但按字母順序"i"在"love"之前。

要求設(shè)計(jì)如下方法：def

topKFrequent(self,

words,

k)

->

List[str]:38/57先定義一個(gè)一個(gè)SortedDict對(duì)象cntmap，以單詞為關(guān)鍵字，遍歷words得到每個(gè)單詞的計(jì)數(shù)。再定義一個(gè)SortedDict對(duì)象ansmap，以計(jì)數(shù)為關(guān)鍵字，其值為該計(jì)數(shù)的單詞列表（按字母順序排列）。ansmap默認(rèn)按計(jì)數(shù)遞增排序，ansmap.key()[-1]是計(jì)數(shù)最大的元素。定義一個(gè)存放結(jié)果的ans列表，取出ansmap中前k個(gè)單詞添加到ans中，最后返回ans。解39/571 from

sortedcontainers

import

SortedDict #引入SortedDict類2 class

Solution:3

def

topKFrequent(self,

words,

k)

->

List[str]:4

cntmap=SortedDict()5

for

i

in

range(0,len(words)):

#單詞計(jì)數(shù)存放在cntmap中6

if

words[i]

in

cntmap:cntmap[words[i]]+=17

else:cntmap[words[i]]=1words={"i"，"love"，"leetcode"，"i"，"love"，"coding"}，k=2cntmap：("coding",1)("i",2)("leetcode",1)("love",2)40/578

ansmap=SortedDict()9

for

s

in

cntmap.keys():10

cnt=cntmap[s]

#獲取s對(duì)應(yīng)的計(jì)數(shù)11

if

cnt

in

ansmap:

#ansmap中存在該計(jì)數(shù)12

ss=ansmap[cnt]13

ss.append(s)14

ansmap[cnt]=ss15

else:

#ansmap中不存在該計(jì)數(shù)16

ss=[]

17

ss.append(s)18

ansmap[cnt]=sscntmap：("coding",1)("i",2)("leetcode",1)("love",2)ansmap:(2,["i","love"])(1,["coding","leetcode"])41/5719

ans=[]20

i=-1

#在ansmap中從后向前查找21

while

k>0:

#取前k個(gè)字符串存放在ans中22

cnt=ansmap.keys()[i]23

ss=ansmap[cnt]24

for

x

in

ss:25

if

k>0:ans.append(x);k-=126

else:break27

i-=128

return

ansansmap:(2,["i","llove"])(1,["coding","leetcode"])ans={"i"，"love"}k=242/57上述程序提交結(jié)果為通過(guò)，運(yùn)行時(shí)間為44ms，消耗空間為15.6MB。43/572.12.1哈希表基礎(chǔ)2.12哈希表哈希表是一種使用哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)地址的數(shù)據(jù)結(jié)構(gòu)。哈希函數(shù)h存儲(chǔ)地址=h(key)n個(gè)元素（對(duì)象）m（m≥n）的連續(xù)內(nèi)存單元44/571）直接定址法h(k)=k+c2）除留余數(shù)法h(k)=kmodp

（mod為求余運(yùn)算，p≤m）構(gòu)造哈希函數(shù)的方法45/57開放定址法拉鏈法哈希沖突解決方法46/572.12.2Python中的哈希表1.Python中的哈希集合Python中提供了集合類型，采用哈希表實(shí)現(xiàn)，集合中存放不可變類型數(shù)據(jù)，如字符串、數(shù)字或元組。集合是一個(gè)無(wú)序的不重復(fù)元素序列，其基本功能包括關(guān)系測(cè)試和消除重復(fù)元素。使用大括號(hào){}或者set()函數(shù)創(chuàng)建集合，而創(chuàng)建一個(gè)空集合必須用set()而不是{}，因?yàn)閧}是用來(lái)創(chuàng)建一個(gè)空字典。47/57集合s的主要操作如下。①len(s)：返回集合s中的元素個(gè)數(shù)。②eins，enotins：分別判定元素e是否在或者不在集合s中。③s.add(e)：向集合s中添加元素e。④s.clear()：移除集合s中的所有元素。⑤s.issubs(t)：判斷集合s是否為集合t的子集。⑥s.remove(e)：移除集合s的元素e，如果元素e不存在，則會(huì)發(fā)生錯(cuò)誤。⑦s.discard(e)：移除集合s的元素e，如果元素e不存在，不會(huì)發(fā)生錯(cuò)誤。⑧s.difference(t)，ersection(t)和s.union(t)：分別返回集合s和t的差集、交集和并集。48/571 hset=set() #定義一個(gè)哈希集合hset2 hset.add(3) #插入33 hset.add(1) #插入24 hset.add(2) #插入25 print(1inhset) #輸出:True6 hset.remove(1) #刪除17 forxinhset: #輸出:238 print(x,end='')9 print()49/572.Python中的哈希映射Python中提供的字典類型相當(dāng)于哈希映射，也是采用哈希表實(shí)現(xiàn)。字典可存儲(chǔ)任意類型對(duì)象，每個(gè)元素由key:value構(gòu)成，其中key是鍵，value是對(duì)應(yīng)的值，中間用逗號(hào)分隔，整個(gè)字典包括在花括號(hào)({})中，鍵必須是唯一的，但值則不必唯一。使用大括號(hào){}或者dict()函數(shù)創(chuàng)建字典。50/57字典dict的主要操作如下：①len(dict)：返回字典dict中的元素個(gè)數(shù)。②dict[key]：返回字典dict中鍵key的值。③keyindict,keynotindict：分別判定鍵key在或者不在字典dict中。④dict.items()：以列表返回字典dict中可遍歷的（鍵鍵,值）元組數(shù)組。⑤dict.keys()：以列表返回字典dict中所有的鍵。⑥dict.values()：以列表返回字典dict中的所有值。⑦pop(key[,default])：刪除字典dict中鍵key所對(duì)應(yīng)的值，返回值為被刪除的值。key值必須給出，否則返回default值。51/571 hmap=dict() #定義一個(gè)哈希字典hmap2 hmap["Mary"]=3 #插入("Mary