《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件全套 李春葆 第1-9章 緒論、常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用 - 最難問(wèn)題-NP完全問(wèn)題

教材：《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述），李春葆等清華大學(xué)出版社20241/49第1章算法入門—概論1.1算法的概念1.2算法分析CONTENTS提綱2/49算法（algorithm）是求解問(wèn)題的一系列計(jì)算步驟，是一個(gè)由若干運(yùn)算或指令組成的有限序列，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。算法輸入輸出1.1.1什么是算法1.1算法的概念3/49算法的5大特性有窮性：在有限步之后結(jié)束。確定性：每一條指令必須有確切的含義，不會(huì)產(chǎn)生二義性?？尚行裕喝藗儍H用筆和紙做有限次運(yùn)算就能完成。輸入：有零個(gè)或多個(gè)輸入。輸出：有一個(gè)或多個(gè)輸出。4/49算法（有窮性、確定性、可行性）輸入輸出求解問(wèn)題5/49【例1-1】有下列兩段描述：

描述1：

描述2：defexam1(): defexam2(): n=2 y=0 whilen%2==0:n=n+2 x=5/y print(n) println(x)違反有窮性違反可行性6/49算法設(shè)計(jì)要求正確性：對(duì)指定的每個(gè)輸入實(shí)例都能輸出正確的結(jié)果并停止。可使用性：用戶友好性。可讀性：算法邏輯清晰、簡(jiǎn)單和結(jié)構(gòu)化。健壯性：容錯(cuò)性。高效率與低存儲(chǔ)量：好的時(shí)空性能。7/491.1.2算法描述Python語(yǔ)言描述算法一般形式采用Python實(shí)現(xiàn)算法。Python中方法的參數(shù)分為引用類型和基本數(shù)據(jù)類型（非引用類型）。在方法調(diào)用時(shí)基本數(shù)據(jù)類型參數(shù)只會(huì)執(zhí)行實(shí)參到形參的單向值傳遞，執(zhí)行方法中這類參數(shù)的改變不會(huì)回傳給對(duì)應(yīng)的實(shí)參。8/49Sum問(wèn)題：求s=1+2+…+n。1=11+2=31+2+3=61+2+3+4=10…9/491 defSum1(n,s):2 ifn<=0:returnFalse #參數(shù)錯(cuò)誤時(shí)返回假3 foriinrange(1,n+1):s+=i4 returnTrue #參數(shù)正確時(shí)計(jì)算出結(jié)果并返回真Sum問(wèn)題：求s=1+2+…+n。1 n,b=10,02 ret=Sum1(n,b)3 print("ret:%s,b:%d"%(ret,b))輸出結(jié)果“ret:True，b:0”顯然結(jié)果是錯(cuò)誤10/491 defSum2(n,sl):2 ifn<=0:returnFalse #參數(shù)錯(cuò)誤時(shí)返回假3 sl[0]=04 foriinrange(1,n+1):sl[0]+=i5 returnTrue #參數(shù)正確時(shí)計(jì)算出結(jié)果并返回真改正：1 n,b=10,[0]2 ret=Sum2(n,b)3 print("ret:%s,b:%d"%(ret,b[0]))輸出結(jié)果“ret:True，b:55”O(jiān)K!11/49對(duì)于一些簡(jiǎn)單的算法：只有一個(gè)輸出并且通過(guò)約束輸入總能夠得到正確結(jié)果時(shí)，可以直接用方法返回值表示輸出，這樣會(huì)簡(jiǎn)化算法設(shè)計(jì)！1 defSum3(n):2 s=03 foriinrange(1,n+1):s+=i4 returns1 n=102 print("b:%d"%(Sum3(n)))輸出結(jié)果“b:55”O(jiān)K!12/491.1.3算法和數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的基礎(chǔ)。算法的操作對(duì)象是數(shù)據(jù)結(jié)構(gòu)。在設(shè)計(jì)算法時(shí)通常要構(gòu)建適合這種算法的數(shù)據(jù)結(jié)構(gòu)。13/491.1.4算法設(shè)計(jì)的基本步驟分析求解問(wèn)題選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)策略描述算法證明算法正確性算法分析建立數(shù)學(xué)模型14/491.2算法分析1.2.1算法時(shí)間復(fù)雜度分析1.什么是算法時(shí)間復(fù)雜度分析事前分析估算法：認(rèn)為算法的“運(yùn)行工作量”的大小只依賴于問(wèn)題規(guī)模n，或者說(shuō)它是問(wèn)題規(guī)模的函數(shù)。算法執(zhí)行時(shí)間是算法中所有語(yǔ)句的執(zhí)行時(shí)間之和，顯然與算法中所有語(yǔ)句的執(zhí)行次數(shù)成正比，可以簡(jiǎn)單地用算法中基本操作的執(zhí)行次數(shù)來(lái)度量。算法中的基本操作是指最深層循環(huán)內(nèi)的原操作，它對(duì)算法執(zhí)行時(shí)間的貢獻(xiàn)最大，是算法中最重要的操作。算法中所有基本操作的執(zhí)行次數(shù)為f(n)。15/49算法時(shí)間復(fù)雜度分析是一種漸進(jìn)分析，是指當(dāng)問(wèn)題規(guī)模n很大并趨于無(wú)窮大時(shí)對(duì)算法的時(shí)間性能分析，可表示為同時(shí)忽略低階項(xiàng)和最高階系數(shù)。16/49算法分析問(wèn)題規(guī)模n，找出其中的基本語(yǔ)句，求出其運(yùn)算次數(shù)f(n)用大O、大

