算法题笔记（自用）——Python

目录

一. 进制&位运算&ASCAII

二. format格式化输出

1. 基本用法

2. 位置参数

3. 格式化数字

4. 对齐和填充

5. 格式化二进制、八进制、十六进制

6. 格式化百分比

7. 格式化科学计数法

8. 格式化字符串字面量（f-string）

三. 字符串

使用 join() 方法拼接字符串列表。

使用 find() 查找子字符串的位置（返回第一个匹配的索引，未找到返回 -1）。

 使用 index() 查找子字符串的位置（未找到会抛出异常）。

使用 replace() 替换子字符串。

使用 split() 按分隔符分割字符串。

使用 upper() 转换为大写。

使用 strip() 去除两端空白。

使用 isalpha() 判断是否全为字母。

使用 isdigit() 判断是否全为数字。

使用 isalnum() 判断是否全为字母或数字。

使用 ljust() 左对齐并填充。使用 rjust() 右对齐并填充。使用 center() 居中对齐并填充。

使用 count() 统计子字符串出现的次数。

使用切片反转字符串。

使用 zfill() 在字符串左侧填充零。

四. 文件操作

1. 打开文件

2. 文件打开模式

3. 读取文件

4. 写入文件

5. 关闭文件

6. 文件指针操作

五. 集合

使用 add() 添加单个元素。

使用 update() 添加多个元素。

使用 remove() 删除指定元素（元素不存在会报错）。

使用 discard() 删除指定元素（元素不存在不会报错）。

使用 pop() 随机删除并返回一个元素。

使用 clear() 清空集合。

使用 union() 或 | 计算两个集合的并集。

使用 intersection() 或 & 计算两个集合的交集。

使用 difference() 或 - 计算两个集合的差集。

使用 symmetric_difference() 或 ^ 计算两个集合的对称差集（仅存在于一个集合中的元素）。

 使用 issubset() 或 <= 判断一个集合是否是另一个集合的子集。

 使用 < 判断一个集合是否是另一个集合的真子集。

使用 issuperset() 或 >= 判断一个集合是否是另一个集合的超集。

使用 > 判断一个集合是否是另一个集合的真超集。

使用 copy() 复制集合。

六. 库函数

bisect

itertools

collections

functools

string

sys

math

heapq

 datetime

Decimal

七. 模板

1. 二分查找：

2. 二位前缀和 & 差分

 3.快速幂

4.dijkstra

5.弗洛伊德

6.并查集

 7.树状数组

 8.素数预处理

八. 其他用法

---

一. 进制&位运算&ASCAII

bin(): 将整数转换为二进制字符串。

hex():将整数转换为十六进制字符串。

oct():将整数转换为八进制字符串。

int(): 将二进制字符串转换为整数。

binary_str = '1010'
num = int(binary_str, 2)  # 输出: 10

ord(): 获取字符的 ASCII 值（整数）。

chr(): 将整数（ASCII 值）转换为对应的字符。

int.bit_count() : （Python 版本: 3.10 及以上。）

num = 0b101011  # 二进制表示是 101011
count = num.bit_count()
print(count)  # 输出: 4

 int.bit_length():  返回整数二进制表示的最小位数（不包括符号位和前导零）

num = 10  # 二进制表示是 1010
length = num.bit_length()
print(length)  # 输出: 4

&: 按位与

|: 按位或

^: 按位异或

~: 按位取反

<<: 左移

>>: 右移

0xaaaaaaaa：        

二进制：10101010 10101010 10101010 10101010设计逻辑：所有奇数位为 1，偶数位为 0。用途：用于提取或检查奇数位。

0x55555555：

二进制：01010101 01010101 01010101 01010101设计逻辑：所有偶数位为 1，奇数位为 0。用途：用于提取或检查偶数位。

0xcccccccc：

二进制：11001100 11001100 11001100 11001100设计逻辑：每两位重复 11 和 00。用途：用于处理两位一组的操作。

0x33333333：

二进制：00110011 00110011 00110011 00110011设计逻辑：每两位重复 00 和 11。用途：用于处理两位一组的操作。

