跳到主要内容
SUN / 笔记
← 全部文章

算法题常用

语言1696 字 · 5 分钟
#Python

在 Python 中解决算法问题时，可以利用其简洁的语法和丰富的内置库来大幅简化代码。以下是一些常用技巧和工具，帮助你高效编写算法代码：

基础语法技巧

1. 快速交换变量

python
a, b = b, a  # 无需临时变量

2. 列表推导式（List Comprehension）

python
# 生成平方列表
squares = [x**2 for x in range(10)]
# 过滤偶数
evens = [x for x in range(10) if x % 2 == 0]

3. 条件表达式（三元运算符）

python
max_val = a if a > b else b

4. 同时遍历索引和值（enumerate）

python
for idx, value in enumerate(['a', 'b', 'c']):
    print(idx, value)  # 输出索引和值

5. 同时遍历多个序列（zip）

python
names = ["Alice", "Bob"]
ages = [25, 30]
for name, age in zip(names, ages):
    print(name, age)

6. 字符串快速反转

python
s = "hello"
reversed_s = s[::-1]  # "olleh"

数据结构

1. 字典（dict）的默认值处理

python
# 统计词频（避免 KeyError）
freq = {}
for word in words:
    freq[word] = freq.get(word, 0) + 1

# 更高效的方式：使用 defaultdict
from collections import defaultdict
freq = defaultdict(int)
for word in words:
    freq[word] += 1

2. 优先队列（堆）

python
import heapq
heap = []
heapq.heappush(heap, 3)  # 插入元素
heapq.heappush(heap, 1)
print(heapq.heappop(heap))  # 弹出最小元素（1）

3. 双端队列（deque）

python
from collections import deque
dq = deque()
dq.append(1)    # 右端插入
dq.appendleft(2) # 左端插入
dq.pop()         # 右端弹出
dq.popleft()     # 左端弹出（适合实现BFS）

4. 集合（set）去重与快速查找

python
seen = set()
seen.add(10)
if 10 in seen:  # O(1) 查找
    print("存在")

输入输出

正常输入

python
# 获取字符串型输入（一行）
s = input()

# 获取一行单个数字输入
x = int(input())

# 获取一行多个数字输入，split（）分割，默认是空格
n,m = map(int,input().split())

1. 快速读取输入

python
import sys
# 单行输入
n = int(sys.stdin.readline())
# 读取一行并分割为列表
arr = list(map(int, sys.stdin.readline().split()))

2. 多行输入（如读取未知行数）

python
import sys
data = [line.strip() for line in sys.stdin]

3. 输出

python
print("hello",end='') #pythonm
print(f"{value:.2f}")  # 保留两位小数
print(" ".join(map(str, arr)))  # 列表输出为空格分隔的字符串

常用库函数

1. 数学运算

python
import math
math.gcd(a, b)    # 最大公约数
math.ceil(x)      # 向上取整
math.pow(x, y)    # 幂运算

2. 排列组合（itertools）

python
from itertools import permutations, combinations
# 全排列
perms = permutations([1, 2, 3], 2)  # 2个元素的全排列
# 组合
combs = combinations([1, 2, 3], 2)  # 2个元素的组合

3. 二分查找（bisect）

python
import bisect
arr = [1, 3, 5, 7]
pos = bisect.bisect_left(arr, 4)  # 返回插入位置（2）

算法实现技巧

1. 递归优化（lru_cache）

python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

2. 快速幂算法（取模）

python
def pow_mod(a, b, mod):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b = b // 2
    return result

3. 前缀和与差分数组

python
# 前缀和
arr = [1, 2, 3, 4]
prefix = [0]
for num in arr:
    prefix.append(prefix[-1] + num)
# 差分数组
diff = [arr[0]] + [arr[i] - arr[i-1] for i in range(1, len(arr))]

性能优化小技巧

1. 局部变量加速

python
def fast_loop():
    local_max = max  # 将内置函数赋值给局部变量
    arr = [1, 3, 5]
    return local_max(arr)

2. 避免全局变量

全局变量访问较慢，尽量使用局部变量。