或大

表示算法分析17/49上界定義：

f(n)=O(g(n))（讀作“f(n)是g(n)的大O”），其含義是存在正常量c和n0，使得n≥n0有0≤f(n)≤cg(n)。也就是說(shuō)f(n)的階不高于g(n)的階，稱g(n)為f(n)的上界。cg(n)f(n)nf(n)=O(g(n))n018/49可以利用極限來(lái)證明：如果=c并且c≠∞，則有f(n)=O(g(n))。19/49一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=O(nm)。例如3n+2=O(n)，因?yàn)?/p>

成立。10n2+4n+2=O(n4)，因?yàn)?/p>

成立。=c≠∞，則有f(n)=O(g(n))。20/49示例對(duì)于f(n)=2n，g(n)=n!，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

(g(n))，并簡(jiǎn)要說(shuō)明理由。f(n)=O(g(n))，因?yàn)閒(n)的階低于g(n)的階。解：或者21/49下界定義：

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c和n0，使得n≥n0時(shí)f(n)≥cg(n)。也就是說(shuō)f(n)的階不低于g(n)的階，稱g(n)為f(n)的下界。f(n)cg(n)nf(n)=

(g(n))n022/49可以利用極限來(lái)證明：如果=c并且c≠0，則有f(n)=

(g(n))。23/49=c≠0，則有f(n)=

(g(n))。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。例如3n+2=

(n)，因?yàn)?/p>

成立。10n2+4n+2=

(n)，因?yàn)?/p>

成立。24/49示例對(duì)于f(n)=3n，g(n)=2n，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

(g(n))，并簡(jiǎn)要說(shuō)明理由。f(n)=Ω(g(n))，因?yàn)閒(n)的階高于g(n)的階。解：或者≠0。25/49確界定義：

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c1、c2和n0，使得n≥n0時(shí)有c1g(n)≤f(n)≤c2g(n)。也就是說(shuō)g(n)與f(n)的同階，也稱g(n)為f(n)的確界。c2g(n)c1g(n)f(n)n0nf(n)=

(g(n))26/49可以利用極限來(lái)證明：如果=c并且0<c<∞，則有f(n)=

(g(n))。27/49，0<c<∞，則有f(n)=

(g(n))。例如3n+2=

(n)。10n2+4n+2=

(n2)。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。28/49證明2n+1=

(2n)關(guān)系成立。示例證明：c=2，c≠0并且c≠∞2n+1=

(2n)29/49大

符號(hào)比大O符號(hào)和大

符號(hào)都要精確，f(n)=

(g(n))隱含著f(n)=O(g(n))和f(n)=

(g(n))。目前國(guó)內(nèi)大部分教科書中習(xí)慣使用大O符號(hào)（實(shí)際上指最接近的那個(gè)上界），本書主要也采用這種表示形式。說(shuō)明30/494.算法的最好、最壞和平均情況分析

