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

第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二叉排序樹和平衡二叉樹1/83CONTENTS提綱2/832.1線性表—數(shù)組2.1.1線性表的定義線性表是性質(zhì)相同的n（n≥0）個(gè)元素的有限序列。每個(gè)元素有唯一的序號(hào)或者位置，也稱為下標(biāo)或者索引，通常下標(biāo)是介于0到n-1之間。線性表中的n個(gè)元素從頭到尾分別稱為第0個(gè)元素，第1個(gè)元素，依此類推。3/832.1.2Python列表Python中數(shù)組對(duì)應(yīng)列表類型，Python列表的基本形式是一個(gè)方括號(hào)內(nèi)以逗號(hào)分隔的若干值，列表的值不需要具有相同的類型?？梢杂昧斜泶鎯?chǔ)線性表。例如，列表a=[2，5，3，1，4]看成一維數(shù)組，列表b=[[2，3，8]，[5，3，4]]看成二維數(shù)組。4/831）訪問列表中的值2）列表腳本操作符3）列表的函數(shù)4）列表的方法5/83【例2-1】（LeetCode215—數(shù)組中的第k個(gè)最大元素★★）給定一個(gè)含n個(gè)整數(shù)的數(shù)組nums和整數(shù)k（1≤k≤n），請(qǐng)返回?cái)?shù)組中第k個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第k個(gè)最大的元素，而不是第k個(gè)不同的元素。

例如，nums=[3，2，3，1，2，4，5，5，6]，k=4，答案為4。6/83解法1nums遞增排序

排序后的nums[n-k]就是原來nums中第k大的整數(shù)。1 class

Solution:2

def

findKthLargest(self，

nums:List[int]，k:int)

->

int:3

n=len(nums)4

nums.sort()5

return

nums[n-k]例如，nums=[6，1，2，2，3，4，5]，n=7序號(hào)：

0，1，2，3，4，5，6遞增排序： 1，2，2，3，4，5，6k：

7，6，5，4，3，2，17/83nums遞減排序

排序后的nums[k-1]就是原來nums中第k大的整數(shù)。1 class

Solution:2

def

findKthLargest(self，nums:List[int]，k:int)

->

int:3

nums.sort(reverse=True)4

return

nums[k-1]解法2例如，nums=[6，1，2，2，3，4，5]，n=7序號(hào)：

0，1，2，3，4，5，6遞減排序： 6，5，4，3，2，2，1k：

1，2，3，4，5，6，78/832.1.3列表元素排序用列表的方法list.sort()或者序列類型函數(shù)sorted(list)進(jìn)行排序。討論前者。list.sort(func=None,key=None,reverse=False)

1 list=[2,5,8,9,3]2 list.sort()#升序排序3 print(list) #輸出：[2,3,5,8,9]4 list.sort(reverse=True) #降序排序5 print(list) #輸出：[9,8,5,3,2]9/83對(duì)于多關(guān)鍵字排序，key可以使用operator模塊提供的itemgetter函數(shù)獲取對(duì)象的哪些維的數(shù)據(jù)實(shí)現(xiàn)排序。1 fromoperatorimportitemgetter,attrgetter #導(dǎo)入operator模塊2 list=[('b',3),('a',1),('c',3),('a',4)]3 list.sort(key=itemgetter(1),reverse=True) #對(duì)第二個(gè)關(guān)鍵字降序排序4 print(list) #輸出：[('a',4),('b',3),('c',3),('a',1)]5 list.sort(key=itemgetter(0,1),reverse=True) #第一二關(guān)鍵字降序排序6 print(list) #輸出：[('c',3),('b',3),('a',4),('a',1)]7 list.sort(key=lambdax:x[0]) #對(duì)第一個(gè)關(guān)鍵字升序排序8 print(list) #輸出：[('a',4),('a',1),('b',3),('c',3)]9 list.sort(key=lambdax:(x[0],-x[1])) #對(duì)第一序,第二降序排序10 print(list) #輸出：[('a',4),('a',1),('b',3),('c',3)]10/83可以制定自定義的比較規(guī)則1 importfunctools2 stud=[[3,"Mary"],[1,"Smith"],[2,"John"]] #學(xué)生列表3 defcmp1(a,b): #自定義比較函數(shù)14 returna[0]-b[0] #按學(xué)號(hào)遞增排序5 print(stud) #輸出:[[3,'Mary'],[1,'Smith'],[2,'John']]6 stud.sort(key=functools.cmp_to_key(cmp1))7 print(stud) #輸出:[[1,'Smith'],[2,'John'],[3,'Mary']]8 defcmp2(a,b): #自定義比較函數(shù)29 ifa[1]<b[1]:return1 #按姓名遞減排序10 elifa[1]==b[1]:return011 else:return-112 stud.sort(key=functools.cmp_to_key(cmp2))13 print(stud) #輸出:[[1,'Smith'],[3,'Mary'],[2,'John']]11/832.1.4列表的拷貝1 a=[1,2,3]2 b=a3 print(a) #輸出：[1,2,3]4 a[0]=45 print(a) #輸出：[4,2,3]6 print(b) #輸出：[4,2,3]7 b[1]=58 print(a) #輸出：[4,5,3]9 print(b) #輸出：[4,5,3]1.非拷貝方法—直接賦值12/831 importcopy #導(dǎo)入copy模塊2 a=[1,[1,2,3],4]3 b=copy.deepcopy(a)4 print(a) #輸出：[1,[1,2,3],4]5 print(b) #輸出：[1,[1,2,3],4]6 b[0]=37 b[1][0]=38 print(a) #輸出：[1,[1,2,3],4]9 print(b) #輸出：[3,[3,2,3],4]2.列表的深拷貝13/831 a=[1,[1,2,3],4]2 b=a.copy()3 print(a) #輸出：[1,[1,2,3],4]4 print(b) #輸出：[1,[1,2,3],4]5 b[0]=36 b[1][0]=37 print(a) #輸出：[1,[3,2,3],4]8 print(b) #輸出：[3,[3,2,3],4]3.列表的淺拷貝14/832.1.5實(shí)戰(zhàn)—移除元素（LeetCode27★）問題描述：給定一個(gè)數(shù)組nums和一個(gè)值val，需要原地移除所有等于val的元素，并返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間（即算法的空間復(fù)雜度為O(1)），元素的順序可以改變。