0xf0f0f0f0：

二进制：11110000 11110000 11110000 11110000设计逻辑：每四位重复 1111 和 0000。用途：用于处理四位一组的操作。

0x0f0f0f0f：

二进制：00001111 00001111 00001111 00001111设计逻辑：每四位重复 0000 和 1111。用途：用于处理四位一组的操作。

0x80000000：

二进制：10000000 00000000 00000000 00000000设计逻辑：最高位为 1，其余位为 0。用途：用于检查符号位（如 32 位整数的符号位）。

0x7fffffff：

二进制：01111111 11111111 11111111 11111111设计逻辑：最高位为 0，其余位为 1。用途：用于表示最大正数（如 32 位整数的最大值）。

快速判断奇偶性：if (x & 1) { /* x是奇数 */ }
快速除以2：x >>= 1（相当于x //= 2）
快速乘以2：x <<= 1（相当于x *= 2）
判断第n位是否为1：if (x & (1 << n)) { /* 第n位是1 */ }
设置第n位为1：x |= (1 << n)
将第n位清零：x &= ~(1 << n)
切换第n位的状态：x ^= (1 << n）

二. format格式化输出

1. 基本用法

format() 方法通过将占位符 {} 替换为传入的参数来格式化字符串。

text = "Hello, {}!".format("World")
print(text)  # 输出: Hello, World!

2. 位置参数

可以在 {} 中指定参数的索引（从 0 开始），以控制参数的替换顺序。

text = "{1} {0}".format("World", "Hello")
print(text)  # 输出: Hello World

3. 格式化数字

format() 支持对数字进行格式化，包括整数、浮点数等。

# 保留两位小数
pi = 3.1415926
text = "Pi: {:.2f}".format(pi)
print(text)  # 输出: Pi: 3.14# 千位分隔符
number = 1000000
text = "Number: {:,}".format(number)
print(text)  # 输出: Number: 1,000,000

4. 对齐和填充

可以通过 : 指定对齐方式和填充字符。

# 左对齐，宽度为 10，填充字符为 ' '
text = "{:<10}".format("Hello")
print(text)  # 输出: Hello# 右对齐，宽度为 10，填充字符为 '*'
text = "{:*>10}".format("Hello")
print(text)  # 输出: *****Hello# 居中对齐，宽度为 10，填充字符为 '='
text = "{:=^10}".format("Hello")
print(text)  # 输出: ==Hello===

5. 格式化二进制、八进制、十六进制

可以将数字格式化为二进制、八进制或十六进制。

num = 255# 二进制
text = "Binary: {:b}".format(num)
print(text)  # 输出: Binary: 11111111# 八进制
text = "Octal: {:o}".format(num)
print(text)  # 输出: Octal: 377# 十六进制（小写）
text = "Hex: {:x}".format(num)
print(text)  # 输出: Hex: ff# 十六进制（大写）
text = "Hex: {:X}".format(num)
print(text)  # 输出: Hex: FF

6. 格式化百分比

可以将浮点数格式化为百分比形式。

ratio = 0.75
text = "Percentage: {:.2%}".format(ratio)
print(text)  # 输出: Percentage: 75.00%

7. 格式化科学计数法

可以将数字格式化为科学计数法。

num = 123456789
text = "Scientific: {:.2e}".format(num)
print(text)  # 输出: Scientific: 1.23e+08

8. 格式化字符串字面量（f-string）

Python 3.6 引入了 f-string，它是一种更简洁的格式化方式。

name = "Alice"
age = 30
text = f"Name: {name}, Age: {age}"
print(text)  # 输出: Name: Alice, Age: 30

三. 字符串

使用 join() 方法拼接字符串列表。

words = ["Hello", "World"]
s = " ".join(words)  # 输出: Hello World

使用 find() 查找子字符串的位置（返回第一个匹配的索引，未找到返回 -1）。

s = "Hello World"
index = s.find("World")  # 输出: 6

 使用 index() 查找子字符串的位置（未找到会抛出异常）。

index = s.index("World")  # 输出: 6

使用 replace() 替换子字符串。

s = "Hello World"
new_s = s.replace("World", "Python")  # 输出: Hello Python

使用 split() 按分隔符分割字符串。

s = "Hello,World,Python"
parts = s.split(",")  # 输出: ['Hello', 'World', 'Python']

使用 upper() 转换为大写。

s = "Hello"
upper_s = s.upper()  # 输出: HELLO
使用 lower() 转换为小写。
lower_s = s.lower()  # 输出: hello

使用 strip() 去除两端空白。

s = "  Hello  "
stripped_s = s.strip()  # 输出: Hello
使用 lstrip() 去除左侧空白。
left_stripped_s = s.lstrip()  # 输出: Hello  
使用 rstrip() 去除右侧空白。
right_stripped_s = s.rstrip()  # 输出:   Hello

使用 isalpha() 判断是否全为字母。

result = "Hello".isalpha()  # 输出: True

使用 isdigit() 判断是否全为数字。

result = "123".isdigit()  # 输出: True

使用 isalnum() 判断是否全为字母或数字。

result = "Hello123".isalnum()  # 输出: True

使用 ljust() 左对齐并填充。
使用 rjust() 右对齐并填充。
使用 center() 居中对齐并填充。

s = "Hello"
aligned_s = s.ljust(10, "-")  # 输出: Hello-----aligned_s = s.rjust(10, "-")  # 输出: -----Helloaligned_s = s.center(10, "-")  # 输出: --Hello---

使用 count() 统计子字符串出现的次数。

s = "Hello Hello"
count = s.count("Hello")  # 输出: 2

使用切片反转字符串。

reversed_s = s[::-1]  # 输出: olleH

使用 zfill() 在字符串左侧填充零。

s = "42"
filled_s = s.zfill(5)  # 输出: 00042

四. 文件操作

1. 打开文件

使用 open() 函数打开文件，返回一个文件对象。

file = open(filename, mode, encoding)
参数：
filename: 文件名（包括路径）。mode: 文件打开模式（如 'r'、'w'、'a' 等）。encoding: 文件编码（如 'utf-8'）。file = open("example.txt", "r", encoding="utf-8")

2. 文件打开模式

'r'    只读模式（默认）。
'w'    写入模式（覆盖文件）。
'a'    追加模式（在文件末尾添加内容）。
'x'    创建模式（文件已存在则报错）。
'b'    二进制模式（如 'rb'、'wb'）。
't'    文本模式（默认）。
'+'    读写模式（如 'r+'、'w+'）。

3. 读取文件

读取整个文件：
with open("example.txt", "r", encoding="utf-8") as file:content = file.read()print(content)逐行读取：
with open("example.txt", "r", encoding="utf-8") as file:for line in file:print(line.strip())  # 去除行尾换行符读取所有行到列表：
with open("example.txt", "r", encoding="utf-8") as file:lines = file.readlines()print(lines)读取指定字节数：
with open("example.txt", "r", encoding="utf-8") as file:chunk = file.read(10)  # 读取前 10 个字符print(chunk)

4. 写入文件

覆盖写入：
with open("example.txt", "w", encoding="utf-8") as file:file.write("Hello, World!")追加写入：
with open("example.txt", "a", encoding="utf-8") as file:file.write("\nAppended text.")写入多行：
lines = ["Line 1\n", "Line 2\n", "Line 3\n"]
with open("example.txt", "w", encoding="utf-8") as file:file.writelines(lines)

5. 关闭文件

使用 close() 方法关闭文件，或使用 with 语句自动关闭。

手动关闭：file = open("example.txt", "r")
content = file.read()
file.close()自动关闭（推荐）：with open("example.txt", "r") as file:content = file.read()

6. 文件指针操作

获取当前指针位置：with open("example.txt", "r") as file:position = file.tell()print(position)移动指针位置：with open("example.txt", "r") as file:file.seek(10)  # 将指针移动到第 10 个字节content = file.read()print(content)

五. 集合

使用 add() 添加单个元素。

s = {1, 2, 3}
s.add(4)  # 输出: {1, 2, 3, 4}

使用 update() 添加多个元素。

s = {1, 2, 3}
s.update([4, 5, 6])  # 输出: {1, 2, 3, 4, 5, 6}

使用 remove() 删除指定元素（元素不存在会报错）。

s = {1, 2, 3}
s.remove(2)  # 输出: {1, 3}

使用 discard() 删除指定元素（元素不存在不会报错）。

s = {1, 2, 3}
s.discard(2)  # 输出: {1, 3}

使用 pop() 随机删除并返回一个元素。

s = {1, 2, 3}
element = s.pop()  # 可能输出: 1

使用 clear() 清空集合。

s = {1, 2, 3}
s.clear()  # 输出: set()

使用 union() 或 | 计算两个集合的并集。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
result = s1.union(s2)  # 输出: {1, 2, 3, 4, 5}
result = s1 | s2  # 同上

使用 intersection() 或 & 计算两个集合的交集。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
result = s1.intersection(s2)  # 输出: {3}
result = s1 & s2  # 同上

使用 difference() 或 - 计算两个集合的差集。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
result = s1.difference(s2)  # 输出: {1, 2}
result = s1 - s2  

使用 symmetric_difference() 或 ^ 计算两个集合的对称差集（仅存在于一个集合中的元素）。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
result = s1.symmetric_difference(s2)  # 输出: {1, 2, 4, 5}
result = s1 ^ s2  # 同上

 使用 issubset() 或 <= 判断一个集合是否是另一个集合的子集。

s1 = {1, 2}
s2 = {1, 2, 3}
result = s1.issubset(s2)  # 输出: True
result = s1 <= s2  # 同上

 使用 < 判断一个集合是否是另一个集合的真子集。

s1 = {1, 2}
s2 = {1, 2, 3}
result = s1 < s2  # 输出: True

使用 issuperset() 或 >= 判断一个集合是否是另一个集合的超集。
 

s1 = {1, 2, 3}
s2 = {1, 2}
result = s1.issuperset(s2)  # 输出: True
result = s1 >= s2  # 同上

使用 > 判断一个集合是否是另一个集合的真超集。
 

s1 = {1, 2, 3}
s2 = {1, 2}
result = s1 > s2  # 输出: True

使用 copy() 复制集合。
 

s1 = {1, 2, 3}
s2 = s1.copy()  # 输出: {1, 2, 3}

六. 库函数

bisect

1.bisect.bisect_left()

import bisect
lst = [1, 3, 4, 4, 6]
index = bisect.bisect_left(lst, 4)
print(index)  # 输出: 2

 2. bisect.bisect_right()

import bisect
lst = [1, 3, 4, 4, 6]
index = bisect.bisect_right(lst, 4)
print(index)  # 输出: 4

itertools

1.itertools.permutations()

import itertools
data = "ABC"
result = itertools.permutations(data, 2)
print(list(result))  # 输出: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

2.itertools.combinations()

import itertools
data = "ABC"
result = itertools.combinations(data, 2)
print(list(result))  # 输出: [('A', 'B'), ('A', 'C'), ('B', 'C')]

3.itertools.accumulate()

import itertools
data = [1, 2, 3, 4]
result = itertools.accumulate(data, lambda x, y: x + y)
print(list(result))  # 输出: [1, 3, 6, 10]

collections

1.collections.Counter

from collections import Counter
data = ["apple", "banana", "apple", "orange", "banana", "apple"]
counter = Counter(data)
print(counter)  # 输出: Counter({'apple': 3, 'banana': 2, 'orange': 1})

2.collections.defaultdict

from collections import defaultdict
dd = defaultdict(int)  # 默认值为 0
dd["apple"] += 1
print(dd["apple"])  # 输出: 1
print(dd["banana"])  # 输出: 0

3. collections.deque

from collections import deque
dq = deque([1, 2, 3])
dq.append(4)
print(dq) # 输出: deque([1, 2, 3, 4])from collections import deque
dq = deque([1, 2, 3])
dq.appendleft(0)
print(dq)  # 输出: deque([0, 1, 2, 3])from collections import deque
dq = deque([1, 2, 3])
item = dq.pop()
print(item)  # 输出: 3
print(dq)    # 输出: deque([1, 2])from collections import deque
dq = deque([1, 2, 3])
item = dq.popleft()
print(item)  # 输出: 1
print(dq)    # 输出: deque([2, 3])

functools

1. functools.lru_cache()

import functools@functools.lru_cache(maxsize=128)
def fibonacci(n):if n < 2:return nreturn fibonacci(n-1) + fibonacci(n-2)print(fibonacci(10))  # 输出: 55

2.functools.cache()  3.9+

import functools
@functools.cache
def factorial(n):if n == 0:return 1return n * factorial(n-1)
print(factorial(5))  # 输出: 120

3.functools.reduce()

import functools
data = [1, 2, 3, 4]
result = functools.reduce(lambda x, y: x + y, data)
print(result)  # 输出: 10

string

1.ascii_lowercase: 26小写字母

sys

1.sys.setrecursionlimit()

import sys
sys.setrecursionlimit(2000)

math

1. math.sqrt() : 得到数字的平方根

2. math.pow() : 计算一个数的幂

3. math.exp() : 计算自然指数函数

4. math.log() : 计算自然对数

5. math.log10() : 计算以10为底的对数

6. math.sin() : 计算正弦值

7. math.cos() : 计算余弦值

8. math.tan() : 计算正切值

9. math.radians() : 将角度转换为弧度

10. math.degrees() : 将弧度转换为角度

11. math.ceil() : 向上取整

12. math.floor() : 向下取整

13. math.fabs() : 返回绝对值

14. math.factorial() : 计算阶乘

15. math.gcd() : 计算最大公约数

16. math.pi : 数学常数π

17. math.e : 数学常数e

heapq

1.heapq.heappush(heap, item)

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heap)  # 输出: [1, 3, 2]

 2.heapq.heappop(heap)