定義4設(shè)一個(gè)算法的輸入規(guī)模為n，Dn是所有輸入的集合，任一輸入I∈Dn，P(I)是I出現(xiàn)的概率，有P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本操作次數(shù)，則該算法的平均執(zhí)行時(shí)間為A(n)=

I∈DnP(I)*T(I)對(duì)應(yīng)的時(shí)間復(fù)雜度稱為平均時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度反映算法的總體時(shí)間性能。31/49算法的最好情況為G(n)=minI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最少執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱為最好時(shí)間復(fù)雜度，最好時(shí)間復(fù)雜度反映算法的最佳性能，即為算法的時(shí)間下界。算法的最壞情況為W(n)=maxI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最大執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱為最懷時(shí)間復(fù)雜度，最懷時(shí)間復(fù)雜度為算法的時(shí)間上界。32/49【例1-4】設(shè)計(jì)一個(gè)盡可能高效的算法，在長(zhǎng)度為n的一維整型數(shù)組a[0..n-1]中查找值最大的元素maxe和值最小的元素mine。并分析算法的最好、最壞和平均時(shí)間復(fù)雜度。解1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))33/49該算法的基本語(yǔ)句是元素比較。最好的情況是a中元素遞增排列，元素比較次數(shù)為n-1，即G(n)=n-1=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))34/49最壞的情況是a中元素遞減排列，元素比較次數(shù)為2(n-1)，即W(n)=2(n-1)=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))35/49平均情況：a中有一半的元素比maxe大，a[i]>maxe比較執(zhí)行n-1次，a[i]<mine比較執(zhí)行(n-1)/2次，因此平均元素比較次數(shù)為3(n-1)/2，即A(n)=3(n-1)/2=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))36/49【例1-5】采用順序查找方法，在長(zhǎng)度為n的一維整數(shù)數(shù)組a[0..n-1]中查找值為x的元素，即從數(shù)組的第一個(gè)元素開始，逐個(gè)與被查值x進(jìn)行比較。找到后返回True，否則返回False，對(duì)應(yīng)的算法如下：1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse37/491 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse回答以下問(wèn)題：

（1）分析該算法在等概率情況下成功查找到值為x的元素的最好、最壞和平均時(shí)間復(fù)雜度。

（2）假設(shè)被查值x在數(shù)組a中的概率是p，不在數(shù)組a中的概率是1-p，求算法的平均時(shí)間復(fù)雜度。38/49（1）僅考慮查找成功的情況。

算法的while循環(huán)中if語(yǔ)句是基本操作（用于元素比較）。a數(shù)組中有n個(gè)元素，當(dāng)?shù)谝粋€(gè)元素a[0]等于x，此時(shí)基本操作僅執(zhí)行一次，此時(shí)呈現(xiàn)最好的情況，即G(n)=1=O(1)。

當(dāng)a中最后一個(gè)元素a[n-1]等于x，此時(shí)基本操作執(zhí)行n次，此時(shí)呈現(xiàn)最壞的情況，即W(n)=n=O(n)。解1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse39/49對(duì)于成功查找的平均情況，假設(shè)查找到每個(gè)元素的概率相同，則P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素時(shí)基本操作正好執(zhí)行i+1次。

所以：1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse40/49（2）這里是既考慮成功查找又考慮不成功查找的情況。

對(duì)于成功查找，被查值x在數(shù)組a中的概率為p時(shí)，算法執(zhí)行有n種成功情況，在等概率情況下元素a[i]被查找到的概率P(a[i])=p/n，成功找到a[i]元素時(shí)基本操作執(zhí)行i+1次。

