《算法设计与分析基础》（Python语言描述） 课件 第2章 常用的数据结构及其应用

第2章工之利器—常用的数据结构及其应用2.1线性表—数组2.3字符串2.2线性表—链表2.4栈2.5队列2.6双端队列2.7优先队列2.8树和二叉树2.9图2.10并查集2.12哈希表2.11二叉排序树和平衡二叉树1/83CONTENTS提纲2/832.1线性表—数组2.1.1线性表的定义线性表是性质相同的n（n≥0）个元素的有限序列。每个元素有唯一的序号或者位置，也称为下标或者索引，通常下标是介于0到n-1之间。线性表中的n个元素从头到尾分别称为第0个元素，第1个元素，依此类推。3/832.1.2Python列表Python中数组对应列表类型，Python列表的基本形式是一个方括号内以逗号分隔的若干值，列表的值不需要具有相同的类型。可以用列表存储线性表。例如，列表a=[2，5，3，1，4]看成一维数组，列表b=[[2，3，8]，[5，3，4]]看成二维数组。4/831）访问列表中的值2）列表脚本操作符3）列表的函数4）列表的方法5/83【例2-1】（LeetCode215—数组中的第k个最大元素★★）给定一个含n个整数的数组nums和整数k（1≤k≤n），请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

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

排序后的nums[n-k]就是原来nums中第k大的整数。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大的整数。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()或者序列类型函数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对于多关键字排序，key可以使用operator模块提供的itemgetter函数获取对象的哪些维的数据实现排序。1 fromoperatorimportitemgetter,attrgetter #导入operator模块2 list=[('b',3),('a',1),('c',3),('a',4)]3 list.sort(key=itemgetter(1),reverse=True) #对第二个关键字降序排序4 print(list) #输出：[('a',4),('b',3),('c',3),('a',1)]5 list.sort(key=itemgetter(0,1),reverse=True) #第一二关键字降序排序6 print(list) #输出：[('c',3),('b',3),('a',4),('a',1)]7 list.sort(key=lambdax:x[0]) #对第一个关键字升序排序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可以制定自定义的比较规则1 importfunctools2 stud=[[3,"Mary"],[1,"Smith"],[2,"John"]] #学生列表3 defcmp1(a,b): #自定义比较函数14 returna[0]-b[0] #按学号递增排序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): #自定义比较函数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 #导入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实战—移除元素（LeetCode27★）问题描述：给定一个数组nums和一个值val，需要原地移除所有等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间（即算法的空间复杂度为O(1)），元素的顺序可以改变。

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

要求设计如下方法：

def

removeElement(self,nums:List[int],val:int)->int:15/83解法1：整体建表法。用nums存放删除所有val元素的结果，先将结果数组nums看成是一个空表，用k表示结果数组的元素个数（初始为0），用i遍历nums，遇到保留元素（不等于val）时重新插入到结果数组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记录结果数组中的元素个数5

while

i<n:6

if

nums[i]!=val:

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

nums[k]=nums[i];

#将nums[i]重新插入到结果数组中8

k+=1

#结果数组的长度增19

i+=110

return

k

#返回保留的元素个数17/83解法2：移动法。同样用nums存放删除所有val元素的结果，先将结果数组看成是整个表，用k表示要删除的元素个数（初始为0），用i遍历nums：①遇到保留元素（不等于val）时将nums[i]前移k个位置。②遇到val元素时将k增1。遍历完毕返回结果数组的长度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记录结果数组中的元素个数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

#返回结果数组的长度n-k19/83解法3：区间划分法。用v[0..k]（共k+1个元素）表示保留的元素区间（即不为val区间），初始时保留区间为空，所以置k=-1。v[k+1..i-1]（共i-k-1个元素）表示删除元素区间（即为val的区间），i从0开始遍历v，初始时删除区间也为空。

vi

…

vn-1保留区间v0…

vkvk+1

…

vi-1删除区间20/83

①若v[i]≠val，将其通过交换添加到保留区间的末尾，再执行i++继续遍历。

vi

…

vn-1保留区间v0…

vkvk+1

…

vi-1删除区间