import heapq
heap = [1, 3, 2]
print(heapq.heappop(heap))  # 输出: 1
print(heap)  # 输出: [2, 3]

3.heapq.heapify(x)

import heapq
heap = [3, 1, 2]
heapq.heapify(heap)
print(heap)  # 输出: [1, 3, 2]

4.heapq.heappushpop(heap, item)

import heapq
heap = [1, 3, 2]
print(heapq.heappushpop(heap, 4))  # 输出: 1
print(heap)  # 输出: [2, 3, 4]

 datetime

1.datetime.date(year, month, day)

import datetime
date_obj = datetime.date(2023, 10, 5)
print(date_obj)  # 输出: 2023-10-05

2. datetime.time(hour, minute, second, microsecond)

import datetime
time_obj = datetime.time(14, 30, 45)
print(time_obj)  # 输出: 14:30:45

3. datetime.datetime(year, month, day, hour, minute, second, microsecond)

import datetime
datetime_obj = datetime.datetime(2023, 10, 5, 14, 30, 45)
print(datetime_obj)  # 输出: 2023-10-05 14:30:45

4. datetime.timedelta(days, seconds, microseconds, milliseconds, minutes, hours, weeks)

import datetime
delta = datetime.timedelta(days=5, hours=3)
print(delta)  # 输出: 5 days, 3:00:00