對(duì)于不成功查找，其概率為1-p，所有不成功查找基本操作都只執(zhí)行n次，不妨看成一種情況。41/49如果已知查找的x有一半的機(jī)會(huì)在數(shù)組中，此時(shí)p=1/2，則A(n)=[(n+1)/4]+n/2≈3n/4。42/494.平攤分析考慮這樣一種算法，在算法中有一種操作反復(fù)執(zhí)行時(shí)有這樣的特性，其運(yùn)行時(shí)間始終變動(dòng)，如果這一操作在大多數(shù)時(shí)候運(yùn)行很快，只是偶爾要花費(fèi)大量時(shí)間，對(duì)這樣的算法可以采用平攤分析。在平攤分析中，執(zhí)行一系列數(shù)據(jù)結(jié)構(gòu)操作所需要的時(shí)間是通過(guò)對(duì)執(zhí)行的所有操作求平均而得出的。平攤分析可用來(lái)證明在一系列操作中，即使單一的操作具有較大的代價(jià)，通過(guò)對(duì)所有操作求平均后，平均代價(jià)還是很小的。平攤分析與平均情況分析的不同之處在于它不牽涉到概率。這種分析保證了在最壞情況下每個(gè)操作具有平均性能。43/49【例1-6】假設(shè)有一個(gè)可以存放若干個(gè)整數(shù)的整數(shù)表，其類為IntList，data域是存放整數(shù)元素的列表，capacity域表示data的容量（data列表中能夠存放的最多元素個(gè)數(shù)，初始容量為常數(shù)m），length域表示長(zhǎng)度（data列表中存放的實(shí)際元素個(gè)數(shù)）。1 classIntList:#整數(shù)表類2 m=2 #初始容量3 def__init__(self): #構(gòu)造方法4 self.capacity=self.m #容量5 self.data=[0]*self.m6 self.length=0 #長(zhǎng)度

整數(shù)表提供有這些運(yùn)算，構(gòu)造方法用于初始化，即設(shè)置初始容量、分配初始空間和將長(zhǎng)度置為0。44/497 defExpand(self): #按長(zhǎng)度兩倍擴(kuò)大容量8 self.capacity=2*self.length #設(shè)置新容量9 newdata=[0]*self.capacity10 foriinrange(0,self.length): #復(fù)制全部元素11 newdata[i]=self.data[i]12 self.data=newdata方法Expand()用于擴(kuò)大容量，當(dāng)長(zhǎng)度達(dá)到容量時(shí)置新容量為兩倍長(zhǎng)度。45/4913 defAdd(self,e): #添加e14 ifself.length==self.capacity:15 self.Expand()16 self.data[self.length]=e17 self.length+=1要求分析調(diào)用Add(e)算法的時(shí)間復(fù)雜度。Add(e)用于在表尾插入元素e。46/49Expand()算法中for循環(huán)執(zhí)行n次（n為復(fù)制的元素個(gè)數(shù)），所以其時(shí)間復(fù)雜度為O(n)。Add(e)算法中可能會(huì)調(diào)用Expand()（調(diào)用一次稱為一次擴(kuò)容），那么其時(shí)間復(fù)雜度是不是也為O(n)呢？插入n個(gè)元素調(diào)用一次Expand()，調(diào)用Expand()的時(shí)間為O(n)，其他n-1次插入的時(shí)間為O(1)，平攤結(jié)果是解13 defAdd(self,e): #添加e14 ifself.length==self.capacity:15 self.Expand()16 self.data[self.length]=e17 self.length+=147/491.2.2算法空間復(fù)雜度分析一個(gè)算法的存儲(chǔ)量包括形參所占空間和臨時(shí)變量所占空間。在對(duì)算法進(jìn)行存儲(chǔ)空間分析時(shí)，只考察臨時(shí)變量所占空間?？臻g復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間大小的量度，一般也作為問(wèn)題規(guī)模n的函數(shù)，以數(shù)量級(jí)形式給出，記作S(n)=O(g(n))、

(g(n))或

(g(n))，其中漸進(jìn)符號(hào)的含義與時(shí)間復(fù)雜度中的含義相同。48/49defmaxe(a，n): maxi=0

foriinrange(1,n):

ifa[i]>a[maxi]:maxi=i returna[maxi]方法體內(nèi)分配的變量空間為臨時(shí)空間，不計(jì)形參占用的空間，這里的僅計(jì)i、maxi變量的空間，其空間復(fù)雜度為O(1)。算法的臨時(shí)空間49/49第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二叉排序樹和平衡二叉樹50/83CONTENTS提綱51/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è)元素，依此類推。52/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ù)組。53/831）訪問(wèn)列表中的值2）列表腳本操作符3）列表的函數(shù)4）列表的方法54/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。55/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，156/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，757/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]58/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)]59/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']]60/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.非拷貝方法—直接賦值61/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.列表的深拷貝62/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.列表的淺拷貝63/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:64/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。numsnums65/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ù)66/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。67/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-k68/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ū)間69/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即可。70/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+171/83上述3個(gè)算法的時(shí)間復(fù)雜度均為O(n)，空間復(fù)雜度均為O(1)，都屬于高效的算法。提交時(shí)運(yùn)行時(shí)間均為4ms左右。結(jié)果72/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 #指針域73/83……一個(gè)帶頭結(jié)點(diǎn)的單鏈表head首結(jié)點(diǎn)尾結(jié)點(diǎn)頭結(jié)點(diǎn)

