算法比赛用到的函数或模块(Python)
·
输入&输出
import sys
sys.setrecursionlimit(10**7) # 设置递归深度，默认为1000，免费午餐，建议使用，以防止递归过深时崩溃
# 允许无限大整数转字符串，防止 n 较大时崩溃
# if hasattr(sys, 'set_int_max_str_digits'):
# sys.set_int_max_str_digits(0)
input = sys.stdin.readline # 替换 input，免费午餐，建议使用，以提高读取大规模数据的效率
n,d=map(int,input().split()) # 输入接收形式，列表、字典等用推导式
list_q = [list(map(int, input().split())) for _ in range(n)]
# 输出大量数据时，先存入列表再一次性 join，或者：
# sys.stdout.write(str(ans) + '\n')
# 当输出数据规模>10^6时，应该分批输出
print(" ".join(map(str, list_q)))
print(*list_q, sep=" ")
for循环
students = ['Alice', 'Bob', 'Charlie']
scores = [90, 80, 85]
for student, score in zip(students, scores):
print(student, score)
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transposed_matrix = [list(row) for row in zip(*matrix)]
print(transposed_matrix)
f - strings
f"{ 变量名 [=] [ : [填充][对齐][符号][宽度][分隔符][.精度][#][类型] ] }"
=:自动打印=前的变量名或字面量和=后的值，适合调试使用填充字符：指定单个字符作为填充（需配合对齐符号使用）对齐方式：<（左）、^（中）、>（右）符号：仅对数字类型有效，指定正数的前缀（+、-、空格）宽度：输出的最小宽度，不足部分用填充字符（默认为空格）填充分隔符：仅可指定,(千分位)或_.精度：指定f类型的小数位数或s类型的最大字符数#：用于显示 0b、0o、0x 前缀或者强制显示小数点（即使没有小数部分）类型：d、f、e、E、%、s、b、o、x等
num = 12345.6789
print(f"严格遵守公式顺序：填充(*) 对齐(^) 前缀(#) 宽度(20) 分隔符(,) 精度(.2) 类型(f)\n{num:*^#20,.2f}")
# 进制转换
n = 10
print(f"{n:b}") # 二进制: 1010
print(f"{n:o}") # 八进制: 12
print(f"{n:x}") # 十六进制(小写): a
print(f"{n:X}") # 十六进制(大写): A
# 前缀（#）表示法
print(f"{n:#b}") # 二进制: 0b1010
print(f"{n:#o}") # 八进制: 0o12
print(f"{n:#x}") # 十六进制(小写): 0xa
print(f"{n:#X}") # 十六进制(大写): 0XA
# int(x,base)函数进行进制转换
# x：要转换的字符串或数字
# base：进制（2-36），默认10
print(f"{int('1010', 2):o}") # 二进制转八进制： 12
print(f"{int('12', 8):x}") # 八进制转十六进制： a
无需导包，直接用的方法
这些方法都在builtins模块中，以使用以下命令查看所有内置函数、常量和异常
import builtins dir(builtins) help(builtins)
print(f"{abs(-10)=}") # abs() 几乎可以完全替代 math.fabs(),且更好
print(all([1 > 0, 1 > 0, 1 > 0])) # True
print(any([1 > 0, 0 > 0, 0 > 0])) # True
print(complex(3, 4)) # output:(3+4j)
print(divmod(10, 3)) # 10/3=3···1 output:(3,1)
print(f"{eval('5 * 10')=}") # 执行字符串中的代码
print(f"{len([1, 2, 3])=}") # output:len([1, 2, 3])=3
print(max(1, 2, 3)) # output:3
print(min(1, 2, 3)) # output:1
print(pow(2, 3)) # # pow() 几乎可以完全替代 math.pow(),且更好
print(pow(2, 3, 5)) # 快速幂 不要写 2**3%5 output:3
print(*range(10, 0, -1)) # output:10 9 8 7 6 5 4 3 2 1
# 四舍六入五成双（银行家合入法），四舍五入用math.floor(x + 0.5)实现
print(round(2.5)) # output:2
print(round(3.5)) # output:4
print(round(2.3456, 2)) # output:2.35
# 接受可迭代对象（如列表、元组、字符串等），返回一个新的已排序列表；与list.sort()不同，list.sort()是在原列表上进行排序
print(sorted((3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5), key=None, reverse=False))
print(sum([1, 2, 3, 4])) # output:10
# zip()将多个可迭代对象中对应的元素打包成一个个元组，
# 然后返回由这些元组组成的一个可迭代对象
# 返回值是迭代器对象
print(list(zip([1, 2, 3], ["a", "b", "c"]))) # output:[(1, 'a'), (2, 'b'), (3, 'c')]
print(*list(zip([1, 2, 3], ["a", "b", "c"]))) # output:(1, 'a') (2, 'b') (3, 'c')
# 将一个可迭代对象组合为一个索引序列，同时列出数据和数据下标。
# 这个函数返回的是一个枚举对象，该对象是一个可以迭代的类型。
# 基本语法为enumerate(iterable, start = 0)，start指定索引的起始值，默认为0
for index, (element1, element2) in enumerate(zip([1, 2], ["a", "b"]), start=0):
print(index, element1, element2)
# output:
# 0 1 a
# 1 2 b
# reversed(iterable)返回一个反向的迭代器对象
print(list(reversed([1, 2, 3]))) # output:[3, 2, 1]
常用字符串方法
字符串是 不可变对象 (Immutable)，所以在字符串的“增、删、改、查”中，“增、删、改”本质上都是在做“字符串拼接”并产生一个新对象
- 增
可以使用 + 对字符串进行拼接，但是f-strings可以全场景替代 + 且速度略快；批量处理列表，join 比 f-strings更高效
str1 = '123' str2 = 'abc' str1 = "".join([str1, str2]) print(str1) # output: 123abc - 删
print("123 abc".replace("3 a", "")) # output:12bc print('123 abc'[2:5]) # output:3 a # strip()：用于去除字符串开头和结尾的指定字符，默认为空白字符（包括空格、制表符、换行符等） print(' a b c '.strip()) # output:a b c # 只去开头 print(' a b c '.lstrip()) # output:a b c # 只去结尾 print(' a b c '.rstrip()) # output: a b c - 改
print('abc abc'.replace('a', 'A')) # output:Abc Abc # 根据转换表（通过maketrans()函数创建）来替换字符串中的字符 trans_table = str.maketrans("abc", "***") print(trans_table) # {97: 42, 98: 42, 99: 42} print('abc123'.translate(trans_table)) # output:***123 - 查
# 查找子字符串第一次出现的位置。 # 如找到，返回起始索引；如没找到，返回-1 # find()从左开始查找，rfind()从右开始查找 print('abc abc'.find('a')) # output:0 print('abc abc'.rfind('abc')) # output:4 # index(),rindex与find(),rfind()对应， # 区别在于没找到，前两个引发ValueError异常，后两个返回-1 print('abc abc'.index('abc')) # output:0 print('abc abc'.rindex('abc')) # output:4 - 其它
print(len("abc")) # output:3 print("abc abc".count("abc")) # output:2 # ord()返回单个字符的 Unicode 码点,与chr对应 print(ord("A")) # output:65 print(chr(65)) # output:A # split()从左开始分割，rsplit()从右开始分割 print("a,b,c".split(",")) # output:['a', 'b', 'c'] print("a,b,c".rsplit(",")) # output:['a', 'b', 'c'] print("ABC".lower()) # output:abc print("abc".upper()) # output:ABC print("abc ABC".swapcase()) # 大小写互换 output:ABC abc print("abc abc".title()) # 单词的首字母转换为大写，其余小写 output:Abc Abc print("aBC ABC".capitalize()) # 首字母转换为大写，其余小写 output:Abc abc print("abc abc".startswith("abc")) # 是否以指定的子字符串开头 output:True print("abc abc".endswith("abc")) # 是否以指定的子字符串结尾 output:True print("abc".isalpha()) # 所有字符是否都是字母 output:True print("123".isdigit()) # 所有字符是否都是数字 output:True print("Abc".isupper()) # 是否都是大写字母 output:False print("Abc".islower()) # 是否都是小写字母 output:False print("Abc".istitle()) # 首字母是否是大写 output:True print(" \t\n\r ".isspace()) # 是否都是空白字符 output:True
常用列表方法
-
增
list = [1, 2] list.append(3) # 在列表的末尾添加一个元素 list.extend((4, 5, 6)) # 将一个可迭代对象中的元素逐个添加到列表的末尾 如 '456' [4,5,6] list.insert(1, 7) # 在索引1的位置插入元素7 print(list) # output:[1, 7, 2, 3, 4, 5, 6] -
删
list = [1, 2, 3, 2] list.remove(2) # 删除第一个匹配的指定元素，如果列表中不存在该元素，则会抛出异常。 print(list) # output:[1, 3, 2] print(list.pop(1)) # 删除并返回列表中索引2位置的元素 output:3 print(list) # output:[1, 2] -
改
my_list = [1, 2, 3] my_list[1] = 4 print(my_list) # output:[1, 4, 3] my_list[1:3] = [2, 3] print(my_list) # output:[1, 2, 3] -
查
# index()用于返回列表中第一个匹配的指定元素的索引。 # 如果列表中不存在该元素，则会抛出异常。 print([1, 2, 3, 2].index(2)) # output:1 -
其它
list = [3, 1, 4, 1, 5, 9] print(list.count(1)) # 统计列表中指定元素出现的次数 list.sort( key=None, reverse=False ) # 对列表中的元素进行排序，默认是升序排序即reverse=False print(list) # output:[1, 1, 3, 4, 5, 9] list.reverse() # 将列表中的元素反转 print(list) # output:[9, 5, 4, 3, 1, 1] names = ["Smith, John", "Doe, Jane", "Johnson, Adam"] names.sort(key=lambda item: item.split(", ")[1]) print(names) students = [ {"name": "Alice", "grade": 85}, {"name": "Bob", "grade": 90}, {"name": "Charlie", "grade": 80}, ] students.sort(key=lambda student: student["grade"]) print(students) """ output:[{'name': 'Charlie', 'grade': 80}, {'name': 'Alice', 'grade': 85}, {'name': 'Bob', 'grade': 90}] """
常用字典方法
dict：有序、键唯一、值允许重复、可变（Mutable）
- 增
my_dict1 = {'a': 1, 'b': 2} my_dict2 = {'b': 3, 'c': 4} my_dict1.update(my_dict2) # 将一个字典中的键-值对更新到另一个字典中 print(my_dict1) # output:{'a': 1, 'b': 3, 'c': 4} - 删
my_dict = {"a": 1, "b": 2, "c": 3} value = my_dict.pop("a") # pop()用于移除字典中指定键的键值对，并返回被移除的值。 print(my_dict) # output:{'b': 2, 'c': 3} print(value) # output:1 try: value2 = my_dict.pop("d") # 如果键不存在，会引发KeyError异常 except KeyError: print("键不存在") # output:键不存在 value3 = my_dict.pop("e", 0) # 可以通过第二个参数指定不存在时的默认返回值 print(value3) # output:0 my_dict = {"a": 1, "b": 2, "c": 3} item = my_dict.popitem() # popitem()移除(以后进先出的顺序)并返回字典中的一个键-值对 print(my_dict) # output:{'a': 1, 'b': 2} print(item) # output:('c', 3) my_dict.clear() # clear()用于清空字典中的所有键 - 值对，将字典变为一个空字典 print(my_dict) # output:{} - 改
# setdefault()设置键值对，如果键不存在，在表中增添键值对，返回默认值，默认值可以修改 dict1 = {"a": 1, "b": 2} print(dict1.setdefault("c")) # output:None print(dict1) # output:{'a': 1, 'b': 2, 'c': None} print(dict1.setdefault("d", 4)) # output:4 print(dict1) # output:{'a': 1, 'b': 2, 'c': None, 'd': 4} - 查
dict1 = {'a': 1, 'b': 2} # get()获取键对应值，不改变字典，如果键不存在，返回默认值，默认值可以修改 print(dict1.get('c')) # output:None print(dict1.get('c', 3)) # output:3 print(dict1) # output:{'a': 1, 'b': 2} - 其它
dict1 = {"a": 1, "b": 2, "c": 3} # keys()返回一个可迭代视图对象,表示字典中的所有键 print(dict1.keys()) # output:dict_keys(['a', 'b', 'c']) # values()返回一个可迭代视图对象,表示字典中的所有值 print(dict1.values()) # output:dict_values([1, 2, 3]) # items()返回一个可迭代视图对象,其中的每个元素是一个包含键和值的元组 print(dict1.items()) # output:dict_items([('a', 1), ('b', 2), ('c', 3)]) for key in dict1.keys(): print(key) # output: # a # b # c for value in dict1.values(): print(value) # output: # 1 # 2 # 3 for item in dict1.items(): print(item) # output: # ('a', 1) # ('b', 2) # ('c', 3) for key, value in dict1.items(): print(key, value) # output: # a 1 # b 2 # c 3
常用集合方法
set：无序、不允许重复元素、可变（Mutable）
-
增
list1 = {1, 2, 3} list1.add(4) # 向集合中添加一个元素 print(list1) # {1, 2, 3, 4} list1.update([5, 6 ,7]) # 将一个可迭代对象中的元素添加到集合中 print(list1) # {1, 2, 3, 4, 5, 6, 7} -
删
list1 = {1, 2, 3} # 删除指定的元素,如果元素不存在，会抛出KeyError异常。 print(list1.remove(3)) # output:None # 删除指定的元素,如果元素不存在，不会会抛出异常。 print(list1.discard(3)) # output:None -
改
没有直接修改方法，可以通过删+增进行间接修改
-
查
print(2 in {1, 2, 3}) # output:True -
其它
print({1, 2, 3} & {3, 4, 5}) # 求交集，返回一个新的集合 output:{3} print({1, 2, 3} | {3, 4, 5}) # 求并集，返回一个新的集合 output:{1, 2, 3, 4, 5} print({1, 2, 3} - {3, 4, 5}) # 求差集，返回一个新的集合 output:{1, 2} print({1, 2, 3} ^ {3, 4, 5}) # 求对称差集，返回一个新的集合 output:{1, 2, 4, 5} print({1, 2, 3} <= ({1, 2, 3})) # 检查一个集合是否是另一个集合的子集 output:True print({1, 2, 3} < ({1, 2, 3})) # 检查一个集合是否是另一个集合的真子集 output:True
常用元组方法
tuple：有序、允许重复元素、不可变（Immutable）
因为tuple是不可变（Immutable）的，它没有增、删、改的方法
- 查
print((2, 1, 2).index(2)) # index() 返回元组中第一个匹配的指定元素的索引 output:0 - 其它
print((2, 1, 2).count(2)) # count() 统计元组中指定元素出现的次数 output:2
deque类
-
增
from collections import deque my_deque = deque([1, 2, 3], maxlen=5) # 创建一个最大长度为5的双端队列 my_deque.insert(1, 4) # 在索引为1的位置插入元素4 print(my_deque) # output：deque([1, 4, 2, 3], maxlen=5) my_deque.append(5) # append()在deque的右端（尾部）添加一个元素 print(my_deque) # output：deque([1, 4, 2, 3, 5], maxlen=5) my_deque.appendleft(6) # appendleft()在deque的左端（头部）添加一个元素 print(my_deque) # output：deque([6, 1, 4, 2, 3], maxlen=5) my_deque.extend([7, 8]) # 在deque的右端（尾部）扩展一个可迭代对象 print(my_deque) # output：deque([4, 2, 3, 7, 8], maxlen=5) my_deque.extendleft([9, 10]) # 在deque的左端（头部）以逆序的方式扩展一个可迭代对象 print(my_deque) # output：deque([10, 9, 4, 2, 3], maxlen=5) -
删
from collections import deque my_deque = deque([1, 2, 3, 1, 2, 3]) # 创建一个双端队列deque last_element = my_deque.pop() # 删除并返回deque的右端（尾部）的元素 print(last_element) # output：3 print(my_deque) # output：deque([1, 2, 3, 1, 2]) first_element = my_deque.popleft() # 删除并返回deque的左端（头部）的元素 print(first_element) # output：1 print(my_deque) # output：deque([2, 3, 1, 2]) my_deque.remove(2) # 从双端队列deque中移除第一个匹配的元素 print(my_deque) # output：deque([3, 1, 2]) -
改
from collections import deque my_deque = deque([1, 2, 3]) # 使用索引访问deque中的元素 my_deque[0] = 4 print(my_deque) # output:deque([4, 2, 3]) # pop()+inset()/append()和popleft()+inset()/appendleft()也可以实现修改 -
查
from collections import deque my_deque = deque([1, 2, 3]) # 使用索引访问deque中的元素 print(my_deque.index(2)) # output:1 -
其它
from collections import deque my_deque = deque([1, 2, 3]) print(len(my_deque)) # output:3 my_deque.clear() # 清空双端队列中的所有元素 print(len(my_deque)) # output:0 my_deque = deque([1, 2, 3, 4, 5]) my_deque.rotate(1) # 将deque中的元素旋转,正数向右旋转，负数向左旋转 print(my_deque) # output：deque([5, 1, 2, 3, 4]) my_deque.rotate(-2) print(my_deque) # output：deque([2, 3, 4, 5, 1]) my_deque1 = deque([1, 2, 3, 1, 2, 3]) my_deque2 = my_deque1.copy() print(my_deque2) # output:deque([1, 2, 3, 1, 2, 3]) print(my_deque2.count(1)) # 计算指定元素在双端队列中出现的次数 output:2 my_deque2.reverse() # 反转双端队列中的元素顺序 print(my_deque2) # output:deque([3, 2, 1, 3, 2, 1])
需要掌握的模块或函数
import bisect
import copy
import functools
import heapq
import itertools
import math
import sys
from collections import Counter, defaultdict, deque
from datetime import datetime
# 重要程度排序：
# 必用：sys（快速输入输出）、collections.deque（BFS、队列、栈、滑动窗口）
# 高频：collections.defaultdict（图邻接表、计数、分组）、heapq（Top K、Dijkstra、优先队列、堆排序）、collections.Counter（频率统计、字母计数、找众数）、itertools（排列、组合、笛卡尔积）、math（gcd、sqrt、ceil、floor）
# 中频：bisect（二分查找、插入有序列表、等级判定）、functools（递归优化、自定义排序）、copy（深拷贝）
# 低频：datetime（日期计算）、math特殊函数（comb、perm）、itertools高级操作（前缀和、分组）
math
import math
# 返回大于或等于x的最小整数
print(math.ceil(4.1)) # output:5
# 返回小于或等于x的最大整数
print(math.floor(4.9)) # output:4
# 返回x的平方根。x必须大于等于 0，否则会产生ValueError
print(math.sqrt(9)) # output:3.0
# 返回e的x次幂
print(math.exp(1)) # 2.718281828459045
# 则返回以base为底x的对数,如果没有指定base,则以e为底
print(math.log(10)) # 2.302585092994046
print(math.log(100, 10)) # 2.0
# 分别返回x（弧度制）的正弦、余弦和正切值
print(math.sin(math.pi / 2)) # 1.0
print(math.cos(0)) # 1.0
print(math.tan(math.pi / 4)) # 0.9999999999999999
# 分别返回x的反正弦、反余弦和反正切值（结果是弧度制）
print(math.asin(1)) # 1.5707963267948966
print(math.acos(0)) # 1.5707963267948966
print(math.atan(1)) # 0.7853981633974483
# 将弧度转换为角度
print(math.degrees(math.pi / 2)) # 90.0
# 将角度转换为弧度
print(math.radians(90)) # output:1.5707963267948966
# 返回n!
print(math.factorial(5)) # output:120
# 返回a和b的最大公约数
print(math.gcd(12, 18, 3)) # output:3
# 从5个元素中取出3个元素的组合数
print(math.comb(5, 3)) # output:10
# 计算两个相同维度的点之间的欧几里得距离
print(math.dist((1, 2), (4, 6))) # output:5.0
print(math.fmod(10, 2)) # output:0.0
heapq
heapq的底层就是普通的Python list,使用type()也返回list类型，这与deque不同
import heapq
# 创建堆 方法1：从空堆开始
# heap = []
# 创建堆 方法2：从现有列表舰队（推荐，O(n)）
heap = [4, 3, 2, 1]
heapq.heapify(heap) # 将列表原地转换为堆，方法1的空列表不需要heapify
print("初始堆:", heap) # [1, 3, 2, 4]（不一定有序，但满足堆性质）
# 入堆
heapq.heappush(heap, 6)
heapq.heappush(heap, 5)
print("入堆后:", heap) # [1, 3, 2, 4, 6, 5]（不一定有序，但满足堆性质）
# 查看最小值（不删除）
min_val = heap[0]
print("最小值:", min_val) # 1
# 堆大小
size = len(heap)
print("堆大小:", size) # 6
# 判空
is_empty = len(heap) == 0
print("是否为空:", is_empty) # False
# 出堆（弹出最小值）
min_val = heapq.heappop(heap)
print("弹出:", min_val) # 1
print("出堆后:", heap) # [2, 3, 5, 4, 6]
# heapreplace = pop + push（更高效）
old_min = heapq.heapreplace(heap, 7)
print("弹出:", old_min) # 2
print("堆:", heap) # [3, 4, 5, 7, 6]
# heappushpop = push + pop（更高效）
new_min = heapq.heappushpop(heap, 0)
print("推入0后弹出:", new_min) # 0
print("堆:", heap) # [3, 4, 5, 7, 6]
largest_3 = heapq.nlargest(3, heap)
smallest_3 = heapq.nsmallest(3, heap)
print("堆中最大的3个元素:", largest_3) # [7, 6, 5]
print("堆中最小的3个元素:", smallest_3) # [3, 4, 5]
# 参数 key 用于指定比较键
students = [
{"name": "Alice", "score": 85},
{"name": "Bob", "score": 92},
{"name": "Charlie", "score": 78},
{"name": "David", "score": 90},
]
top_two_students = heapq.nlargest(2, students, key=lambda s: s["score"])
print(top_two_students)
# output:[{'name': 'Bob', 'score': 92}, {'name': 'David', 'score': 90}]
itertools
import itertools
list1 = [1, 2, 3]
list2 = ["a", "b", "c"]
# 返回可迭代对象中元素的所有排列
# 如果r指定长度，则返回指定长度的排列
print(f"{'itertools.permutations':=^80}")
for i in itertools.permutations(list1, r=3):
print(i, end=" ")
# output: (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
print(f"\n\n{'itertools.combinations':=^80}")
# 1. 普通组合（比如从3个人里选2个去比赛）
print(list(itertools.combinations(list1, 2))) # output: [(1, 2), (1, 3), (2, 3)]
print(f"\n{'itertools.combinations_with_replacement':=^80}")
# 2. 可重复组合（比如买2个水果，可以买2个都是苹果）
print(list(itertools.combinations_with_replacement(list1, 2)))
# output: [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
print(f"\n\n{'itertools.product':=^80}")
# 不指定repeat,计算多个可迭代对象的笛卡尔积
# 指定repeat，则计算可迭代对象自身的笛卡尔积repeat次
for i in itertools.product(list1, list2):
print(i, end=" ")
# output: (1, 'a') (1, 'b') (1, 'c') (2, 'a') (2, 'b') (2, 'c') (3, 'a') (3, 'b') (3, 'c')
print(f"\n\n{'itertools.product':=^80}")
# 指定repeat，则计算可迭代对象自身的笛卡尔积repeat次
for i in itertools.product(list1, repeat=2):
print(i, end=" ")
# output: (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)
print(f"\n\n{'itertools.chain':=^80}")
# 将多个可迭代对象连接成一个单一的迭代器
for i in itertools.chain(list1, list2):
print(i, end=" ")
# output: 1 2 3 a b c
print(f"\n\n{'itertools.accumulate':=^80}")
result = itertools.accumulate(list1, lambda x, y: x * y) # 默认是求和
print(list(result)) # output:[1, 2, 6]
print(f"\n{'itertools.groupby':=^80}")
for char, group in itertools.groupby("AAAABBBCCDAA"):
# group 也是一个迭代器，需要转成 list 才能看长度
print(f"{char}: {len(list(group))}", end=" ")
# output: A: 4 B: 3 C: 2 D: 1 A: 2
# 注意：它只管连续的！最后的 AA 会被单独分成一组。
print(f"\n\n{'itertools.count':=^80}")
# 创建一个从start开始，以step为步长的无限迭代器
for i in itertools.count(1, 2): # count(start=0, step=1)
if i > 10:
break
print(i, end=" ")
# output:1 3 5 7 9
print(f"\n\n{'itertools.cycle':=^80}")
# 对一个可迭代对象进行无限循环
count = 0
for i in itertools.cycle("ABC"): # cycle(iterable)
if count > 5:
break
print(i, end=" ")
count += 1
# output:A B C A B C
print(f"\n\n{'itertools.repeat':=^80}")
# 重复object指定的times次（如果不指定times，则无限重复）
for i in itertools.repeat("Hello", 3):
print(i, end=" ")
# output:Hello Hello Hello
functools
lru_cache
from functools import lru_cache
@lru_cache(None) # 加上这一行，这题就稳了
def dfs(state):
if 终止条件: return 0
# ... 各种递归调用
return result
sort函数key参数使用 cmp_to_key 时：cmp_to_key 的唯一作用就是接收一个
双参数比较函数（即cmp_to_key与双参数比较函数是固定搭配）
cmp_to_key()函数专用于解决最大数问题
题目描述： 给定一组正整数，相邻连接复合成一个最大的整数
from functools import cmp_to_key
def compare(a, b):
if a + b > b + a:
return -1 # a 排在 b 前（降序）
elif a + b < b + a:
return 1 # b 排在 a 前
else:
return 0
nums = [3, 30, 34, 5, 9]
strs = [str(x) for x in nums]
strs.sort(key=cmp_to_key(compare))
result = "".join(strs).lstrip("0") or "0"
print(result) # "9534330"
bisect
import bisect
# 1.必掌握：用 bisect 查找“前驱”和“后继”
arr = [10, 20, 20, 30, 30]
x = 20
print(f"第一个 >= {x} 的位置: {bisect.bisect_left(arr, x)}") # 1
print(f"第一个 > {x} 的位置: {bisect.bisect_right(arr, x)}") # 3
# 2.进阶用法：查表/等级判定
def grade(score):
breakpoints = [60, 70, 80, 90]
grades = "EDCBA"
# bisect 返回插入位置，正好对应 grades 的索引
i = bisect.bisect_right(breakpoints, score)
return grades[i]
print([grade(s) for s in [55, 60, 75, 89, 95]]) # output: ['E', 'D', 'C', 'B', 'A']
collections
Counter类
from collections import Counter
list1 = [3, 2, 1, 2, 1, 1]
# Counter是一个容器，用于对可哈希（散列）对象的元素进行计数
counter_obj = Counter(list1)
print(counter_obj) # output:Counter({1: 3, 2: 2, 3: 1})
print(counter_obj[1]) # Counter对象可以看作是一个字典子类，可以使用索引访问 output:3
# most_common()返回一个按照元素计数从高到低排序的元组列表
print(counter_obj.most_common()) # output:[(1, 3), (2, 2), (3, 1)]
# 返回出现次数最多的前2个元素及其计数的元组列表
print(counter_obj.most_common(2)) # output:[(1, 3), (2, 2)]
elements_iter = counter_obj.elements() # elements()方法返回一个迭代器
for element in elements_iter: # 该迭代器会根据元素的计数重复返回元素
print(element, end=" ") # output:3 2 2 1 1 1
counter_obj.clear() # clear()方法用于清空Counter对象中的所有元素计数
print("\nAfter clear:", counter_obj) # output:After clear: Counter()
# 传入一个可迭代对象，将其中元素的计数添加到当前Counter对象中
counter_obj.update([3, 2, 1, 2, 1, 1])
print(counter_obj) # output: Counter({1: 3, 2: 2, 3: 1})
defaultdict
from collections import defaultdict
# 它的主要作用是在访问时字典中不存在的键时，能够返回一个默认值
# 访问前字典是没有默认值的
# 而不是像普通字典那样抛出KeyError异常。
my_dict = defaultdict(int) # int()的默认值是0
print(my_dict) # output:defaultdict(<class 'int'>, {})
my_dict["key1"] += 1
print(my_dict["key1"]) # output:1
print(my_dict["key2"]) # output:0
my_list_dict = defaultdict(list) # list()的默认值是一个空列表
my_list_dict["key1"].append(1)
print(my_list_dict["key1"]) # output:[1]
print(my_list_dict["key2"]) # output:[]
# 自定义默认值函数
def custom_default():
return ["default value"]
my_custom_dict = defaultdict(custom_default)
print(my_custom_dict["key1"]) # output:['default value']
# 统计一个列表中元素出现的次数，使用defaultdict比使用普通字典更简洁
# 使用defaultdict
my_list = [1, 2, 3, 1, 2]
# 使用defaultdict
count_dict = defaultdict(int)
for i in my_list:
count_dict[i] += 1
print(count_dict) # output:defaultdict(<class 'int'>, {1: 2, 2: 2, 3: 1})
print(dict(count_dict)) # output:{1: 2, 2: 2, 3: 1}
# 使用普通字典
count_dict = {}
for i in my_list:
if i in count_dict:
count_dict[i] += 1
else:
count_dict[i] = 1
print(count_dict) # output:{1: 2, 2: 2, 3: 1}
deque
deque与list的区别：
- deque是双端队列，底层实现是分段连续块+指针数组，左右端操作效率属于同一数量级别（右端略微快），因此它有appendleft/append和popleft/pop方法。
- list的底层实现是一个动态数组，所以右端操作效率远高于左端操作，因此它没有appendleft和popleft方法。
- 所以当只涉及右端操作时，list和deque的性能差不多；当涉及左端操作时，deque的性能远优于list。
栈
from collections import deque
# 1.deque实现的栈：
# deque是双端队列，底层实现是分段连续块+指针数组，左右端操作效率属于同一数量级别（右端略微快），因此它有appendleft/append和popleft/pop方法。
# 所以deque实现的栈的栈顶可以在右端，也可以在左端。
stack = deque(maxlen=None)
stack.append(1)
stack.append(2)
print("入栈后:", stack)
top = stack[-1] if stack else None
print("栈顶元素:", top)
is_empty = len(stack) == 0
print("栈是否为空:", is_empty)
size = len(stack)
print("栈的大小:", size)
stack.pop()
print("出栈后:", stack)
# 2.list实现的栈：
# list的底层实现是一个动态数组，所以右端操作效率远高于左端操作，因此它没有appendleft和popleft方法。
# 所以list实现的栈的栈顶在右端，入栈和出栈都在右端进行。
stack = []
stack.append(1)
stack.append(2)
print("入栈后:", stack)
top = stack[-1] if stack else None
print("栈顶元素:", top)
is_empty = len(stack) == 0
print("栈是否为空:", is_empty)
size = len(stack)
print("栈的大小:", size)
stack.pop()
print("出栈后:", stack)
队列
from collections import deque
# 普通队列和双端队列的区别：
# 1.普通队列只能在一端入队，在另一端出队；
# 2.双端队列可以在两端入队和出队。
# 可以根据需要选择append/appendleft和pop/popleft方法来实现不同类型的队列。
queue = deque()
queue.append(1)
queue.append(2)
print(f"入队后的队列: {queue}") # output: deque([1, 2])
print(f"查看队首元素: {queue[0]}") # output: 1
print(f"查看队尾元素: {queue[-1]}") # output: 2
print(f"队列是否为空: {len(queue) == 0}") # output: False
print(f"队列大小: {len(queue)}") # output: 2
queue.popleft()
print(f"出队后的队列: {queue}") # output: deque([2])
并查集（Union-Find）问题
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1)) # 父节点数组
self.rank = [0] * (n + 1) # 秩（树的高度）
self.count = n # 集合数量
def find(self, x):
"""查找根节点 + 路径压缩"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
"""合并两个集合（按秩合并）"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # 已经在同一集合
# 按秩合并：将矮树合并到高树下
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1 # 集合数量减少
return True # 合并成功
def connected(self, x, y):
"""判断两个元素是否连通"""
return self.find(x) == self.find(y)
# ========== 示例1：基本使用 ==========
print("=== 示例1：基本使用 ===")
uf = UnionFind(10)
# 合并操作
uf.union(1, 2)
uf.union(2, 3)
uf.union(4, 5)
uf.union(6, 7)
uf.union(7, 8)
# 查询连通性
print(f"1和3连通吗？ {uf.connected(1, 3)}") # True
print(f"1和4连通吗？ {uf.connected(1, 4)}") # False
print(f"6和8连通吗？ {uf.connected(6, 8)}") # True
# 合并不同集合
uf.union(3, 4)
print(f"合并后1和4连通吗？ {uf.connected(1, 4)}") # True
print(f"当前集合数量： {uf.count}") # output: 4
邻接表（存储结构）
用于实现图和树（无环连通图）
import sys
sys.setrecursionlimit(10**7) # 设置递归深度，默认为1000
input = sys.stdin.readline
# n个点, m条边
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)] # 下标从1开始比较直观
for _ in range(m):
u, v, w = map(int, input().split())
adj[u].append((v, w)) # 存(终点, 权重)
# adj[v].append((u, w)) # 无向图才加这行
datetime
from datetime import date, datetime, timedelta
# 1. 创建日期对象
d = date(2026, 3, 30)
# 2. 提取属性 (用于判断条件)
print(d.year, d.month, d.day)
print(d.weekday()) # 0代表周一, 6代表周日（注意：不同于ISO）
print(d.isoweekday()) # 1代表周一, 7代表周日（更符合直觉）
# 3. 日期的加减 (核心技巧：利用 timedelta 遍历)
# 比如：求 100 天后是哪一天
new_d = d + timedelta(days=100)
print(new_d) # output:2026-07-08
# datetime 几乎用不到
t1 = datetime(2023, 1, 1, 12, 0, 0)
t2 = datetime(2023, 2, 2, 13, 30, 0)
diff = t2 - t1
print(diff.days) # 相差的天数部分: 1
print(diff.seconds) # 去掉天数后剩余的秒数: 5400 (1.5小时)
print(diff.total_seconds()) # 总共相差的秒数: 2770200.0
更多推荐
7
0- 0
已为社区贡献6条内容
所有评论(0)