《算法設(shè)計與分析基礎(chǔ)》（Python語言描述） 課件 第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隊列2.6雙端隊列2.7優(yōu)先隊列2.8樹和二叉樹2.9圖2.10并查集2.12哈希表2.11二叉排序樹和平衡二叉樹1/83CONTENTS提綱2/832.1線性表—數(shù)組2.1.1線性表的定義線性表是性質(zhì)相同的n（n≥0）個元素的有限序列。每個元素有唯一的序號或者位置，也稱為下標或者索引，通常下標是介于0到n-1之間。線性表中的n個元素從頭到尾分別稱為第0個元素，第1個元素，依此類推。3/832.1.2Python列表Python中數(shù)組對應(yīng)列表類型，Python列表的基本形式是一個方括號內(nèi)以逗號分隔的若干值，列表的值不需要具有相同的類型。可以用列表存儲線性表。例如，列表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個最大元素★★）給定一個含n個整數(shù)的數(shù)組nums和整數(shù)k（1≤k≤n），請返回數(shù)組中第k個最大的元素。請注意，你需要找的是數(shù)組排序后的第k個最大的元素，而不是第k個不同的元素。

例如，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序號：

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序號：

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)進行排序。討論前者。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對于多關(guān)鍵字排序，key可以使用operator模塊提供的itemgetter函數(shù)獲取對象的哪些維的數(shù)據(jù)實現(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) #對第二個關(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]) #對第一個關(guān)鍵字升序排序8 print(list) #輸出：[('a',4),('a',1),('b',3),('c',3)]9 list.sort(key=lambdax:(x[0],-x[1])) #對第一序,第二降序排序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é)號遞增排序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實戰(zhàn)—移除元素（LeetCode27★）問題描述：給定一個數(shù)組nums和一個值val，需要原地移除所有等于val的元素，并返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間（即算法的空間復(fù)雜度為O(1)），元素的順序可以改變。

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

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

def

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

i+=110

return

k

#返回保留的元素個數(shù)17/83解法2：移動法。同樣用nums存放刪除所有val元素的結(jié)果，先將結(jié)果數(shù)組看成是整個表，用k表示要刪除的元素個數(shù)（初始為0），用i遍歷nums：①遇到保留元素（不等于val）時將nums[i]前移k個位置。②遇到val元素時將k增1。遍歷完畢返回結(jié)果數(shù)組的長度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ù)組中的元素個數(shù)5

while

i<n:6

if

nums[i]!=val:

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

nums[i-k]=nums[i]

#將nums[i]前移k個位置8

else:

#nums[i]是要刪除的元素9

k+=1

#k增110

i+=111

return

n-k

#返回結(jié)果數(shù)組的長度n-k19/83解法3：區(qū)間劃分法。用v[0..k]（共k+1個元素）表示保留的元素區(qū)間（即不為val區(qū)間），初始時保留區(qū)間為空，所以置k=-1。v[k+1..i-1]（共i-k-1個元素）表示刪除元素區(qū)間（即為val的區(qū)間），i從0開始遍歷v，初始時刪除區(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++擴大刪除區(qū)間，再繼續(xù)遍歷。

vi

…

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

vkvk+1

…

vi-1刪除區(qū)間最后的結(jié)果v中僅保留所有不為val區(qū)間的k+1個元素，返回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ù)組中的元素個數(shù)5

while

i<n:6

if

nums[i]!=val:

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

k+=1

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

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

#交換9

i+=110

return

k+1

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

class

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