a0an-1∧a1head結(jié)點(diǎn)序號(hào)01n-174/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★）75/83問(wèn)題求解：先創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空單鏈表h，用p遍歷head，采用頭插法將結(jié)點(diǎn)p插入到表頭。最后返回h.next即可。a0heada1a2…a0pa1a2…∧h76/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。77/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)。78/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))…79/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)->int80/83問(wèn)題求解：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。81/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-182/832.4棧2.4.1棧的定義棧是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，規(guī)定只能在其中一端進(jìn)行進(jìn)棧和出棧操作，該端點(diǎn)稱為棧頂，另外一個(gè)端點(diǎn)稱為棧底。棧的主要運(yùn)算有判斷?？铡⑦M(jìn)棧、出棧和取棧頂元素等。棧具有后進(jìn)先出的特點(diǎn)83/832.4.2用Python列表實(shí)現(xiàn)棧Python中沒(méi)有提供專門的棧數(shù)據(jù)類型，由于列表具有在末尾插入和刪除元素的時(shí)間為O(1)的特性，可以用列表實(shí)現(xiàn)棧。定義一個(gè)空棧st：st=[]84/83st棧的主要操作及其說(shuō)明如下：①st，len(st)==0：判斷棧是否為空。②len(st)：返回棧的長(zhǎng)度。③st.append(e)：進(jìn)棧元素e。④st[-1]：返回棧頂元素。⑤st.pop()：移除棧頂元素。85/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()86/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:87/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)度即可。解88/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。89/832.5雙端隊(duì)列2.5.1雙端隊(duì)列的定義前端后端前端進(jìn)前端出后端進(jìn)后端出雙端隊(duì)列是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，每個(gè)端點(diǎn)都可以進(jìn)隊(duì)和出隊(duì)元素。90/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()91/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ì)元素。92/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()93/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）。94/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

95/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）96/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

ans97/83上述程序提交結(jié)果為通過(guò)，運(yùn)行時(shí)間為365ms，消耗空間為28.9MB。98/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)。99/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ì)列二100/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)棧二101/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ì)拿走它并離開隊(duì)列，否則這名學(xué)生會(huì)放棄這個(gè)三明治并回到隊(duì)列的尾部。這個(gè)過(guò)程會(huì)一直持續(xù)到隊(duì)列里所有學(xué)生都不喜歡棧頂?shù)娜髦螢橹埂?02/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ù)量。103/83例如students=[1，1，1，0，0，1]，sandwiches=[1，0，0，0，1，1]，n=6，過(guò)程如下：

（1）students[0]=sandwiches[0]，拿走三明治并離開隊(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]，拿走三明治并離開隊(duì)列，問(wèn)題轉(zhuǎn)換為n=4，students=[0，1，1，1]，sandwiches=[0，0，1，1]。

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

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

def

countStudents(self,students,sandwiches)->int:105/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ù)量。解106/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ì)列107/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。108/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)大根堆。109/832.7.2Python中的優(yōu)先隊(duì)列Python中提供了heapq模塊，其中包含優(yōu)先隊(duì)列的基本操作方法，默認(rèn)創(chuàng)建小根堆。110/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中刪除堆頂元素并且返回該元素值。111/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()112/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); //返回8113/83解KthLargest

類用于數(shù)據(jù)流操作，設(shè)計(jì)一個(gè)小根堆minpq，并始終保證在當(dāng)前操作后小根堆中保存當(dāng)前數(shù)據(jù)流中前k個(gè)最大的元素，這樣堆頂就是第k大元素。114/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]替換堆頂元素，但不能直接替換）。115/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)堆。最后返回堆頂元素。116/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])117/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 hea