②若v[i]=val，只需要执行i++扩大删除区间，再继续遍历。

vi

…

vn-1保留区间v0…

vkvk+1

…

vi-1删除区间最后的结果v中仅保留所有不为val区间的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记录结果数组中的元素个数5

while

i<n:6

if

nums[i]!=val:

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

k+=1

#扩大保留元素区间8

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

#交换9

i+=110

return

k+1

#返回结果数组的长度k+122/83上述3个算法的时间复杂度均为O(n)，空间复杂度均为O(1)，都属于高效的算法。提交时运行时间均为4ms左右。结果23/832.2线性表—链表2.2.1单链表定义一个整数单链表的结点类如下：1

class

ListNode: #单链表结点类2 def

__init__(self,

x):3 self.val=x #数据域4 self.next=None #指针域24/83……一个带头结点的单链表head首结点尾结点头结点

a0an-1∧a1head结点序号01n-125/83问题描述：给定一个不带头结点的单链表head，将其反转，并返回反转后的链表。例如，head=（1，2，3，4），返回结果为（4，3，2，1）。要求设计如下方法：def

reverseList(self,

head:

Optional[ListNode]):实战—反转链表（LeetCode206★）26/83问题求解：先创建一个带头结点的空单链表h，用p遍历head，采用头插法将结点p插入到表头。最后返回h.next即可。a0heada1a2…a0pa1a2…∧h27/831 class

Solution:2

def

reverseList(self,

head:

Optional[ListNode]):3

h=ListNode()

#建立一个头结点h4

p=head5

while

p!=None:6

q=p.next7

p.next=h.next

#结点p插入到表头8

h.next=p9

p=q10

return

h.next上述程序提交结果为通过，运行时间为36ms，消耗空间为16MB。28/832.3字符串2.3.1字符串的定义字符串简称为串，是字符的有限序列，可以看成元素类型是字符的线性表。一个串s中若干连续的字符构成的串t称为s的子串。空串是任何串的子串。两个串相等当且仅当它们的长度相同并且对应位置的字符均相同。字符串主要有数组和链串两种存储结构。29/832.3.2Python中的字符串Python中使用单引号或者双引号来创建字符串，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实战—最大重复子字符串（LeetCode1668★）问题描述：给你一个字符串sequence，如果字符串word连续重复k次形成的字符串是sequence的一个子串，那么单词word的重复值为k。

单词word的最大重复值是单词word在sequence中最大的重复值。如果word不是sequence的子串，那么重复值k为0。设计一个算法返回最大重复值k。

例如sequence="ababc"，word="ab"，返回结果为2。要求设计如下方法：

def

maxRepeating(self,sequence:str,word:

str)->int31/83问题求解：k从1开始，构造由word连续重复k次形成的字符串subs，若subs是sequence的子串，置k++，subs+=word，然后继续循环判断，否则退出循环，最后返回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栈的定义栈是一种特殊的线性表，有前、后两个端点，规定只能在其中一端进行进栈和出栈操作，该端点称为栈顶，另外一个端点称为栈底。栈的主要运算有判断栈空、进栈、出栈和取栈顶元素等。栈具有后进先出的特点34/832.4.2用Python列表实现栈Python中没有提供专门的栈数据类型，由于列表具有在末尾插入和删除元素的时间为O(1)的特性，可以用列表实现栈。定义一个空栈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: #栈不空循环7 print("栈顶元素:",st[-1])#依次输出43218 print("出栈")9 st.pop()37/832.4.3实战—使括号有效的最少添加（LeetCode921★★）

问题描述：给定一个由

'('

和

')'

括号组成的字符串

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

'('

或是

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

设计一个算法求为使结果字符串有效而必须添加的最少括号数。

例如，s="())"，结果为1s="(())"。要求设计如下方法：def

minAddToMakeValid(self,

s:

str)

->