例如，nums={3，1，2，3}，val=3，返回值為2，nums中前面2個(gè)元素為{1，2，*，*}。

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

def

removeElement(self,nums:List[int],val:int)->int:15/83解法1：整體建表法。用nums存放刪除所有val元素的結(jié)果，先將結(jié)果數(shù)組nums看成是一個(gè)空表，用k表示結(jié)果數(shù)組的元素個(gè)數(shù)（初始為0），用i遍歷nums，遇到保留元素（不等于val）時(shí)重新插入到結(jié)果數(shù)組nums中，遇到val元素時(shí)跳過。最后返回k。numsnums16/831 class

Solution:2 def

removeElement(self,nums:List[int],val:int)->int:3

n=len(nums)4

k,i=0,0

#k記錄結(jié)果數(shù)組中的元素個(gè)數(shù)5

while

i<n:6

if

nums[i]!=val:

#nums[i]是保留的元素7

nums[k]=nums[i];

#將nums[i]重新插入到結(jié)果數(shù)組中8

k+=1

#結(jié)果數(shù)組的長(zhǎng)度增19

i+=110

return

k

#返回保留的元素個(gè)數(shù)17/83解法2：移動(dòng)法。同樣用nums存放刪除所有val元素的結(jié)果，先將結(jié)果數(shù)組看成是整個(gè)表，用k表示要?jiǎng)h除的元素個(gè)數(shù)（初始為0），用i遍歷nums：①遇到保留元素（不等于val）時(shí)將nums[i]前移k個(gè)位置。②遇到val元素時(shí)將k增1。遍歷完畢返回結(jié)果數(shù)組的長(zhǎng)度n-k。18/831 class

Solution:2

def

removeElement(self,nums:List[int],val:int)->int:3

n=len(nums)4

k,i=0,0

#k記錄結(jié)果數(shù)組中的元素個(gè)數(shù)5

while

i<n:6

if

nums[i]!=val:

#nums[i]是保留的元素7

nums[i-k]=nums[i]

#將nums[i]前移k個(gè)位置8

else:

#nums[i]是要?jiǎng)h除的元素9

k+=1

#k增110

i+=111

return

n-k

#返回結(jié)果數(shù)組的長(zhǎng)度n-k19/83解法3：區(qū)間劃分法。用v[0..k]（共k+1個(gè)元素）表示保留的元素區(qū)間（即不為val區(qū)間），初始時(shí)保留區(qū)間為空，所以置k=-1。v[k+1..i-1]（共i-k-1個(gè)元素）表示刪除元素區(qū)間（即為val的區(qū)間），i從0開始遍歷v，初始時(shí)刪除區(qū)間也為空。

vi

…

vn-1保留區(qū)間v0…

vkvk+1

…

vi-1刪除區(qū)間20/83

①若v[i]≠val，將其通過交換添加到保留區(qū)間的末尾，再執(zhí)行i++繼續(xù)遍歷。

vi

…

vn-1保留區(qū)間v0…

vkvk+1

…

vi-1刪除區(qū)間

②若v[i]=val，只需要執(zhí)行i++擴(kuò)大刪除區(qū)間，再繼續(xù)遍歷。

vi

…

vn-1保留區(qū)間v0…

vkvk+1

…

vi-1刪除區(qū)間最后的結(jié)果v中僅保留所有不為val區(qū)間的k+1個(gè)元素，返回k+1即可。21/831 class

Solution:2

def

removeElement(self,nums:List[int],val:int)->int:3

n=len(nums)4

k,i=-1,0

#k記錄結(jié)果數(shù)組中的元素個(gè)數(shù)5

while

i<n:6

if

nums[i]!=val:

#nums[i]是保留的元素7

k+=1

#擴(kuò)大保留元素區(qū)間8

nums[k],nums[i]=nums[i],nums[k]

#交換9

i+=110

return

k+1

