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

第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樹(shù)和二叉樹(shù)2.9圖2.10并查集2.12哈希表2.11二叉排序樹(shù)和平衡二叉樹(shù)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）訪問(wèn)列表中的值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]就是原來(lái)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]就是原來(lái)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★）問(wèn)題描述：給定一個(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í)跳過(guò)。最后返回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開(kāi)始遍歷v，初始時(shí)刪除區(qū)間也為空。

vi

…

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

vkvk+1

…

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

①若v[i]≠val，將其通過(guò)交換添加到保留區(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問(wèn)題描述：給定一個(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問(wèn)題求解：先創(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é)果為通過(guò)，運(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)來(lái)創(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★）問(wèn)題描述：給你一個(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問(wèn)題求解：k從1開(kāi)始，構(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中沒(méi)有提供專門的棧數(shù)據(jù)類型，由于列表具有在末尾插入和刪除元素的時(shí)間為O(1)的特性，可以用列表實(shí)現(xiàn)棧。定義一個(gè)空棧st：st=[]35/83st棧的主要操作及其說(shuō)明如下：①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★★）

問(wèn)題描述：給定一個(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í)：若棧不空并且棧頂為'('，說(shuō)明這一對(duì)括號(hào)是匹配的，將棧頂'('退棧。否則說(shuō)明該')'是不匹配的，需要添加一個(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é)果為通過(guò)，運(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的主要操作及其說(shuō)明如下：①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★★★)問(wèn)題描述：給定一個(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ì)頭過(guò)期的元素從隊(duì)頭出隊(duì)，為此nums[i]進(jìn)隊(duì)時(shí)改為求序號(hào)i進(jìn)隊(duì)。本題f

s

…

i

kdq[0]前端過(guò)期：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ì)頭過(guò)期的元素從隊(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é)果為通過(guò)，運(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中沒(méi)有提供專門的隊(duì)列數(shù)據(jù)類型，通常用雙端隊(duì)列deque作為隊(duì)列，即通過(guò)限制操作將雙端隊(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í)際上還可以通過(guò)限制操作將雙端隊(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★)問(wèn)題描述：學(xué)校的自助午餐提供圓形和方形的三明治，分別用數(shù)字0和1表示。所有學(xué)生站在一個(gè)隊(duì)列里，每個(gè)學(xué)生要么喜歡圓形的要么喜歡方形的。餐廳里三明治的數(shù)量與學(xué)生的數(shù)量相同。

所有三明治都放在一個(gè)棧里，每一輪：如果隊(duì)列最前面的學(xué)生喜歡棧頂?shù)娜髦?，那么?huì)拿走它并離開(kāi)隊(duì)列，否則這名學(xué)生會(huì)放棄這個(gè)三明治并回到隊(duì)列的尾部。這個(gè)過(guò)程會(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ì)列的最開(kāi)始位置）。設(shè)計(jì)一個(gè)算法求無(wú)法吃午餐的學(xué)生數(shù)量。54/83例如students=[1，1，1，0，0，1]，sandwiches=[1，0，0，0，1，1]，n=6，過(guò)程如下：

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

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

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

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

（5）students[0]=sandwiches[0]，拿走三明治并離開(kāi)隊(duì)列，問(wèn)題轉(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è)過(guò)程，定義一個(gè)隊(duì)列qu作為學(xué)生隊(duì)列，定義一個(gè)棧st作為三明治棧，用n表示初始學(xué)生人數(shù)。如果st[-1]==qu[0]，子問(wèn)題人數(shù)n減少1；否則執(zhí)行tmp=qu.popleft()，qu.append(tmp)問(wèn)題的關(guān)鍵是如何確定循環(huán)結(jié)束的條件：用i累計(jì)子問(wèn)題的該操作次數(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

#子問(wèn)題的人數(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é)果為通過(guò)，運(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)來(lái)實(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的主要操作及其說(shuō)明如下：①heapq.heapify(pqu)：把列表pqu調(diào)整為堆。②len(pqu)：返回pqu中的元素個(gè)數(shù)。③pqu[0]：取堆頂?shù)脑?。④heapq.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★）問(wèn)題描述：設(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)的過(guò)程是先求出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é)果為通過(guò)，運(yùn)行時(shí)間為76ms，消耗空間為19.3MB。70/832.8樹(shù)和二叉樹(shù)2.8.1樹(shù)樹(shù)是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合（記為T）。如果n=0，它是一棵空樹(shù)，這是樹(shù)的特例。如果n>0