int:38/83定义一个栈st。遍历字符串s：遇到'('时进栈。遇到')'时：若栈不空并且栈顶为'('，说明这一对括号是匹配的，将栈顶'('退栈。否则说明该')'是不匹配的，需要添加一个'('，将其进栈。遍历结束后，栈中每个'('需要添加一个')'，每个')'需要添加一个'('，这是使得括号字符串s匹配需要添加的最少括号个数，返回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)上述程序提交结果为通过，运行时间为28ms，消耗空间为14.8MB。40/832.5双端队列2.5.1双端队列的定义前端后端前端进前端出后端进后端出双端队列是一种特殊的线性表，有前、后两个端点，每个端点都可以进队和出队元素。41/832.5.2Python中的双端队列dequedeque是Python标准库collections中的一个类，实现了两端都可以操作的队列即双端队列，与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结果是（5，5，5，4，6，7）共n-k+1个滑动窗口2.5.3实战—滑动窗口最大值(LeetCode239★★★)问题描述：给定一个含n个整数的数组nums和一个整数k（1≤k≤n），一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，每次只能看到滑动窗口内的k个整数。滑动窗口每次向右移动一位。设计一个算法返回滑动窗口中的最大值。

例如，n=8，nums=（4，3，5，4，3，3，6，7），k=3，最终返回结果是（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结果是（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时每个位置对应一个窗口13

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

#新队头元素添加到ans中14

return

ans48/83上述程序提交结果为通过，运行时间为365ms，消耗空间为28.9MB。49/832.6队列2.6.1队列的定义队列是一种特殊的线性表，有前、后两个端点，规定只能在一端进队元素，另外一端出队元素。队列的主要运算有判断队空、进队、出队和取队头元素等。队列具有先进先出的特点。50/832.6.2Python中的队列Python中没有提供专门的队列数据类型，通常用双端队列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实战—无法吃午餐的学生数量(LeetCode1700★)问题描述：学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治的数量与学生的数量相同。

所有三明治都放在一个栈里，每一轮：如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列，否则这名学生会放弃这个三明治并回到队列的尾部。这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。53/83给定两个整数数组students和sandwiches（两个数组的长度相同），其中sandwiches[i]是栈里面第i​​个三明治的类型（i=0是栈的顶部），students[j]是初始队列里第j名学生对三明治的喜好（j=0是队列的最开始位置）。设计一个算法求无法吃午餐的学生数量。54/83例如students=[1，1，1，0，0，1]，sandwiches=[1，0，0，0，1，1]，n=6，过程如下：

（1）students[0]=sandwiches[0]，拿走三明治并离开队列，问题转换为n=5，students=[1，1，0，0，1]，sandwiches=[0，0，0，1，1]。

（2）students[0]≠sandwiches[0]，students[0]回到队列的尾部，问题转换为n=5，students=[1，0，0，1，1]，sandwiches=[0，0，0，1，1]。

（3）students[0]≠sandwiches[0]，students[0]回到队列的尾部，问题转换为n=5，students=[0，0，1，1，1]，sandwiches=[0，0，0，1，1]。

（4）students[0]=sandwiches[0]，拿走三明治并离开队列，问题转换为n=4，students=[0，1，1，1]，sandwiches=[0，0，1，1]。

（5）students[0]=sandwiches[0]，拿走三明治并离开队列，问题转换为n=3，students=[1，1，1]，sandwiches=[0，1，1]。

显然后面不可能拿走三明治，所以无法吃午餐的学生数量为3。55/83要求设计如下方法：

def

countStudents(self,students,sandwiches)->int:56/83利用队列和栈模拟整个过程，定义一个队列qu作为学生队列，定义一个栈st作为三明治栈，用n表示初始学生人数。如果st[-1]==qu[0]，子问题人数n减少1；否则执行tmp=qu.popleft()，qu.append(tmp)问题的关键是如何确定循环结束的条件：用i累计子问题的该操作次数（初始为n），当i=0时循环结束，此时st栈中元素个数就是无法吃午餐的学生数量。解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:

#建立学生队列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记录本轮的学生人数11

while

i>0:12

if

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

#队列最前面学生喜欢栈顶三明治13

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

n-=1

#子问题的人数减少115

i=n

#重置i16

else:

#否则17

tmp=qu.popleft()

#出队后进入队尾18

qu.append(tmp)19

i-=1

#操作次数减少120

return