#返回結(jié)果數(shù)組的長(zhǎng)度k+122/83上述3個(gè)算法的時(shí)間復(fù)雜度均為O(n)，空間復(fù)雜度均為O(1)，都屬于高效的算法。提交時(shí)運(yùn)行時(shí)間均為4ms左右。結(jié)果23/832.2線性表—鏈表2.2.1單鏈表定義一個(gè)整數(shù)單鏈表的結(jié)點(diǎn)類如下：1

class

ListNode: #單鏈表結(jié)點(diǎn)類2 def

__init__(self,

x):3 self.val=x #數(shù)據(jù)域4 self.next=None #指針域24/83……一個(gè)帶頭結(jié)點(diǎn)的單鏈表head首結(jié)點(diǎn)尾結(jié)點(diǎn)頭結(jié)點(diǎn)

a0an-1∧a1head結(jié)點(diǎn)序號(hào)01n-125/83問題描述：給定一個(gè)不帶頭結(jié)點(diǎn)的單鏈表head，將其反轉(zhuǎn)，并返回反轉(zhuǎn)后的鏈表。例如，head=（1，2，3，4），返回結(jié)果為（4，3，2，1）。要求設(shè)計(jì)如下方法：def

reverseList(self,

head:

Optional[ListNode]):實(shí)戰(zhàn)—反轉(zhuǎn)鏈表（LeetCode206★）26/83問題求解：先創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空單鏈表h，用p遍歷head，采用頭插法將結(jié)點(diǎn)p插入到表頭。最后返回h.next即可。a0heada1a2…a0pa1a2…∧h27/831 class

Solution:2

def

reverseList(self,

head:

Optional[ListNode]):3

h=ListNode()

#建立一個(gè)頭結(jié)點(diǎn)h4

p=head5

while

p!=None:6

q=p.next7

p.next=h.next

#結(jié)點(diǎn)p插入到表頭8

h.next=p9

p=q10

return

h.next上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為36ms，消耗空間為16MB。28/832.3字符串2.3.1字符串的定義字符串簡(jiǎn)稱為串，是字符的有限序列，可以看成元素類型是字符的線性表。一個(gè)串s中若干連續(xù)的字符構(gòu)成的串t稱為s的子串?？沾侨魏未淖哟?。兩個(gè)串相等當(dāng)且僅當(dāng)它們的長(zhǎng)度相同并且對(duì)應(yīng)位置的字符均相同。字符串主要有數(shù)組和鏈串兩種存儲(chǔ)結(jié)構(gòu)。29/832.3.2Python中的字符串Python中使用單引號(hào)或者雙引號(hào)來創(chuàng)建字符串，Python不支持單字符類型，單字符在Python中也是作為一個(gè)字符串使用。1）字符串運(yùn)算符2）字符串方法①string.count(str,beg=0,end=len(string))②string.find(str,beg=0,end=len(string))③string.rfind(str,beg=0,end=len(string))④string.index(str,beg=0,end=len(string))…30/832.3.3實(shí)戰(zhàn)—最大重復(fù)子字符串（LeetCode1668★）問題描述：給你一個(gè)字符串sequence，如果字符串word連續(xù)重復(fù)k次形成的字符串是sequence的一個(gè)子串，那么單詞word的重復(fù)值為k。

單詞word的最大重復(fù)值是單詞word在sequence中最大的重復(fù)值。如果word不是sequence的子串，那么重復(fù)值k為0。設(shè)計(jì)一個(gè)算法返回最大重復(fù)值k。

例如sequence="ababc"，word="ab"，返回結(jié)果為2。要求設(shè)計(jì)如下方法：

def

maxRepeating(self,sequence:str,word:

str)->int31/83問題求解：k從1開始，構(gòu)造由word連續(xù)重復(fù)k次形成的字符串subs，若subs是sequence的子串，置k++，subs+=word，然后繼續(xù)循環(huán)判斷，否則退出循環(huán)，最后返回k-1。sequence="ababc"，word="ab"。subs=word,k=1（1）subs是sequence的子串

subs+=word,k=2（2）subs是sequence的子串

subs+=word,k=3（3）subs不是sequence的子串，返回k-1=2。32/831 class

Solution:2

def

maxRepeating(self,sequence:str,word:

str)->int:3

n,m=len(sequence),len(word)4

k=15

subs=word6

while

m*k<=n:7

if

sequence.find(subs)!=-1:8

k+=19

subs+=word10

else:break11

return

k-133/832.4棧2.4.1棧的定義棧是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，規(guī)定只能在其中一端進(jìn)行進(jìn)棧和出棧操作，該端點(diǎn)稱為棧頂，另外一個(gè)端點(diǎn)稱為棧底。棧的主要運(yùn)算有判斷?？?、進(jìn)棧、出棧和取棧頂元素等。棧具有后進(jìn)先出的特點(diǎn)34/832.4.2用Python列表實(shí)現(xiàn)棧Python中沒有提供專門的棧數(shù)據(jù)類型，由于列表具有在末尾插入和刪除元素的時(shí)間為O(1)的特性，可以用列表實(shí)現(xiàn)棧。定義一個(gè)空棧st：st=[]35/83st棧的主要操作及其說明如下：①st，len(st)==0：判斷棧是否為空。②len(st)：返回棧的長(zhǎng)度。③st.append(e)：進(jìn)棧元素e。④st[-1]：返回棧頂元素。⑤st.pop()：移除棧頂元素。36/831 st=[] #用列表作為棧st2 st.append(1)3 st.append(2)4 st.append(3)5 st.append(4)6 whilest: #棧不空循環(huán)7 print("棧頂元素:",st[-1])#依次輸出43218 print("出棧")9 st.pop()37/832.4.3實(shí)戰(zhàn)—使括號(hào)有效的最少添加（LeetCode921★★）