5. datetime.datetime.now()

import datetime
now = datetime.datetime.now()
print(now)  # 输出: 当前日期和时间，例如: 2023-10-05 14:30:45.123456

6. datetime 对象相减

import datetime# 创建两个 datetime 对象
dt1 = datetime.datetime(2023, 10, 5, 14, 30, 0)
dt2 = datetime.datetime(2023, 10, 10, 10, 15, 0)# 计算时间差
time_diff = dt2 - dt1
print(time_diff)  # 输出: 4 days, 19:45:00
print(type(time_diff))  # 输出: <class 'datetime.timedelta'>

7. datetime 对象加减 timedelta

import datetime# 创建一个 datetime 对象
dt = datetime.datetime(2023, 10, 5, 14, 30, 0)# 创建一个 timedelta 对象
delta = datetime.timedelta(days=3, hours=2, minutes=15)# 加法
new_dt = dt + delta
print(new_dt)  # 输出: 2023-10-08 16:45:00# 减法
new_dt = dt - delta
print(new_dt)  # 输出: 2023-10-02 12:15:00

8. timedelta 对象的使用

timedelta 对象表示时间间隔，可以通过以下属性访问其值：import datetime# 计算时间差
dt1 = datetime.datetime(2023, 10, 5, 14, 30, 0)
dt2 = datetime.datetime(2023, 10, 10, 10, 15, 0)
time_diff = dt2 - dt1# 访问 timedelta 的属性
print("天数:", time_diff.days)  # 输出: 天数: 4
print("秒数:", time_diff.seconds)  # 输出: 秒数: 71100 (19小时45分钟的秒数)
print("总秒数:", time_diff.total_seconds())  # 输出: 总秒数: 416100.0