len(st)上述程序提交结果为通过，运行时间为36ms，消耗空间为15MB。59/832.7优先队列2.7.1优先队列的定义普通队列是一种先进先出的数据结构，在队尾进队元素，在队头出队元素。在优先队列中，元素被赋予优先级，出队的元素总是当前具有最高优先级的元素，实际上普通队列可以看成进队时间越早优先级越高的优先队列。优先队列通常采用堆数据结构来实现，元素值越小越优先出队的优先队列对应小根堆，元素值越大越优先出队的优先队列对应大根堆。60/832.7.2Python中的优先队列Python中提供了heapq模块，其中包含优先队列的基本操作方法，默认创建小根堆。61/83优先队列pqu的主要操作及其说明如下：①heapq.heapify(pqu)：把列表pqu调整为堆。②len(pqu)：返回pqu中的元素个数。③pqu[0]：取堆顶的元素。④heapq.heappush(pqu，e)：将元素e插入到优先队列pqu中，该方法会维护堆的性质。⑤heapq.heappop(pqu)：从优先队列pqu中删除堆顶元素并且返回该元素。⑥heapq.heapreplace(pqu，e)：从优先队列pqu中删除堆顶元素并且返回该元素，同时将e插入并且维护堆的性质。⑦heapq.heappushpop(pqu，e)：将元素e插入到优先队列pqu中，然后从pqu中删除堆顶元素并且返回该元素值。62/831importheapq2pqu=[]

#定义一个优先队列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实战—数据流中的第k大元素（LeetCode703★）问题描述：设计一个找到数据流中第k大元素的类。注意是排序后的第k大元素，不是第k个不同的元素。请实现

KthLargest

类：

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

（2）intadd(intval)：将val插入数据流nums后，返回当前数据流中第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

类用于数据流操作，设计一个小根堆minpq，并始终保证在当前操作后小根堆中保存当前数据流中前k个最大的元素，这样堆顶就是第k大元素。65/83KthLargest(k，nums)：构造函数。对应的过程是先求出nums中元素个数n。

若n<k，将nums中全部元素进入minpq。否则将nums的前k个元素进入minpq，用i遍历剩余的元素，若nums[i]大于堆顶元素，则出堆一个元素，再将nums[i]进堆（相当于用nums[i]替换堆顶元素，但不能直接替换）。66/83add(val)：用于插入val并且返回当前第k大的元素。根据题意做本操作时小根堆中至少有k-1个元素。若minpq中恰好有k-1个元素，则将val进堆。否则若nums[i]大于堆顶元素，则出堆一个元素，再将nums[i]进堆。最后返回堆顶元素。67/831 importheapq2 classKthLargest:3 def__init__(self,k,nums): #构造函数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]上述程序提交结果为通过，运行时间为76ms，消耗空间为19.3MB。70/832.8树和二叉树2.8.1树树是由n（n≥0）个结点组成的有限集合（记为T）。如果n=0，它是一棵空树，这是树的特例。如果n>0，这n个结点中有且仅有一个结点作为树的根（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根的子树。rootT1T2Tm…71/83树特别适合表示具有层次关系的数据。由一棵或者多棵树构成森林，可以将森林看成是树的集合。树的存储要求既要存储结点的数据元素本身，又要存储结点之间的逻辑关系。树的常用存储结构有双亲存储结构、孩子链存储结构和长子兄弟链存储结构。72/832.8.2二叉树1.二叉树的定义二叉树是有限的结点集合。这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。21435673/83在一棵二叉树中如果所有分支结点都有左、右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。0125436满二叉树结点层序编号：(i-1)/2i2i+12i+274/83在一棵二叉树中如果最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。0124375/8321435(a)一棵二叉树53421403521(b)补齐为完全二叉树021124334NIL55(c)二叉树顺序存储结构2.二叉树的存储结构1）二叉树顺序存储结构76/832）二叉树链式存储结构root21∧3∧∧4∧5∧∧2143577/83整数二叉链结点类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实战—二叉树的完全性检验（LeetCode958★★）问题描述：给定一棵二叉树，采用二叉链存储，确定它是否是一棵完全二叉树。

