Python 标准库与数据结构

Python的标准库提供了丰富的内置数据结构和函数，使用这些工具能为我们提供一套强有力的工具。

需要注意的是，相比C++与Java，Python的一些特点：

1. Python不需要显式声明变量类型
2. Python没有模板(Template)的概念，因为Python是动态类型语言
3. Python的标准库导入更简单，只需要 import 相关模块即可

我们主要介绍以下几种数据结构：

• list：列表
• set：集合
• dict：字典
• queue 和 deque：队列
• heapq：堆

如果在比赛的过程中，忘记了某些函数的使用或者拼写，可能查看比赛机器桌面上的手册，会有这些函数的具体使用方法。

1. 迭代器说明

在Python中，迭代器的概念比C++更简单。所有的Python集合都是可迭代的，不需要显式声明迭代器。我们可以直接使用for循环进行遍历：

numbers = [1, 2, 3, 4, 5]
for num in numbers:print(num)  # 输出: 1 2 3 4 5# 如果需要索引，可以使用enumerate
for index, num in enumerate(numbers):print(f"索引 {index}: {num}")

2. 数据结构详解

2.1 list（列表）

list是Python中最基础的序列数据结构，本身则就具有可变数组的能力。

基本操作：

# 创建列表
lst = []                  # 创建空列表
lst = [1, 2, 3]          # 创建包含元素的列表
lst = [0] * 5            # 创建长度为5的列表，所有元素为0# 常用操作
lst.append(x)            # 在末尾添加元素x
lst.pop()               # 删除并返回末尾元素
lst.pop(i)              # 删除并返回索引i处的元素
lst.insert(i, x)        # 在索引i处插入元素x
len(lst)                # 返回列表长度
lst[i]                  # 访问第i个元素

例子：

numbers = []
numbers.append(1)    # numbers = [1]
numbers.append(2)    # numbers = [1, 2]
numbers.append(3)    # numbers = [1, 2, 3]
print(len(numbers))  # 输出: 3
numbers.pop()        # numbers = [1, 2]

2.2 set（集合）

set是Python中的无序不重复元素集合，实现方式是哈希表，而不是C++中的红黑树。这意味着Python的set操作复杂度是O(1)，而不是O(log n)。

基本操作：

s = set()               # 创建空集合
s.add(x)               # 添加元素x
s.remove(x)            # 删除元素x（元素不存在会报错）
s.discard(x)           # 删除元素x（元素不存在不会报错）
len(s)                 # 返回元素个数
x in s                 # 检查元素是否在集合中

例子：

s = set()
s.add(3)      # s = {3}
s.add(1)      # s = {1, 3}
s.add(2)      # s = {1, 2, 3}
s.add(2)      # s仍然是{1, 2, 3}
print(2 in s)  # 输出: True

2.3 dict（字典）

dict是Python中的键值对容器，同样基于哈希表实现，操作复杂度是O(1)。

基本操作：

d = {}                 # 创建空字典
d[key] = value        # 添加或更新键值对
d.pop(key)            # 删除并返回键对应的值
len(d)                # 返回键值对数量
key in d              # 检查键是否存在

例子：

scores = {}
scores["Alice"] = 95    # 记录Alice的分数
scores["Bob"] = 89      # 记录Bob的分数
print(scores["Alice"])  # 输出: 95

2.4 queue和deque（队列）

Python提供了collections.deque作为双端队列实现，功能比C++的queue更强大。

from collections import deque# 基本操作
q = deque()           # 创建空队列
q.append(x)           # 在右侧添加元素
q.appendleft(x)       # 在左侧添加元素
q.pop()               # 删除并返回右侧元素
q.popleft()           # 删除并返回左侧元素
len(q)                # 返回元素个数

例子：

from collections import deque
q = deque()
q.append(1)     # q = deque([1])
q.append(2)     # q = deque([1, 2])
q.append(3)     # q = deque([1, 2, 3])
print(q[0])     # 输出: 1
q.popleft()     # q = deque([2, 3])

2.5 heapq（堆）