問題描述：給定一個(gè)由

'('

和

')'

括號(hào)組成的字符串

S，需要添加最少的括號(hào)（

'('

或是

')'，可以在任何位置），以使得到的括號(hào)字符串有效。

設(shè)計(jì)一個(gè)算法求為使結(jié)果字符串有效而必須添加的最少括號(hào)數(shù)。

例如，s="())"，結(jié)果為1s="(())"。要求設(shè)計(jì)如下方法：def

minAddToMakeValid(self,

s:

str)

->

int:38/83定義一個(gè)棧st。遍歷字符串s：遇到'('時(shí)進(jìn)棧。遇到')'時(shí)：若棧不空并且棧頂為'('，說明這一對(duì)括號(hào)是匹配的，將棧頂'('退棧。否則說明該')'是不匹配的，需要添加一個(gè)'('，將其進(jìn)棧。遍歷結(jié)束后，棧中每個(gè)'('需要添加一個(gè)')'，每個(gè)')'需要添加一個(gè)'('，這是使得括號(hào)字符串s匹配需要添加的最少括號(hào)個(gè)數(shù)，返回st的長(zhǎng)度即可。解39/831 class

Solution:2

def

minAddToMakeValid(self,

s:

str)

->

int:3

st=[]

#用列表作為棧4

for

ch

in

s:5

if

ch=='(':

#遇到'('6

st.append(ch)7

else:

#遇到')'8

if

st

and

st[-1]=='(':

9

st.pop()10

else:

#?？栈蛘卟黄ヅ涞?)'進(jìn)棧11

st.append(ch)12

return

len(st)上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為28ms，消耗空間為14.8MB。40/832.5雙端隊(duì)列2.5.1雙端隊(duì)列的定義前端后端前端進(jìn)前端出后端進(jìn)后端出雙端隊(duì)列是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，每個(gè)端點(diǎn)都可以進(jìn)隊(duì)和出隊(duì)元素。41/832.5.2Python中的雙端隊(duì)列dequedeque是Python標(biāo)準(zhǔn)庫(kù)collections中的一個(gè)類，實(shí)現(xiàn)了兩端都可以操作的隊(duì)列即雙端隊(duì)列，與Python的列表相似。定義一個(gè)空的deque對(duì)象dq：dq=deque()42/83dq的主要操作及其說明如下：①dq，len(dq)==0：判斷隊(duì)列是否為空。②len(dq)：返回隊(duì)列的長(zhǎng)度。③dq.clear()：清除雙端隊(duì)列中的所有元素。④dq[0]：返回雙端隊(duì)列中左端（前端）的元素。⑤dq[-1]：返回雙端隊(duì)列中右端（后端）的元素。⑥dq.appendleft(e)：從雙端隊(duì)列的左端（前端）進(jìn)隊(duì)元素e。⑦dq.popleft()：從雙端隊(duì)列的左端（前端）出隊(duì)元素。⑧dq.append(e)：從雙端隊(duì)列的右端（后端）進(jìn)隊(duì)元素e。⑨dq.pop()：從雙端隊(duì)列的右端（后端）出隊(duì)元素。43/831 fromcollectionsimportdeque #引用deque類2 dq=deque()3 dq.append(1)4 dq.appendleft(2)5 dq.append(3)6 dq.appendleft(4)7 print("右端:",dq[-1]) #輸出:38 whiledq:9 print("左端:",dq[0]) #依次輸出421310 print("左端出隊(duì)")11 dq.popleft()44/83nums:[4，3，5]，4，3，3，6，7

5nums:4，[3，5，4]，3，3，6，7

5nums:4，3，[5，4，3]，3，6，7

5nums:4，3，5，[4，3，3]，6，7

4nums:4，3，5，4，[3，3，6]，7

6nums:4，3，5，4，3，[3，6，7]

7結(jié)果是（5，5，5，4，6，7）共n-k+1個(gè)滑動(dòng)窗口2.5.3實(shí)戰(zhàn)—滑動(dòng)窗口最大值(LeetCode239★★★)問題描述：給定一個(gè)含n個(gè)整數(shù)的數(shù)組nums和一個(gè)整數(shù)k（1≤k≤n），一個(gè)大小為k的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)，每次只能看到滑動(dòng)窗口內(nèi)的k個(gè)整數(shù)?；瑒?dòng)窗口每次向右移動(dòng)一位。設(shè)計(jì)一個(gè)算法返回滑動(dòng)窗口中的最大值。