要求设计如下方法：

def

isCompleteTree(self,

root)

->

bool:80/83解

根据完全二叉树的定义，对完全二叉树进行层次遍历时应该满足以下条件：

（1）若某结点没有左孩子，则一定无右孩子。

（2）若某结点缺左或右孩子，则其所有后继结点一定无孩子，或者说其所有后继结点均为叶子结点。

若不满足上述任何一条，则不为完全二叉树。81/831 class

Solution:2

def

isCompleteTree(self,

root)

->

bool:3

ans=True;

#ans表示是否为完全二叉树4

bj=True;

#bj表示是否所有结点均有左右孩子5

qu=deque()

#定义一个队列6

qu.append(root)

#根结点进队82/837

while

qu:8

p=qu.popleft()

#出队一个结点p9

if

p.left==None:

#结点p没有左孩子10

bj=False11

if

p.right!=None:ans=False

#违反(1)12

else:

#结点p有左孩子13

if

bj==True: #所有结点均有左右孩子14

qu.append(p.left)

#左孩子进队15

if

p.right==None:bj=False16

else:qu.append(p.right)17

else:ans=False

#违反(2)18

return

ans上述程序提交结果为通过，运行时间为36ms，消耗空间为14.9MB。83/83第2章工之利器—常用的数据结构及其应用2.1线性表—数组2.3字符串2.2线性表—链表2.4栈2.5队列2.6双端队列2.7优先队列2.8树和二叉树2.9图2.10并查集2.12哈希表2.11二叉排序树和平衡二叉树CONTENTS提纲84/572.9.1图基础1.图的定义2.9图G=(V，E)143012232(a)一个带权有向图G1(b)一个带权无向图G23385431210143521(c)一个不带权无向图G30123485/572.图的存储结构1）邻接矩572）边数组n=4edges=[[0，1，2]，[0，2，4]，[1，2，2]，[2，3，3]，[3，0，1]573）邻接表用二维数组adj作为图的邻接表，对于不带权图，adj[i]表示顶点i的所有出边。adj=[[1，2，3]，[0，2，4]，[0，1，3]，[0，2，4]，[1，3]]0123488/57对于带权图，每一条边用“[v，w]”表示，如adj[i]中包含该元素时表示有一条顶点i到顶点v的权为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）深度优先遍历DFS序列：0，1，2，3，4，5338543121014352190/572）广度优先遍历BFS序列：0，1，2，3，5，4338543121014352191/57一个有n个顶点的连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只包含构成一棵树的n-1条边。一个带权连通图中权值和最小的生成树称为最小生成树。Prim算法。Kruskal算法。4.生成树和最小生成树92/57对于带权图中两个顶点之间的路径可能有多条，把带权路径长度最短的那条路径称为最短路径，其路径长度称为最短路径长度或者最短距离。Dijkstra算法。Floyd算法。5.最短路径93/57在一个有向图G中找一个拓扑序列的过程称为拓扑排序。如果一个有向图拓扑排序产生包含全部顶点的拓扑序列，则该图中不存在环，否则该图中一定存在环。6.拓扑排序94/572.9.2实战—课程表（LeetCode207★★）问题描述：n门课程（编号为0到n-1）的选修关系用prerequisites数组表示，其中每个元素[b，a]表示课程a是课程b的先修课程即a→b。判断是否可能完成所有课程的学习。

例如，n=2，prerequisites=[[1，0]]，表示共有2门课程，课程1的先修课程是课程0，这是可能的，结果为true。

要求设计如下方法：

def

canFinish(self,numCourses,prerequisites)

->

bool:95/57每门课程用一个顶点表示，两门课程之间的先修关系用一条有向边表示，这样构成一个有向图，用邻接表存储。需要注意的是prerequisites中的元素[b，a]对应的有向边为<a，b>。采用拓扑排序思路，用整数n累计拓扑序列中的元素个数，拓扑排序完毕，若n=numCourses则说明没有环，能够完成所有课程的学习，返回True，否则说明存在环，不能完成所有课程的学习，返回False。解96/571 class

Solution:2

def

canFinish(self,numCourses,prerequisites)

->

bool:3

indegree=[0]*numCourses;

#入度数组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()

#定义一个栈st10

for

i

in

range(0,numCourses):

#入度为0的顶点i进栈11

if

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

n=0

#累计拓扑序列的顶点个数13

while

st:14

i=st.popleft()

#出栈顶点i15

n+=116

for

j

in

adj[i]:

#找到i的所有邻接点j17

indegree[j]-=1

#顶点j的入度减少118

if

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

#入度为0的顶点j进栈19

return

n==numCourses上述程序提交结果为通过，运行时间为44ms，消耗空间为15.9MB。98/571.并查集的定义给定n个结点的集合U，结点编号为1～n，再给定一个等价关系R（满足自反性、对称性和传递性的关系称为等价关系。像图中顶点之间的连通性、亲戚关系等都是等价关系），由等价关系产生所有结点的一个划分，每个结点属于一个等价类，所有等价类是不相交的。R2.10并查集2.10.1并查集基础99/57基本运算①Init()：初始化。②Find(x)：查找x（x∈U）结点所属的等价类。③Union(x，y)：将x和y（x∈U，y∈U）所属的两个等价类合并。100/572.并查集的实现Axy并查集的基本存储结构self.parent=[0]*self.MAXN

#并查集存储结构self.rnk=[0]*self.MAXN

#存储结点的秩(近似于高度)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结点的根结点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结点的根结点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的两个集合的合并2

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

if

rx==ry:return

#x和y属于同一棵树时返回4

if

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

self.parent[rx]=ry

#rx结点作为ry的孩子6

else:7

if

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

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

self.rnk[rx]+=19

self.parent[ry]=rx

#ry结点作为rx的孩子105/572.10.2实战—省份数量（LeetCode547★★）问题描述：有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个n×n的矩阵isConnected，其中isConnected[i][j]=1表示第i个城市和第j个城市直接相连，而isConnected[i][j]=0

表示二者不直接相连。求矩阵中省份的数量。

例如，isConnected={{1，1，0}，{1，1，0}，{0，0，1}}，结果为2。

要求设计如下方法：

def

findCircleNum(self,

isConnected)

->

int:106/57城市之间的相连关系（含直接相连和间接相连）是一种等价关系（满足自反性、对称性和传递性）。采用并查集求解，按相连关系划分产生若干子集树，每棵子集树对应一个省份。首先初始化并查集（这里n个城市的编号为0～n-1），由于isConnected是对称矩阵，遍历其上三角部分，对于直接相连的城市对（i，j），调用并查集的合并运算Union(i，j)将i和j所在的子集树合并。最后求并查集中子集树棵数（即满足parent[i]=i的子集树棵数）ans，最后返回ans。解107/571 class

UFS(): #并查集类2

MAXN=20053

def

__init__(self):

4

self.parent=[0]*self.MAXN

#并查集存储结构5

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

#存储结点的秩(近似于高度)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结点的根结点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的两个集合的合并15

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

if

rx==ry:

#x和y属于同一棵树时返回17

return18

if

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

self.parent[rx]=ry

#rx结点作为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结点作为rx的孩子24ryyrxxryyrxxrx的秩不变112/5725 class

Solution:26

def

findCircleNum(self,

isConnected)

->

int:27

n=len(isConnected)28

ufs=UFS() #定义并查集类对象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上述程序提交结果为通过，运行时间为48ms，消耗空间为15.4MB。113/572.11.1二叉排序树1.二叉排序树的定义2.11二叉排序树和平衡二叉树538167中序序列：135678

递增有序114/572.二叉排序树的插入和生成3.二叉排序树的删除4.二叉排序树的查找538167查找6115/572.11.2平衡二叉树通过一些平衡规则和调整操作让一棵二叉排序树既保持BST性质又保证高度较小，即接近O(log2n)的高度，称为平衡二叉树。平衡二叉树：AVL树和红黑树。AVL树的平衡规则是树中每个结点的左、右子树的高度至多相差1。116/57红黑树中每个结点有一个表示颜色的标志，增加外部结点（通常用NIL表示），同时满足以下性质：

（1