__init__(self,

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

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

reverseList(self,

head:

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

Solution:2

def

reverseList(self,

head:

Optional[ListNode]):3

h=ListNode()

#建立一個頭結(jié)點h4

p=head5

while

p!=None:6

q=p.next7

p.next=h.next

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

h.next=p9

p=q10

return

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

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

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

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棧的定義棧是一種特殊的線性表，有前、后兩個端點，規(guī)定只能在其中一端進行進棧和出棧操作，該端點稱為棧頂，另外一個端點稱為棧底。棧的主要運算有判斷?？铡⑦M棧、出棧和取棧頂元素等。棧具有后進先出的特點34/832.4.2用Python列表實現(xiàn)棧Python中沒有提供專門的棧數(shù)據(jù)類型，由于列表具有在末尾插入和刪除元素的時間為O(1)的特性，可以用列表實現(xiàn)棧。定義一個空棧st：st=[]35/83st棧的主要操作及其說明如下：①st，len(st)==0：判斷棧是否為空。②len(st)：返回棧的長度。③st.append(e)：進棧元素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實戰(zhàn)—使括號有效的最少添加（LeetCode921★★）

問題描述：給定一個由

'('

和

')'

括號組成的字符串

S，需要添加最少的括號（

'('

或是

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

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

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

minAddToMakeValid(self,

s:

str)

->

int:38/83定義一個棧st。遍歷字符串s：遇到'('時進棧。遇到')'時：若棧不空并且棧頂為'('，說明這一對括號是匹配的，將棧頂'('退棧。否則說明該')'是不匹配的，需要添加一個'('，將其進棧。遍歷結(jié)束后，棧中每個'('需要添加一個')'，每個')'需要添加一個'('，這是使得括號字符串s匹配需要添加的最少括號個數(shù)，返回st的長度即可。解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:

#?？栈蛘卟黄ヅ涞?)'進棧11

st.append(ch)12

return

len(st)上述程序提交結(jié)果為通過，運行時間為28ms，消耗空間為14.8MB。40/832.5雙端隊列2.5.1雙端隊列的定義前端后端前端進前端出后端進后端出雙端隊列是一種特殊的線性表，有前、后兩個端點，每個端點都可以進隊和出隊元素。41/832.5.2Python中的雙端隊列dequedeque是Python標準庫collections中的一個類，實現(xiàn)了兩端都可以操作的隊列即雙端隊列，與Python的列表相似。定義一個空的deque對象dq：dq=deque()42/83dq的主要操作及其說明如下：①dq，len(dq)==0：判斷隊列是否為空。②len(dq)：返回隊列的長度。③dq.clear()：清除雙端隊列中的所有元素。④dq[0]：返回雙端隊列中左端（前端）的元素。⑤dq[-1]：返回雙端隊列中右端（后端）的元素。⑥dq.appendleft(e)：從雙端隊列的左端（前端）進隊元素e。⑦dq.popleft()：從雙端隊列的左端（前端）出隊元素。⑧dq.append(e)：從雙端隊列的右端（后端）進隊元素e。⑨dq.pop()：從雙端隊列的右端（后端）出隊元素。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("左端出隊")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個滑動窗口2.5.3實戰(zhàn)—滑動窗口最大值(LeetCode239★★★)問題描述：給定一個含n個整數(shù)的數(shù)組nums和一個整數(shù)k（1≤k≤n），一個大小為k的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)，每次只能看到滑動窗口內(nèi)的k個整數(shù)?；瑒哟翱诿看蜗蛴乙苿右晃?。設(shè)計一個算法返回滑動窗口中的最大值。

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

s

…

i

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

46/83nums:隊頭隊尾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()

#定義一個雙端隊列dq5

ans=[]6

for

i

in

range(0,n):

#處理nums中剩余的元素7

while

len(dq)>0

and

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

dq.pop()

#將隊尾小于nums[i]者從隊尾出隊9

dq.append(i)

#將元素下標i進隊尾10

if

i-dq[0]>=k:

#將隊頭過期的元素從隊頭出隊11

dq.popleft()12

if

i>=k-1:

#i>=k-1時每個位置對應(yīng)一個窗口13

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

#新隊頭元素添加到ans中14

return

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

所有三明治都放在一個棧里，每一輪：如果隊列最前面的學(xué)生喜歡棧頂?shù)娜髦危敲磿米咚㈦x開隊列，否則這名學(xué)生會放棄這個三明治并回到隊列的尾部。這個過程會一直持續(xù)到隊列里所有學(xué)生都不喜歡棧頂?shù)娜髦螢橹埂?3/83給定兩個整數(shù)數(shù)組students和sandwiches（兩個數(shù)組的長度相同），其中sandwiches[i]是棧里面第i??個三明治的類型（i=0是棧的頂部），students[j]是初始隊列里第j名學(xué)生對三明治的喜好（j=0是隊列的最開始位置）。設(shè)計一個算法求無法吃午餐的學(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]，拿走三明治并離開隊列，問題轉(zhuǎn)換為n=5，students=[1，1，0，0，1]，sandwiches=[0，0，0，1，1]。

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

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

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

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

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

def

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

Solution:2

def

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

n=len(students)4

qu=deque()

#定義一個隊列qu5

st=deque()

#定義一個棧st6

for

x

in

students:

#建立學(xué)生隊列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()隊頭dq[0]隊尾dq[-1]append()隊列58/8310

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

while

i>0:12

if

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

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

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

n-=1

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

i=n

#重置i16

else:

#否則17

tmp=qu.popleft()

#出隊后進入隊尾18

qu.append(tmp)19

i-=1

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

return

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

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

KthLargest

類：

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

（2）intadd(intval)：將val插入數(shù)據(jù)流nums后，返回當前數(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è)計一個小根堆minpq，并始終保證在當前操作后小根堆中保存當前數(shù)據(jù)流中前k個最大的元素，這樣堆頂就是第k大元素。65/83KthLargest(k，nums)：構(gòu)造函數(shù)。對應(yīng)的過程是先求出nums中元素個數(shù)n。

若n<k，將nums中全部元素進入minpq。否則將nums的前k個元素進入minpq，用i遍歷剩余的元素，若nums[i]大于堆頂元素，則出堆一個元素，再將nums[i]進堆（相當于用nums[i]替換堆頂元素，但不能直接替換）。66/83add(val)：用于插入val并且返回當前第k大的元素。根據(jù)題意做本操作時小根堆中至少有k-1個元素。若minpq中恰好有k-1個元素，則將val進堆。否則若nums[i]大于堆頂元素，則出堆一個元素，再將nums[i]進堆。最后返回堆頂元素。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é)果為通過，運行時間為76ms，消耗空間為19.3MB。70/832.8樹和二叉樹2.8.1樹樹是由n（n≥0）個結(jié)點組成的有限集合（記為T）。如果n=0，它是一棵空樹，這是樹的特例。如果n>0