例如，n=8，nums=（4，3，5，4，3，3，6，7），k=3，最終返回結(jié)果是（5，5，5，4，6，7）。45/83解append隊(duì)頭dq[0]隊(duì)尾dq[-1]popleft前端大，保持前端元素為當(dāng)前滑動(dòng)窗口的最大元素。處理nums[i]：將隊(duì)尾小于nums[i]的所有元素從隊(duì)尾元素出隊(duì)，再將nums[i]從隊(duì)尾進(jìn)隊(duì)。隊(duì)頭過期的元素從隊(duì)頭出隊(duì)，為此nums[i]進(jìn)隊(duì)時(shí)改為求序號(hào)i進(jìn)隊(duì)。本題f

s

…

i

kdq[0]前端過期：i-dq[0]≥k

46/83nums:隊(duì)頭隊(duì)尾0[4]1[3]2[5]3[4]4[3]5[3]6[6]7[7]k=3

ans：555467結(jié)果是（5，5，5，4，6，7）47/831 class

Solution:2

def

maxSlidingWindow(self,

nums,

k)

->

List[int]:3

n=len(nums)4

dq=deque()

#定義一個(gè)雙端隊(duì)列dq5

ans=[]6

for

i

in

range(0,n):

#處理nums中剩余的元素7

while

len(dq)>0

and

nums[i]>nums[dq[-1]]:8

dq.pop()

#將隊(duì)尾小于nums[i]者從隊(duì)尾出隊(duì)9

dq.append(i)

#將元素下標(biāo)i進(jìn)隊(duì)尾10

if

i-dq[0]>=k:

#將隊(duì)頭過期的元素從隊(duì)頭出隊(duì)11

dq.popleft()12

if

i>=k-1:

#i>=k-1時(shí)每個(gè)位置對(duì)應(yīng)一個(gè)窗口13

ans.append(nums[dq[0]])

#新隊(duì)頭元素添加到ans中14

return

ans48/83上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為365ms，消耗空間為28.9MB。49/832.6隊(duì)列2.6.1隊(duì)列的定義隊(duì)列是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，規(guī)定只能在一端進(jìn)隊(duì)元素，另外一端出隊(duì)元素。隊(duì)列的主要運(yùn)算有判斷隊(duì)空、進(jìn)隊(duì)、出隊(duì)和取隊(duì)頭元素等。隊(duì)列具有先進(jìn)先出的特點(diǎn)。50/832.6.2Python中的隊(duì)列Python中沒有提供專門的隊(duì)列數(shù)據(jù)類型，通常用雙端隊(duì)列deque作為隊(duì)列，即通過限制操作將雙端隊(duì)列dq作為隊(duì)列。進(jìn)隊(duì)和出隊(duì)操作僅使用append()/popleft()，如圖(a)所示。進(jìn)隊(duì)和出隊(duì)操作僅使用appendleft()/pop()，如圖(b)所示。隊(duì)頭dq[0]隊(duì)尾dq[-1]popleft()append()(a)隊(duì)列一pop()appendleft()隊(duì)尾dq[0]隊(duì)頭dq[-1](b)隊(duì)列二51/83實(shí)際上還可以通過限制操作將雙端隊(duì)列dq作為棧。dq進(jìn)隊(duì)和出隊(duì)操作僅僅使用append()/pop()，如圖(a)所示。dq進(jìn)隊(duì)和出隊(duì)操作僅僅使用appendleft()/popleft()，如圖(b)所示。棧底dq[0]棧頂dq[-1]append()(a)棧一pop()appendleft()popleft()棧頂dq[0]棧底dq[-1](b)棧二52/832.6.3實(shí)戰(zhàn)—無(wú)法吃午餐的學(xué)生數(shù)量(LeetCode1700★)問題描述：學(xué)校的自助午餐提供圓形和方形的三明治，分別用數(shù)字0和1表示。所有學(xué)生站在一個(gè)隊(duì)列里，每個(gè)學(xué)生要么喜歡圓形的要么喜歡方形的。餐廳里三明治的數(shù)量與學(xué)生的數(shù)量相同。

所有三明治都放在一個(gè)棧里，每一輪：如果隊(duì)列最前面的學(xué)生喜歡棧頂?shù)娜髦危敲磿?huì)拿走它并離開隊(duì)列，否則這名學(xué)生會(huì)放棄這個(gè)三明治并回到隊(duì)列的尾部。這個(gè)過程會(huì)一直持續(xù)到隊(duì)列里所有學(xué)生都不喜歡棧頂?shù)娜髦螢橹埂?3/83給定兩個(gè)整數(shù)數(shù)組students和sandwiches（兩個(gè)數(shù)組的長(zhǎng)度相同），其中sandwiches[i]是棧里面第i??個(gè)三明治的類型（i=0是棧的頂部），students[j]是初始隊(duì)列里第j名學(xué)生對(duì)三明治的喜好（j=0是隊(duì)列的最開始位置）。設(shè)計(jì)一個(gè)算法求無(wú)法吃午餐的學(xué)生數(shù)量。54/83例如students=[1，1，1，0，0，1]，sandwiches=[1，0，0，0，1，1]，n=6，過程如下：

（1）students[0]=sandwiches[0]，拿走三明治并離開隊(duì)列，問題轉(zhuǎn)換為n=5，students=[1，1，0，0，1]，sandwiches=[0，0，0，1，1]。