Python通过heapq模块提供堆的功能，默认是小根堆（最小元素在顶部），注意，该模块使用需要一个容器来进行操作。

基本操作：

import heapqheap = []               # 创建空列表作为堆
heapq.heappush(heap, x) # 将元素x压入堆
heapq.heappop(heap)     # 弹出并返回最小元素
heap[0]                 # 查看最小元素
len(heap)               # 返回元素个数

例子：

import heapqheap = []
heapq.heappush(heap, 3)  # heap = [3]
heapq.heappush(heap, 1)  # heap = [1, 3]
heapq.heappush(heap, 4)  # heap = [1, 3, 4]
print(heap[0])           # 输出: 1（最小元素）

3. 补充说明-关于有序集合

Python的set和dict不支持像C++那样的二分查找API（lower_bound、upper_bound），因为它们是基于哈希表实现的。在python组的题目中，也基本不会出现相关的题。

5. 实践与例题

5.1 真题-连连看

很明显，需要求的是每条对角线上的相同数值的对数，如下图：

我们可以枚举每一条45度角对角线，然后进行从上到下、或是从下到上进行遍历，一边遍历一边记录当前数值的数量即可，使用map 进行维护：

def get_l(x, y):global ansmp = {}while x <= n and y <= m:if a[x][y] not in mp:mp[a[x][y]] = 0ans += mp[a[x][y]]  mp[a[x][y]] += 1x += 1y += 1def get_r(x, y):global ansmp = {}while x > 0 and y <= m:if a[x][y] not in mp:mp[a[x][y]] = 0ans += mp[a[x][y]]  # 当 key 不存在 mp 中时，默认值为 0mp[a[x][y]] += 1x -= 1y += 1n, m = map(int, input().split())
a = [[0] * (m + 1) for _ in range(n + 1)]  # 创建二维数组 a，索引从 1 开始
ans = 0# 读取输入
for i in range(1, n + 1):a[i] = [0] + list(map(int, input().split()))  # 读取每一行，并加上前导零，保持从索引 1 开始# 遍历处理主对角线和另外一条对角线
for i in range(1, n + 1):get_l(i, 1)  # 处理主对角线get_r(i, 1)  # 处理另外一条对角线for i in range(2, m + 1):get_l(1, i)get_r(n, i)print(ans * 2)

5.2 哈希表的实现-set

我们直接使用 set 即可

n = int(input())  # 读取输入的整数 n
st = set()  # 创建一个空的集合for _ in range(n):opt, m = input().split()  # 读取操作符和整数 mm = int(m)  # 将 m 转换为整数if opt == 'I':  # 如果操作符是 'I'，则插入元素 mst.add(m)elif m not in st:  # 如果操作符不是 'I' 且 m 不在集合中print("No")else:print("Yes")

5.3 堆与优先队列

我们使用优先队列解决：

import heapqn = int(input())  # 读取操作次数 n
pq = []  # 使用列表来模拟小根堆for _ in range(n):op = input().split()  # 读取操作符if op[0] == "push":x = int(op[1])heapq.heappush(pq, x)  # elif op[0] == "remove":if not pq:print("empty")else:heapq.heappop(pq)  # 弹出堆顶元素elif op[0] == "min":if not pq:print("empty")else:print(pq[0])  # 输出堆顶元素elif op[0] == "print":k = int(op[1])if 0 < k <= len(pq):temp = []for _ in range(k):temp.append(pq[0])  # 获取堆顶元素heapq.heappop(pq)  # 弹出堆顶元素print(*temp)  # 打印出来

5.4 小蓝的图书馆

题，要求我们，每一个作者对应一个书的列表，我们可能使用map，同时套上vector。

mp = {}n = int(input())  # 读取操作次数 nfor _ in range(n):arg = input().split()  # 读取操作指令if arg[0] == "add":book, au = arg[1], arg[2]  # 读取书名和作者if au not in mp:mp[au] = []mp[au].append(book)  # 将书名添加到对应作者的列表中else:au = arg[1]  # 读取作者名if au not in mp:mp[au] = []print(len(mp[au]))  # 输出该作者的书籍数量