Decimal

1. Decimal(value)

from decimal import Decimal# 创建 Decimal 对象
num1 = Decimal('10.5')
num2 = Decimal('3.2')print(num1)  # 输出: 10.5
print(num2)  # 输出: 3.2

七. 模板

1. 二分查找：

while left + 1 < right:mid = (right + left) // 2if 条件:left = mid else:right = mid return right 

2. 二位前缀和 & 差分

n = int(input())
matrix = []
for _ in range(n):matrix.append(list(map(int,input().split())))
s = [[0] * (n + 1) for _ in range(n + 1)]
for i, row in enumerate(matrix):for j, x in enumerate(row):s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x
mx = float('-inf')# 以下这四个循环是为了枚举所有子矩阵用的。
for x1 in range(1, n + 1):for y1 in range(1, n + 1):for x2 in range(1, n + 1):for y2 in range(1, n + 1):if x2 < x1 or y2 < y1:continuecurrent_sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]mx = max(mx, current_sum)
print(mx)

# 二维差分
diff = [[0] * (n + 2) for _ in range(n + 2)]
for r1, c1, r2, c2 in queries:diff[r1 + 1][c1 + 1] += 1diff[r1 + 1][c2 + 2] -= 1diff[r2 + 2][c1 + 1] -= 1diff[r2 + 2][c2 + 2] += 1# 计算 diff 的二维前缀和（原地修改）
for i in range(1, n + 1):for j in range(1, n + 1):diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]# 保留中间 n*n 的部分，即为答案
diff = diff[1:-1]
for i, row in enumerate(diff):diff[i] = row[1:-1]
print(diff)

 3.快速幂