（2）students[0]≠sandwiches[0]，students[0]回到隊(duì)列的尾部，問題轉(zhuǎn)換為n=5，students=[1，0，0，1，1]，sandwiches=[0，0，0，1，1]。

（3）students[0]≠sandwiches[0]，students[0]回到隊(duì)列的尾部，問題轉(zhuǎn)換為n=5，students=[0，0，1，1，1]，sandwiches=[0，0，0，1，1]。

（4）students[0]=sandwiches[0]，拿走三明治并離開隊(duì)列，問題轉(zhuǎn)換為n=4，students=[0，1，1，1]，sandwiches=[0，0，1，1]。

（5）students[0]=sandwiches[0]，拿走三明治并離開隊(duì)列，問題轉(zhuǎn)換為n=3，students=[1，1，1]，sandwiches=[0，1，1]。

顯然后面不可能拿走三明治，所以無(wú)法吃午餐的學(xué)生數(shù)量為3。55/83要求設(shè)計(jì)如下方法：

def

countStudents(self,students,sandwiches)->int:56/83利用隊(duì)列和棧模擬整個(gè)過程，定義一個(gè)隊(duì)列qu作為學(xué)生隊(duì)列，定義一個(gè)棧st作為三明治棧，用n表示初始學(xué)生人數(shù)。如果st[-1]==qu[0]，子問題人數(shù)n減少1；否則執(zhí)行tmp=qu.popleft()，qu.append(tmp)問題的關(guān)鍵是如何確定循環(huán)結(jié)束的條件：用i累計(jì)子問題的該操作次數(shù)（初始為n），當(dāng)i=0時(shí)循環(huán)結(jié)束，此時(shí)st棧中元素個(gè)數(shù)就是無(wú)法吃午餐的學(xué)生數(shù)量。解57/831 class

Solution:2

def

countStudents(self,students,sandwiches)->int:3

n=len(students)4

qu=deque()

#定義一個(gè)隊(duì)列qu5

st=deque()

#定義一個(gè)棧st6

for

x

in

students:

#建立學(xué)生隊(duì)列7

qu.append(x)8

for

i

in

range(n-1,-1,-1):

#建立三明治棧9

st.append(sandwiches[i])棧底dq[0]棧頂dq[-1]append()棧pop()popleft()隊(duì)頭dq[0]隊(duì)尾dq[-1]append()隊(duì)列58/8310

i=n #n記錄本輪的學(xué)生人數(shù)11

while

i>0:12

if

st[-1]==qu[0]:

#隊(duì)列最前面學(xué)生喜歡棧頂三明治13

st.pop();qu.popleft()14

n-=1

#子問題的人數(shù)減少115

i=n

#重置i16

else:

#否則17

tmp=qu.popleft()

#出隊(duì)后進(jìn)入隊(duì)尾18

qu.append(tmp)19

i-=1

#操作次數(shù)減少120

return

len(st)上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為36ms，消耗空間為15MB。59/832.7優(yōu)先隊(duì)列2.7.1優(yōu)先隊(duì)列的定義普通隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，在隊(duì)尾進(jìn)隊(duì)元素，在隊(duì)頭出隊(duì)元素。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級(jí)，出隊(duì)的元素總是當(dāng)前具有最高優(yōu)先級(jí)的元素，實(shí)際上普通隊(duì)列可以看成進(jìn)隊(duì)時(shí)間越早優(yōu)先級(jí)越高的優(yōu)先隊(duì)列。優(yōu)先隊(duì)列通常采用堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，元素值越小越優(yōu)先出隊(duì)的優(yōu)先隊(duì)列對(duì)應(yīng)小根堆，元素值越大越優(yōu)先出隊(duì)的優(yōu)先隊(duì)列對(duì)應(yīng)大根堆。60/832.7.2Python中的優(yōu)先隊(duì)列Python中提供了heapq模塊，其中包含優(yōu)先隊(duì)列的基本操作方法，默認(rèn)創(chuàng)建小根堆。61/83優(yōu)先隊(duì)列pqu的主要操作及其說明如下：①heapq.heapify(pqu)：把列表pqu調(diào)整為堆。②len(pqu)：返回pqu中的元素個(gè)數(shù)。③pqu[0]：取堆頂?shù)脑亍＂躧eapq.heappush(pqu，e)：將元素e插入到優(yōu)先隊(duì)列pqu中，該方法會(huì)維護(hù)堆的性質(zhì)。⑤heapq.heappop(pqu)：從優(yōu)先隊(duì)列pqu中刪除堆頂元素并且返回該元素。⑥heapq.heapreplace(pqu，e)：從優(yōu)先隊(duì)列pqu中刪除堆頂元素并且返回該元素，同時(shí)將e插入并且維護(hù)堆的性質(zhì)。⑦h(yuǎn)eapq.heappushpop(pqu，e)：將元素e插入到優(yōu)先隊(duì)列pqu中，然后從pqu中刪除堆頂元素并且返回該元素值。62/831importheapq2pqu=[]