3. 使用生成器（yield）

python
def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

4. 缓存装饰器@cache

常见算法模板

1. 快速排序

python
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

2. BFS 模板

python
from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append(neighbor)
    return visited

总结

Python 的简洁语法和丰富库函数（如 collections、itertools、heapq）能大幅简化算法实现。重点掌握：

  1. 列表推导式和生成器简化循环。
  2. 字典和集合的高效操作。
  3. 递归优化（lru_cache）。
  4. 输入输出优化（避免超时）。

通过结合这些技巧，你可以写出比 C++ 更短且易读的代码，尤其在快速原型设计和笔试中优势明显！

字典

Counter（计数器）

用途：专门用于统计可哈希对象（如字符串、列表中的元素）的出现次数。

基本用法

  • 初始化：

    python
    from collections import Counter

# 直接传入可迭代对象（如列表、字符串）
cnt = Counter(['a', 'b', 'a', 'c', 'b', 'a'])
print(cnt)  # 输出: Counter({'a': 3, 'b': 2, 'c': 1})

  • 统计其他类型：

    python
    text = "hello world"
cnt = Counter(text)
# 输出: Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

常用方法

  • most_common(n)：返回出现次数最多的前 n 个元素。

    python
    cnt.most_common(2)  # 输出: [('a', 3), ('b', 2)]

  • 数学运算：支持加法、减法、交集（&）和并集（|）。

    python
    c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
c1 + c2  # Counter({'a': 4, 'b': 3})
c1 - c2  # Counter({'a': 2})

  • 更新计数：使用 update() 方法合并统计。

    python
    cnt.update(['a', 'd'])  # Counter({'a': 4, 'b': 2, 'c': 1, 'd': 1})

  • 获取所有元素：elements() 返回一个迭代器。

    python
    list(cnt.elements())  # ['a', 'a', 'a', 'b', 'b', 'c']

特性

  • 不存在的键返回 0，而不是 KeyError。
    python
    print(cnt['x'])  # 输出: 0

defaultdict（默认字典）

用途：当访问不存在的键时，自动生成默认值，避免 KeyError。

基本用法

  • 初始化：

    python
    from collections import defaultdict

# 需要指定默认值的类型（工厂函数）
d = defaultdict(int)      # 默认值为 0
d = defaultdict(list)     # 默认值为空列表 []
d = defaultdict(set)      # 默认值为空集合 set()
d = defaultdict(lambda: "默认值")  # 自定义默认值

  • 示例：统计单词位置。

    python
    words = ['apple', 'banana', 'apple', 'orange']
word_positions = defaultdict(list)

for idx, word in enumerate(words):
    word_positions[word].append(idx)

# 输出: defaultdict(list, {'apple': [0, 2], 'banana': [1], 'orange': [3]})

特性

  • 与普通字典完全兼容，但自动处理缺失键。
  • 默认值仅在访问时创建，不会预先填充所有键。

3. 对比与适用场景

特性 Counter defaultdict
主要用途 统计元素出现次数 处理缺失键，自动生成默认值
初始化参数 可迭代对象或映射 工厂函数（如 int, list）
键不存在时的行为 返回 0（不修改字典） 创建键并赋默认值
典型场景 词频统计、数据分析 分组、聚合、树状结构

4. 综合示例

结合使用 defaultdict 和 Counter：

python
from collections import defaultdict, Counter

# 统计每个城市的人员年龄分布
data = [
    ('Paris', 25),
    ('Tokyo', 30),
    ('Paris', 28),
    ('Tokyo', 25),
]

city_ages = defaultdict(Counter)

for city, age in data:
    city_ages[city][age] += 1

# 输出：
# defaultdict(Counter, {
#   'Paris': Counter({25: 1, 28: 1}),
#   'Tokyo': Counter({30: 1, 25: 1})
# })
  • Counter：优先选择需要快速统计元素频率的场景。
  • defaultdict：优先选择需要避免 KeyError 并简化代码的场景。

相关文章

如何启动 & 基本运行 →C++面向对象 →day02——面向对象高级 →