def fast_pow(base, exponent, mod=None):result = 1while exponent > 0:if exponent % 2 == 1:if mod is not None:result = (result * base) % modelse:result = result * baseif mod is not None:base = (base * base) % modelse:base = base * baseexponent = exponent // 2return result# 示例使用
base = 2
exponent = 10
mod = 1000000007
# 不使用取模
print(fast_pow(base, exponent))
# 使用取模
print(fast_pow(base, exponent, mod))

4.dijkstra

import heapq
from collections import defaultdictdef dijkstra(graph, start):# 初始化距离字典，将所有顶点的距离初始化为无穷大distances = {node: float('inf') for node in graph}# 起始顶点到自身的距离为 0distances[start] = 0# 优先队列，用于存储待处理的顶点及其距离，初始时只有起始顶点priority_queue = [(0, start)]while priority_queue:# 从优先队列中取出当前距离源点最近的顶点及其距离current_distance, current_node = heapq.heappop(priority_queue)# 如果当前取出的距离大于已记录的最短距离，跳过该顶点if current_distance > distances[current_node]:continue# 遍历当前顶点的所有邻接顶点for neighbor, weight in graph[current_node].items():# 计算从源点经过当前顶点到邻接顶点的距离distance = current_distance + weight# 如果该距离小于已记录的最短距离，更新最短距离if distance < distances[neighbor]:distances[neighbor] = distance# 将更新后的邻接顶点及其距离加入优先队列heapq.heappush(priority_queue, (distance, neighbor))return distances# 示例图的邻接表表示
graph = defaultdict(dict)
graph[0][1] = 4
graph[0][2] = 1
graph[1][2] = 2
graph[1][3] = 5
graph[2][1] = 2
graph[2][3] = 8
graph[2][4] = 10
graph[3][4] = 2
graph[4][3] = 2# 起始顶点
start_vertex = 0# 调用 Dijkstra 算法计算最短路径
shortest_distances = dijkstra(graph, start_vertex)# 输出结果
for vertex, distance in shortest_distances.items():print(f"从顶点 {start_vertex} 到顶点 {vertex} 的最短距离是: {distance}")