#定義一個(gè)優(yōu)先隊(duì)列pqu3heapq.heappush(pqu,2) #進(jìn)隊(duì)元素24heapq.heappush(pqu,3) #進(jìn)隊(duì)元素35heapq.heappush(pqu,1) #進(jìn)隊(duì)元素16whilelen(pqu)>0:7 print(heapq.heappop(pqu),end='') #依次輸出1238print()63/832.7.3實(shí)戰(zhàn)—數(shù)據(jù)流中的第k大元素（LeetCode703★）問題描述：設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第k大元素的類。注意是排序后的第k大元素，不是第k個(gè)不同的元素。請(qǐng)實(shí)現(xiàn)

KthLargest

類：

（1）KthLargest(intk,int[]nums)：使用整數(shù)k和整數(shù)流nums初始化對(duì)象。

（2）intadd(intval)：將val插入數(shù)據(jù)流nums后，返回當(dāng)前數(shù)據(jù)流中第k大的元素。 KthLargestkthLargest=newKthLargest(3,[4,5,8,2]); kthLargest.add(3); //返回4 kthLargest.add(5); //返回5 kthLargest.add(10); //返回5 kthLargest.add(9); //返回8 kthLargest.add(4); //返回864/83解KthLargest

類用于數(shù)據(jù)流操作，設(shè)計(jì)一個(gè)小根堆minpq，并始終保證在當(dāng)前操作后小根堆中保存當(dāng)前數(shù)據(jù)流中前k個(gè)最大的元素，這樣堆頂就是第k大元素。65/83KthLargest(k，nums)：構(gòu)造函數(shù)。對(duì)應(yīng)的過程是先求出nums中元素個(gè)數(shù)n。

若n<k，將nums中全部元素進(jìn)入minpq。否則將nums的前k個(gè)元素進(jìn)入minpq，用i遍歷剩余的元素，若nums[i]大于堆頂元素，則出堆一個(gè)元素，再將nums[i]進(jìn)堆（相當(dāng)于用nums[i]替換堆頂元素，但不能直接替換）。66/83add(val)：用于插入val并且返回當(dāng)前第k大的元素。根據(jù)題意做本操作時(shí)小根堆中至少有k-1個(gè)元素。若minpq中恰好有k-1個(gè)元素，則將val進(jìn)堆。否則若nums[i]大于堆頂元素，則出堆一個(gè)元素，再將nums[i]進(jìn)堆。最后返回堆頂元素。67/831 importheapq2 classKthLargest:3 def__init__(self,k,nums): #構(gòu)造函數(shù)4 self.minpq=[]

#小根堆5 self.K=k6 n=len(nums)7 ifn<k:8 foriinrange(0,n):9 heapq.heappush(self.minpq,nums[i])68/8310 else:11 foriinrange(0,self.K):12 heapq.heappush(self.minpq,nums[i])13 foriinrange(self.K,n):14 ifself.minpq[0]<nums[i]:15 heapq.heappop(self.minpq)16 heapq.heappush(self.minpq,nums[i])1769/8318 defadd(self,val:int)->int:19 iflen(self.minpq)==self.K-1:20 heapq.heappush(self.minpq,val)21 else:22 ifself.minpq[0]<val:23 heapq.heappop(self.minpq)24 heapq.heappush(self.minpq,val)25 returnself.minpq[0]上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為76ms，消耗空間為19.3MB。70/832.8樹和二叉樹2.8.1樹樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合（記為T）。如果n=0，它是一棵空樹，這是樹的特例。如果n>0，這n個(gè)結(jié)點(diǎn)中有且僅有一個(gè)結(jié)點(diǎn)作為樹的根（root），其余結(jié)點(diǎn)可分為m（m≥0）個(gè)互不相交的有限集T1、T2、…、Tm，其中每個(gè)子集本身又是一棵符合本定義的樹，稱為根的子樹。rootT1T2Tm…71/83樹特別適合表示具有層次關(guān)系的數(shù)據(jù)。由一棵或者多棵樹構(gòu)成森林，可以將森林看成是樹的集合。樹的存儲(chǔ)要求既要存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)元素本身，又要存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系。樹的常用存儲(chǔ)結(jié)構(gòu)有雙親存儲(chǔ)結(jié)構(gòu)、孩子鏈存儲(chǔ)結(jié)構(gòu)和長(zhǎng)子兄弟鏈存儲(chǔ)結(jié)構(gòu)。72/832.8.2二叉樹1.二叉樹的定義二叉樹是有限的結(jié)點(diǎn)集合。這個(gè)集合或者是空，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。21435673/83在一棵二叉樹中如果所有分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。0125436滿二叉樹結(jié)點(diǎn)層序編號(hào)：(i-1)/2i2i+12i+274/83在一棵二叉樹中如果最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于2，并且最下面一層的葉子結(jié)點(diǎn)都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。0124375/8321435(a)一棵二叉樹53421403521(b)補(bǔ)齊為完全二叉樹021124334NIL55(c)二叉樹順序存儲(chǔ)結(jié)構(gòu)2.二叉樹的存儲(chǔ)結(jié)構(gòu)1）二叉樹順序存儲(chǔ)結(jié)構(gòu)76/832）二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)root21∧3∧∧4∧5∧∧2143577/83整數(shù)二叉鏈結(jié)點(diǎn)類TreeNode1 class

TreeNode:2

def

__init__(self,

x):3

self.val=x4

self.left=None5

