PYTHON常用基础库-写算法

搜索和排序算法

• heapq： 实现最小堆和最大堆（优先队列），用于快速找到最小或最大的元素。

import heapq
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)
heapq.heappop(heap)  # 1

• bisect： 提供二分查找功能，适合在有序列表中查找插入位置或边界。

import bisect
arr = [1, 3, 5, 7]
bisect.bisect_left(arr, 4)  # 2

• functools 和 operator： 常用于排序和比较函数。
  • functools.cmp_to_key： 自定义排序顺序。
  • operator.itemgetter： 按某个字段排序。

from operator import itemgetter
data = [('a', 3), ('b', 1), ('c', 2)]
sorted(data, key=itemgetter(1))  # [('b', 1), ('c', 2), ('a', 3)]

图论算法

• collections.deque： 双端队列，适用于广度优先搜索（BFS）。

from collections import deque
queue = deque([start_node])
queue.append(next_node)
queue.popleft()

• heapq： 可以用来实现带权图中的 Dijkstra 算法。
• collections.defaultdict： 构建邻接表的图结构。

from collections import defaultdict
graph = defaultdict(list)
graph[node].append(neighbor)

动态规划

• functools.lru_cache： 递归动态规划中常用缓存装饰器，减少重复计算。

from functools import lru_cache
@lru_cache(None)
def dp(n):
    if n < 2:
        return n
    return dp(n - 1) + dp(n - 2)

• math： 常用于一些动态规划题目中涉及的数学运算，比如斐波那契数列。

import math
math.factorial(5)  # 120

组合数学与排列

• itertools： 提供排列、组合、累加、笛卡尔积等操作。
  • permutations 和 combinations： 生成排列和组合。
  • product： 生成笛卡尔积。

from itertools import permutations, combinations, product
list(permutations([1, 2, 3], 2))  # [(1, 2), (1, 3), (2, 1), ...]
list(combinations([1, 2, 3], 2))  # [(1, 2), (1, 3), (2, 3)]
list(product([1, 2], [3, 4]))     # [(1, 3), (1, 4), (2, 3), (2, 4)]

字符串处理

• re： 正则表达式，适合复杂的字符串匹配和处理。

import re
re.findall(r'\d+', '12 apples and 10 bananas')  # ['12', '10']

• collections.Counter： 统计字符频率，可以用来判断是否是字母异位词等问题。

from collections import Counter
Counter('aabbcc')  # Counter({'a': 2, 'b': 2, 'c': 2})

数学与数论

• math： 包含基本数学操作，例如开方、对数、三角函数、因数分解等。

import math
math.gcd(12, 15)   # 3
math.isqrt(16)     # 4 (返回整数)

• fractions： 提供分数操作，适合处理分数运算问题。

from fractions import Fraction
Fraction(1, 3) + Fraction(2, 3)  # Fraction(1, 1)

• random： 生成随机数，常用于随机算法或模拟。

import random
random.randint(1, 10)  # 生成 1 到 10 之间的随机整数

时间与日期处理

• time： 可以进行计时操作，比如记录算法的执行时间。

import time
start = time.time()
# Some algorithm
end = time.time()
print("Execution time:", end - start)

• datetime： 用于日期和时间的操作，可以帮助处理带日期的题目。

from datetime import datetime, timedelta
now = datetime.now()

统计与概率

• statistics： 包含基本的统计函数，比如均值、中位数、标准差等。

import statistics
data = [1, 2, 2, 3, 4]
statistics.mean(data)  # 2.4

• random： 生成随机浮点数、整数和选择随机元素等，适合模拟和随机采样。

import random
random.choice([1, 2, 3])  # 从列表中随机选择一个元素

集合与集合操作

• set： Python 内置的集合数据类型，提供交集、并集、差集等操作，适合处理不重复元素的集合运算。

set_a = {1, 2, 3}
set_b = {2, 3, 4}
set_a.intersection(set_b)  # {2, 3}

调试和性能分析

• timeit： 精确测试代码段的执行时间，适合分析算法的性能。

import timeit
print(timeit.timeit("sum(range(100))", number=10000))

• cProfile： 提供详细的性能分析报告，包括每个函数的执行次数和时间。

import cProfile
def func():
    sum(range(100))
cProfile.run('func()')

小结

搜索和排序问题中，heapq 可用于优先队列，快速查找最小或最大元素；bisect 提供二分查找功能，便于在有序列表中插入和查找位置。
在图论算法中，collections.deque 实现广度优先搜索（BFS）高效而简洁；collections.defaultdict 构建邻接表，方便管理图节点和邻接关系。
动态规划中，functools.lru_cache 缓存递归结果，减少重复计算；math 的数学函数在优化动态规划中提供基础运算支持。
组合数学与排列问题利用 itertools 生成排列、组合、笛卡尔积等，有效处理复杂排列组合需求。
字符串处理时，re 提供正则表达式匹配，适合复杂字符串查找与替换；collections.Counter 统计字符频率，轻松解决计数问题。
数学与数论中，math 包含常用数学函数，fractions 支持分数运算，random 提供随机数生成，适用于模拟和数值生成。
时间与日期处理方面，time 和 datetime 可用于计时和日期操作，记录算法执行时间。
统计与概率问题中，statistics 包含均值、中位数等统计函数，random 用于随机采样和概率分布生成。
在集合操作中，set 提供交集、并集和差集运算，简化集合相关问题的实现。
调试与性能分析工具 timeit 和 cProfile 测量代码运行时间，生成性能分析报告，是优化算法性能的有力工具。