5.弗洛伊德

# 定义无穷大
INF = float('inf')def floyd_warshall(graph):# 获取图中顶点的数量num_vertices = len(graph)# 初始化距离矩阵，初始值为图的邻接矩阵dist = [row[:] for row in graph]# 弗洛伊德算法核心部分for k in range(num_vertices):for i in range(num_vertices):for j in range(num_vertices):# 如果经过顶点 k 可以使从 i 到 j 的距离更短，则更新距离if dist[i][k] != INF and dist[k][j] != INF and dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] = dist[i][k] + dist[k][j]return dist# 示例图的邻接矩阵表示
graph = [[0, 5, INF, 10],[INF, 0, 3, INF],[INF, INF, 0, 1],[INF, INF, INF, 0]
]# 调用弗洛伊德算法计算所有顶点对之间的最短路径
shortest_distances = floyd_warshall(graph)# 输出结果
for i in range(len(shortest_distances)):for j in range(len(shortest_distances[i])):if shortest_distances[i][j] == INF:print(f"从顶点 {i} 到顶点 {j} 的最短距离是: 无穷大")else:print(f"从顶点 {i} 到顶点 {j} 的最短距离是: {shortest_distances[i][j]}")

6.并查集

class UnionFind:def __init__(self, n):# 初始化每个元素的父节点为自身self.parent = [i for i in range(n)]def find(self, x):# 查找元素 x 的根节点while self.parent[x] != x:x = self.parent[x]return xdef union(self, x, y):# 合并元素 x 和 y 所在的集合root_x = self.find(x)root_y = self.find(y)if root_x != root_y:self.parent[root_x] = root_ydef is_connected(self, x, y):# 判断元素 x 和 y 是否在同一个集合中return self.find(x) == self.find(y)# 示例使用
uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.is_connected(0, 2))  # 输出: True
print(uf.is_connected(0, 3))  # 输出: False

 7.树状数组

class BinaryIndexedTree:def __init__(self, n):# 初始化树状数组，长度为 n + 1，因为树状数组的下标从 1 开始self.bit = [0] * (n + 1)self.n = ndef lowbit(self, x):# lowbit 函数用于获取 x 的最低位 1 所表示的数值return x & -xdef update(self, idx, val):# 单点更新操作，将原数组中 idx 位置的值增加 valwhile idx <= self.n:self.bit[idx] += validx += self.lowbit(idx)def query(self, idx):# 前缀和查询操作，计算原数组中从 1 到 idx 的元素和res = 0while idx > 0:res += self.bit[idx]idx -= self.lowbit(idx)return resdef range_query(self, left, right):# 区间和查询操作，计算原数组中从 left 到 right 的元素和return self.query(right) - self.query(left - 1)

 8.素数预处理

MX = 1000001
LPF = [0] * MX
for i in range(2, MX):if LPF[i] == 0:for j in range(i, MX, i):if LPF[j] == 0:LPF[j] = i

八. 其他用法

1. zip(): 将多个可迭代对象“压缩”为一个元组迭代器，用于并行遍历多个序列。

2. enumerate(): 为可迭代对象添加索引，返回 (索引, 元素) 的元组迭代器。

3. all(): 判断可迭代对象中是否所有元素都为真（非零、非空、非 False）。

4. any(): 判断可迭代对象中是否有任意一个元素为真。

5. help(): 查看函数、模块或对象的帮助文档。

6. lambda: 用于创建匿名函数，简化代码，通常用于定义简单的单行函数。

7. key: 用于指定排序、分组等操作中的关键字函数，决定如何比较或处理元素。

8. exit(): 结束程序

9. pow(a,b,c)

10. dfs.cache_clear()