self.right=Noneroot21∧3∧∧4∧5∧∧78/833.二叉樹遍歷先序遍歷中序遍歷后序遍歷層次遍歷79/832.8.3實(shí)戰(zhàn)—二叉樹的完全性檢驗(yàn)（LeetCode958★★）問題描述：給定一棵二叉樹，采用二叉鏈存儲(chǔ)，確定它是否是一棵完全二叉樹。

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

def

isCompleteTree(self,

root)

->

bool:80/83解

根據(jù)完全二叉樹的定義，對(duì)完全二叉樹進(jìn)行層次遍歷時(shí)應(yīng)該滿足以下條件：

（1）若某結(jié)點(diǎn)沒有左孩子，則一定無(wú)右孩子。

（2）若某結(jié)點(diǎn)缺左或右孩子，則其所有后繼結(jié)點(diǎn)一定無(wú)孩子，或者說其所有后繼結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。

若不滿足上述任何一條，則不為完全二叉樹。81/831 class

Solution:2

def

isCompleteTree(self,

root)

->

bool:3

ans=True;

#ans表示是否為完全二叉樹4

bj=True;

#bj表示是否所有結(jié)點(diǎn)均有左右孩子5

qu=deque()

#定義一個(gè)隊(duì)列6

qu.append(root)

#根結(jié)點(diǎn)進(jìn)隊(duì)82/837

while

qu:8

p=qu.popleft()

#出隊(duì)一個(gè)結(jié)點(diǎn)p9

if

p.left==None:

#結(jié)點(diǎn)p沒有左孩子10

bj=False11

if

p.right!=None:ans=False

#違反(1)12

else:

#結(jié)點(diǎn)p有左孩子13

if

bj==True: #所有結(jié)點(diǎn)均有左右孩子14

qu.append(p.left)

#左孩子進(jìn)隊(duì)15

if

p.right==None:bj=False16

else:qu.append(p.right)17

else:ans=False

#違反(2)18

return

ans上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為36ms，消耗空間為14.9MB。83/83第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提綱84/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ú)向圖G30123485/572.圖的存儲(chǔ)結(jié)構(gòu)1）鄰接矩572）邊數(shù)組n=4edges=[[0，1，2]，[0，2，4]，[1，2，2]，[2，3，3]，[3，0，1]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]]0123488/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]] ]338543121014352189/573.圖的遍歷1）深度優(yōu)先遍歷DFS序列：0，1，2，3，4，5338543121014352190/572）廣度優(yōu)先遍歷BFS序列：0，1，2，3，5，4338543121014352191/57一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只包含構(gòu)成一棵樹的n-1條邊。一個(gè)帶權(quán)連通圖中權(quán)值和最小的生成樹稱為最小生成樹。Prim算法。Kruskal算法。4.生成樹和最小生成樹92/57對(duì)于帶權(quán)圖中兩個(gè)頂點(diǎn)之間的路徑可能有多條，把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度或者最短距離。Dijkstra算法。Floyd算法。5.最短路徑93/57在一個(gè)有向圖G中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。如果一個(gè)有向圖拓?fù)渑判虍a(chǎn)生包含全部頂點(diǎn)的拓?fù)湫蛄?，則該圖中不存在環(huán)，否則該圖中一定存在環(huán)。6.拓?fù)渑判?4/572.9.2實(shí)戰(zhàn)—課程表（LeetCode207★★）問題描述：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:95/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ù)渑判蛲戤叄鬾=numCourses則說明沒有環(huán)，能夠完成所有課程的學(xué)習(xí)，返回True，否則說明存在環(huán)，不能完成所有課程的學(xué)習(xí)，返回False。解96/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]ab97/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é)果為通過，運(yùn)行時(shí)間為44ms，消耗空間為15.9MB。98/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ǔ)99/57基本運(yùn)算①Init()：初始化。②Find(x)：查找x（x∈U）結(jié)點(diǎn)所屬的等價(jià)類。③Union(x，y)：將x和y（x∈U，y∈U）所屬的兩個(gè)等價(jià)類合并。100/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)的秩(近似于高度)101/571 def

Init(self,n):

#并查集初始化2

for

i

in

range(0,n):3

self.parent[i]=i4

self.rnk[i]=0i102/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查找中路徑壓縮CC103/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查找中路徑壓縮104/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的孩子105/572.10.2實(shí)戰(zhàn)—省份數(shù)量（LeetCode547★★）問題描述：有n個(gè)城市，其中一些彼此相連，另一些沒有相連。如果城市a與城市b直接相連，且城市b與城市c直接相連，那么城市a與城市c間接相連。省份是一組直接或間接相連的城市，組內(nè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:106/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。解107/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]=0108/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]ABxACxCB109/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的秩不變110/5720

else:21

if

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

#秩相同，rx的秩增122

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

self.parent[ry]=rx

#ry結(jié)點(diǎn)作為rx的孩子24ryyrxxryyrxxrx的秩不變112/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é)果為通過，運(yùn)行時(shí)間為48ms，消耗空間為15.4MB。113/572.11.1二叉排序樹1.二叉排序樹的定義2.11二叉排序樹和平衡二叉樹538167中序序列：135678

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

（1