跳转至

08 · 高频手撕代码背诵手册(Python 3)

核心概念

(a) 🗂️ 高频手撕代码地图:背模板、讲复杂度、扛追问

手撕代码不是考算法竞赛,而是考「面试官给模板题,你能不能在 5 分钟内写对 + 讲清复杂度 + 扛住追问」。本篇按「语言特性 → 并发 → 轮子 → 数据结构 → 设计模式 → 工具类」组织,每段代码都带注释与时空复杂度标注,可直接运行。

(该图在 GitHub/VSCode + mermaid 插件中可渲染)

flowchart TB
    Hand["✍️ 高频手撕代码"]
    Hand --> Dec["🎁 装饰器四件套"]
    Hand --> Gen["⏳ 生成器与 yield"]
    Hand --> Single["🔂 单例模式三种写法"]
    Hand --> Con["🧵 线程 / 进程 / asyncio"]
    Hand --> Wheel["🔧 轮子题<br/>LRU / LFU / 最小栈"]
    Hand --> Ds["📚 数据结构实现<br/>栈↔队列 / KMP / 回文"]
    Hand --> Pattern["🧩 设计模式可运行版"]
    Hand --> Tool["🛠️ 工具类三件套"]
  • 🎁 装饰器四件套:无参装饰器(两层函数)、带参装饰器(三层函数)、functools.wraps(保留原函数元信息)、类装饰器(带状态计数)是默写底线。要能说出每段的时空复杂度(包装 O(1))与「@ 糖」的等价写法。
  • ⏳ 生成器与 yield:斐波那契生成器(O(1) 空间、可无限)、无限序列 take、yield from 委托子生成器是三大模板。背清楚「惰性求值、一次性遍历」两个特性,空间复杂度永远是面试追问点。
  • 🔂 单例模式三种写法:模块级(import 一次天然单例)、__new__ 版(加锁保证线程安全)、装饰器版(dict 缓存首建实例)要能切换默写。追问点:线程安全、什么场景用哪个。
  • 🧵 线程 / 进程 / asyncio:生产者-消费者(threading + queue,毒丸退出)、线程池(IO 密集)、进程池(CPU 密集)、asyncio 并发与 asyncio.Queue 消费者模型。每个都要能报复杂度并说清选型依据(GIL)。
  • 🔧 轮子题:手写 LRU Cache(OrderedDict 版是标准答案,进阶问 dict + 双向链表)、手写 LFU(频率桶 + OrderedDict)、手写最小栈(辅助栈同步法)。追问:不用 OrderedDict 怎么实现、LFU 为何频率相同再按时间淘汰。
  • 📚 数据结构实现:两栈实现队列(均摊 O(1))、单队列实现栈(push O(n))、KMP 字符串匹配(O(m+n))、最长回文子串中心扩展(O(n²),追问 Manacher O(n))。复杂度与边界条件是评分关键。
  • 🧩 设计模式可运行版:观察者(订阅-发布 + 回调改进)、策略(注册表字典替代 if/elif、函数即策略)、工厂(简单工厂 vs 工厂方法、开闭原则)。追问方向:新增一种产品要不要改旧代码。
  • 🛠️ 工具类三件套:retry 装饰器(指数退避 0.1→0.2→0.4,注意 4xx 不重试)、计时器上下文管理器(contextmanager,异常路径也打印)、参数校验装饰器。能讲清何时该重试、__enter__/__exit__ 与 contextmanager 的关系。

面向秋招算法/后端岗位的 背诵级手写代码合集。 所有代码均为 标准库实现、可直接运行,每段都带注释与 时间/空间复杂度标注。 结构:每个小节先给「考点」一句话 → 完整代码 → 「面试追问」。 背诵策略:先默写主框架,再补细节(边界条件、decorator 的 wraps、队列判空等)。


1. 装饰器四件套

1.1 无参装饰器

💡 心法(一句话):装饰器 = 在不改原函数代码的前提下,给函数「套一件外套」(计时 / 打日志 / 加权限),再把「穿着外套的函数」还给你。

🏷️ 类比:网上买书加「防摔包装」:书(原函数)不用动,快递站(装饰器)在外面包一层气泡膜(wrapper),拆开包装里面还是原来那本书。

🔍 逐步走查:执行 slow_add(1, 2) 时:① @timer 等价于 slow_add = timer(slow_add),此时 slow_add 其实已是 wrapper;② 进入 wrapper:记下 start → 调用真函数 slow_add(1, 2),睡 0.1s 后返回 3;③ 打印耗时,return 3。函数名没变、行为却多了「计时」,这就是装饰器的全部秘密。

考点:装饰器本质是"接收函数返回函数"的高阶函数;熟练写出 *args, **kwargs 万能签名并保持返回值。

# decorator_basic.py —— 无参装饰器(最基础版)
import time

def timer(func):
    """打印函数耗时的装饰器"""
    def wrapper(*args, **kwargs):          # 万能签名,兼容任意入参
        start = time.perf_counter()
        result = func(*args, **kwargs)     # 调用原函数并透传参数
        print(f"{func.__name__} 耗时 {time.perf_counter() - start:.4f}s")
        return result                      # 必须返回原函数的结果
    return wrapper

@timer
def slow_add(a, b):
    time.sleep(0.1)
    return a + b

print(slow_add(1, 2))                      # 输出耗时 + 3
# 等价写法(@ 糖的本质):
# slow_add = timer(slow_add)
# 时间复杂度 O(1) 包装,空间复杂度 O(1)

1.2 带参装饰器

💡 心法(一句话):无参装饰器是 2 层(工厂 → 外套);带参装饰器是 3 层——先按参数「定制」一件外套(如重复 3 次),再给函数套上。

🏷️ 类比:定做西装:先跟裁缝说「要 3 粒扣」(外层 times=3 参数),裁缝按参数做好版型(中层 decorator),再量你的身材给现成函数套上(内层 wrapper)。

🔍 逐步走查:@repeat(3) 展开为 hello = repeat(3)(hello):① repeat(3) 先执行,返回 decorator;② decorator(hello) 执行,返回 wrapper;③ 之后调用 hello("Alice") 实际走 wrapper,for _ in range(3) 打印 3 次。口诀:参数进外层、函数进中层、干活儿在内层。

考点:带参装饰器 = 三层函数:外层(参数) -> 中层(函数) -> 内层(wrapper);@deco(3) 先调用建参再装饰。

# decorator_param.py —— 带参装饰器(可配置重复次数)
def repeat(times: int):                     # 第一层:接收装饰器参数
    def decorator(func):                    # 第二层:接收被装饰函数
        def wrapper(*args, **kwargs):       # 第三层:真正执行逻辑
            for _ in range(times):
                result = func(*args, **kwargs)
            return result
        return wrapper
    return decorator

@repeat(3)
def hello(name: str) -> str:
    print(f"Hello, {name}")
    return name

hello("Alice")                              # 打印 3 次
# 等价写法:hello = repeat(3)(hello)
# 带参装饰器依次是 3 层,与无参装饰器 2 层区分开

1.3 functools.wraps

💡 心法(一句话):装饰器套外套时会把函数的「身份证」(__name__ / __doc__)换成 wrapper 的;@functools.wraps(func) 负责把身份证贴回原函数。

🏷️ 类比:安检口换装后证件被拿错:wrapper 顶替了原函数的名牌;wraps 就是「把名牌还给你」的柜台——调试、报错、生成文档时才能认出原函数。

考点:不带 wraps 的装饰器会把原函数的 __name__/__doc__ 覆盖成 wrapper 的;functools.wraps 用 update_wrapper 把元信息拷回。

# decorator_wraps.py —— 为什么需要 functools.wraps
import functools

def bad_log(func):
    def wrapper(*args, **kwargs):
        """wrapper 自己的文档"""
        return func(*args, **kwargs)
    return wrapper

def good_log(func):
    @functools.wraps(func)                  # 把 func 的 __name__/__doc__ 等拷给 wrapper
    def wrapper(*args, **kwargs):
        return func(*args, **kwargs)
    return wrapper

@bad_log
def add(a, b):
    """两数相加"""
    return a + b

@good_log
def sub(a, b):
    """两数相减"""
    return a - b

print("bad  :", add.__name__, add.__doc__)   # wrapper / wrapper 自己的文档 ❌
print("good :", sub.__name__, sub.__doc__)   # sub / 两数相减 ✅
# 面试必答:wraps = update_wrapper(wrapper, func),内省/调试/Sphinx 文档依赖它

1.4 类装饰器

💡 心法(一句话):类装饰器 = 让「实例」当装饰器:类实现 __call__ 后对象能像函数一样被调用,还能用实例属性存状态(比如数一数被调了几次)。

🏷️ 类比:带计数功能的门卫:每次放人进门都「计数 +1」,计数存在门卫自己身上(实例属性 calls),而不是写在进门的人身上。

考点:类实现 __call__ 后可作为装饰器;类版本可以在实例上保存状态(如调用计数),比函数闭包更"有状态"。

# decorator_class.py —— 类装饰器(带调用计数状态)
class CountCalls:
    def __init__(self, func):
        self.func = func
        self.calls = 0                      # 实例属性保存状态

    def __call__(self, *args, **kwargs):
        self.calls += 1
        print(f"第 {self.calls} 次调用 {self.func.__name__}")
        return self.func(*args, **kwargs)

@CountCalls
def ping(x):
    return f"pong:{x}"

print(ping(1))
print(ping(2))                              # 计数累加为 2
# 时间复杂度 O(1) 每调用,空间复杂度 O(1)(存一个计数器)

1.5 对比表格

类型 层数 特点 常见写法
无参装饰器 2 层 最简单,@deco deco(func)
带参装饰器 3 层 可配置参数 deco(args)(func)
wraps 装饰器 2 层 + wraps 保留元信息,范式 @functools.wraps(func)
类装饰器 类 + __call__ 可保存状态 class Deco: __call__

1.6 面试追问

Q1:装饰器实现原理?

语法糖:@deco 等价于 func = deco(func);函数是一等公民,可作为参数与返回值传递。带参装饰器相当于 func = deco(args)(func)。

Q2:函数装饰器和类装饰器区别?

函数版闭包简单无状态;类版能存实例属性(计数器、配置),但多一层对象开销。两者用 __call__/闭包都能实现,看状态需求选型。

Q3:装饰器顺序 @A @B 是谁先执行?

自下而上装饰(B 先包裹,A 再包裹),所以 A(B(func));调用时自上而下执行。例:@auth @cache,先过 auth 再过 cache。

易错点:忘写 return result(吞返回值)、忘 @wraps(丢元信息)、带参装饰器少写一层函数 —— 这三点写完自检一遍。


2. 生成器

2.1 斐波那契生成器

考点:yield 让函数变生成器,惰性求值只占 O(1) 内存;手写斐波那契是最经典热身题。

# generator_fib.py —— 斐波那契生成器
def fib():
    """无限斐波那契序列生成器"""
    a, b = 0, 1
    while True:
        yield a                    # 挂起并返回当前值,下次从这继续
        a, b = b, a + b            # 滚动推进

g = fib()
print([next(g) for _ in range(10)])   # [0,1,1,2,3,5,8,13,21,34]
# 时间:每次 next O(1);空间:仅两个变量 O(1);可无限生成,不占内存

2.2 无限序列 take

💡 心法(一句话):生成器像「无限长的传送带」,take 就是只取前 n 件的截断器——防止程序在无限序列上永远等下去。

🏷️ 类比:自助餐不限量供应(无限生成器),但你的盘子有限——take(n) 就是「只夹 n 个就停」的手。

考点:无限生成器必须用 take/islice 截断消费,防止死循环;这是"生成器 + 工具函数"的配合题。

# generator_take.py —— 从无限序列中取前 n 项
import itertools

def naturals():
    n = 0
    while True:
        yield n
        n += 1

def take(n, iterable):
    """手写 take:取前 n 个(用 index 控制,防止死循环)"""
    result, it = [], iter(iterable)
    for _ in range(n):
        result.append(next(it))
    return result

print(take(5, naturals()))                    # [0,1,2,3,4]
print(list(itertools.islice(naturals(), 5)))  # 标准库版,等价
# 时间 O(n),空间 O(n)(只保存取出的 n 项,而非全部序列)

2.3 yield from

💡 心法(一句话):yield from 是「中转站」:把子生成器产出的每个值原封不动转发给外层调用者,相当于替外层写了一个 for x in sub: yield x。

🏷️ 类比:快递中转站:总站(outer)不拆包裹,收到子站(sub_gen)的件直接转发给收件人,子站的「返回值」也会带回总站。

考点:yield from 把子生成器的产出"透传"给外层,用于委托生成器 / 扁平化嵌套可迭代。

# generator_yieldfrom.py —— yield from 的两种典型用法
def sub_gen(x):
    yield f"sub-start:{x}"
    yield f"sub-end:{x}"

def outer():
    yield "outer-before"
    yield from sub_gen(1)          # 将子生成器的 yield 全部透传出去
    yield "outer-after"

print(list(outer()))
# ['outer-before', 'sub-start:1', 'sub-end:1', 'outer-after']

def flatten(nested):
    """yield from 扁平化嵌套列表"""
    for item in nested:
        if isinstance(item, (list, tuple)):
            yield from flatten(item)
        else:
            yield item

print(list(flatten([1, [2, [3, 4]], 5])))    # [1, 2, 3, 4, 5]
# 时间 O(总元素数),空间 O(嵌套深度)(递归栈)

2.4 面试追问

Q1:生成器和普通函数区别?

① 生成器含 yield,调用不执行,返回生成器对象;② 每 next 执行到下一个 yield 并挂起,保存局部状态;③ 惰性求值内存占用小;④ 迭代一次即耗尽。

Q2:yield from 相比手动 for x in sub: yield x 的好处?

它还会处理返回值(return 的值变成 yield from 表达式的值),并能在双向通信时透传 send/throw;手写 for 循环做不到这两点。

Q3:生成器有什么用(工程场景)?

① 处理超大数据/流式读取不爆内存;② 协程的基础;③ 惰性流水线(如日志解析管道)。

易错点:无限生成器忘截断 → 死循环;生成器复用后已耗尽(迭代过一次再迭代为空)。


3. 单例模式(三种实现对比)

考点:单例 = 一个类全局只有一个实例;三种写法(模块级 / __new__ / 装饰器)都要会,并说清线程安全问题。

3.1 模块级单例

# singleton_module.py —— 模块级单例(Python 原生推荐)
class Config:
    def __init__(self):
        self.debug = True

# 模块只被 import 一次,天然单例
config = Config()

用法:任何地方 from singleton_module import config 拿到的都是同一对象。优点:最简单、无并发问题(解释器保证模块只初始化一次);缺点:不够"类内聚",无法防外面再 Config()。

3.2 __new__ 版单例

考点:__new__ 在 __init__ 前创建实例;用类属性缓存实例 + 双检锁保证线程安全。

# singleton_new.py —— __new__ 版(线程安全取价版)
import threading

class Singleton:
    _instance = None
    _lock = threading.Lock()

    def __new__(cls, *args, **kwargs):
        if cls._instance is None:            # 快速路径:避免每次都抢锁
            with cls._lock:                  # 双检锁:只有一个线程能创建
                if cls._instance is None:
                    cls._instance = super().__new__(cls)
        return cls._instance

    def __init__(self, name="default"):
        # 注意:__init__ 每次都会执行,赋值要幂等
        if not hasattr(self, "_inited"):
            self.name = name
            self._inited = True

a, b = Singleton("x"), Singleton("y")
print(a is b, a.name)                        # True  'x'(第二次 __init__ 被幂等跳过)
# 时间 O(1)(首建加锁一次),空间 O(1)

3.3 装饰器版单例

# singleton_deco.py —— 装饰器版(用 dict 缓存首建实例)
import threading

def singleton(cls):
    instances = {}
    lock = threading.Lock()
    def get_instance(*args, **kwargs):
        if cls not in instances:             # 双检锁
            with lock:
                if cls not in instances:
                    instances[cls] = cls(*args, **kwargs)
        return instances[cls]
    return get_instance

@singleton
class DBConn:
    def __init__(self):
        self.conn_id = id(self)              # 每次新实例 id 不同

c1, c2 = DBConn(), DBConn()
print(c1 is c2)                              # True
# 时间 O(1),空间 O(类数)

3.4 对比表格

版本 实现 线程安全 适用
模块级 import 机制 ✅ 天然安全 生产首选,最简单
__new__ 类属性缓存 + 双检锁 ✅ 必须用类封装时
装饰器 闭包 dict 缓存 ✅(加锁) 不想侵入类内部时

3.5 面试追问

Q1:__new__ 和 __init__ 区别?

__new__ 是创建实例的静态方法(cls 参数,返回实例);__init__ 是初始化实例(self 参数,返回 None)。单例应重写 __new__ 控制创建,__init__ 可用幂等标记防止重复初始化覆盖属性。

Q2:单例真的线程安全吗?怎么保证?

不加锁的"判断 + 赋值"两步在并发下可能建多个实例;标准做法是双检锁(先查后锁再查)或模块级(Python import 锁保证只执行一次)。

Q3:单例的缺点?

全局状态难测试、隐蔽依赖、违背开闭原则;"单例 vs 依赖注入"是经典的架构选择题,可答"并发安全的模块级单例 + 显式传参"折中。

易错点:__new__ 版里忘了 super().__new__(cls) 会返回 None;__init__ 重复执行把同名属性覆盖。


4. 线程 / 进程

4.1 生产者-消费者(threading + queue)

💡 心法(一句话):生产者「放货」、消费者「取货」,中间用线程安全的 queue.Queue 当缓冲区;队列满时生产者阻塞、空时消费者阻塞,各自都不空转。

🏷️ 类比:奶茶店:后厨(生产者)做好奶茶放进取餐台(队列),顾客(消费者)按顺序取;取餐台放满后厨就等一等,取餐台空了顾客就等一等。

🔍 逐步走查:1 个生产者、2 个消费者、容量 5:① 生产者放「P-0」→ 队列=[P-0],C0 取走 → 队列=[];② 放「P-1」→ C1 取走;③ ……放完 8 个后,生产者往队列放 2 个 None 毒丸(每个消费者一个);④ 消费者 get() 到 None 就 task_done() 并 break——没有毒丸,消费者会永远阻塞在 get(),q.join() 卡死。

考点:queue.Queue 内部已带锁,是线程安全队列;用它实现生产者-消费者,配合 task_done/join 优雅收尾。

# producer_consumer.py —— 生产者-消费者模型
import threading, queue, time, random

NUM_CONSUMERS = 2
q = queue.Queue(maxsize=5)          # 容量 5,满时生产阻塞

def producer(name, total=8):
    for i in range(total):
        item = f"{name}-{i}"
        q.put(item)                 # 满则阻塞直到有空位
        print(f"[生产者{name}] 放入 {item}, 队列大小={q.qsize()}")
        time.sleep(random.uniform(0.02, 0.05))
    for _ in range(NUM_CONSUMERS):
        q.put(None)                 # 毒丸:每消费者一个,通知其退出

def consumer(name):
    while True:
        item = q.get()              # 空则阻塞等待
        if item is None:            # 收到毒丸 → 标记完成并退出
            q.task_done()
            break
        print(f"[消费者{name}] 取出 {item}")
        q.task_done()               # 告诉队列该任务已完成
        time.sleep(random.uniform(0.05, 0.1))

threads = [threading.Thread(target=producer, args=("P",))]
threads += [threading.Thread(target=consumer, args=(f"C{i}",)) for i in range(NUM_CONSUMERS)]
for t in threads:
    t.start()
threads[0].join()                   # 等生产者放完(含毒丸)
q.join()                            # 等所有任务被 task_done(含毒丸),然后消费者退出
for c in threads[1:]:
    c.join()                        # 等消费者线程结束,脚本干净退出
print("全部线程已优雅退出")
# 时间:整体 O(任务数 × 每任务耗时),空间 O(队列容量)
# 注意:q.join() 配合 q.task_done() 缺一不可;消费者必须用毒丸(None)显式退出,否则卡死

4.2 线程池 ThreadPoolExecutor

💡 心法(一句话):线程池 = 一批「固定数量的临时工」,任务来了排队干、干完不辞退,省去反复开线程/关线程的开销。

🏷️ 类比:银行柜台:固定开几个窗口(max_workers),客户(任务)排队,谁空谁办;窗口不随客户来去而增减。

考点:线程池 = 复用受控数量的线程;map 简化批量任务;注意 GIL——线程池适合 IO 任务、不适合 CPU 密集。

# thread_pool.py —— 线程池(IO 密集场景合适)
from concurrent.futures import ThreadPoolExecutor, as_completed
import time

def fetch(url, delay=0.1):
    time.sleep(delay)               # 模拟网络 IO
    return f"{url} -> ok"

urls = [f"http://site{i}.com" for i in range(5)]

with ThreadPoolExecutor(max_workers=3) as pool:   # 最多 3 个线程并发
    # 方式一:map 保持输入顺序返回
    results = list(pool.map(fetch, urls))
    # 方式二:submit + as_completed 按完成顺序返回
    futures = [pool.submit(fetch, u) for u in urls]
    for f in as_completed(futures):
        print("完成:", f.result())
print("顺序结果:", results)
# 时间:max_workers=3 时总耗时 ≈ 5×0.1/3(并行摊薄),空间 O(任务数)

4.3 进程池 ProcessPoolExecutor

考点:进程池绕开 GIL 并行 CPU 密集任务;Windows 下必须 if __name__ == '__main__': 保护,否则递归创建子进程。

# process_pool.py —— 进程池(CPU 密集场景合适)
from concurrent.futures import ProcessPoolExecutor

def cpu_heavy(n: int) -> int:
    """模拟 CPU 密集计算(Python 大整数乘法会释放 GIL 吗?不释放,
    但进程各自独立解释器,可真正并行)"""
    total = 0
    for i in range(n):
        total += i * i
    return total

if __name__ == "__main__":          # Windows 必备保护,否则子进程无限 fork
    nums = [10_000_000] * 4
    with ProcessPoolExecutor(max_workers=4) as pool:
        results = list(pool.map(cpu_heavy, nums))
    print("进程池结果:", results[:2], "...")
# 时间:4 个 CPU 任务 ≈ 单核耗时的 1/4(真并行);空间:每进程独立内存

4.4 对比表格

手段 适用 关键限制 常用 API
线程 IO 密集(网络/文件) GIL 限制 CPU 并行 threading, queue
线程池 批量 IO 任务 线程切换开销、GIL ThreadPoolExecutor
进程池 CPU 密集 内存/启动开销、IPC 成本 ProcessPoolExecutor

4.5 面试追问

Q1:Python 多线程能加速 CPU 密集计算吗?

不能——GIL(全局解释器锁)保证同一时刻只有一个线程执行 Python 字节码;CPU 密集场景应改多进程或用 C 扩展(numpy)释放 GIL。

Q2:queue.Queue 为什么线程安全?

内部用 deque + 一把 mutex + 两个 Condition(not_empty/not_full),put/get 的"检查-等待-操作"都在锁内完成。

Q3:Q 大时生产者-消费者怎么防止数据丢失?

task_done() + q.join() 确保队列中所有项都被消费完再退出;生产者在 while running 循环里最后放毒丸(sentinel,如 None) 通知消费者退出,避免死等。

易错点:Windows 进程池忘 if __name__ == '__main__' 会报 RuntimeError;消费者 while True 没有退出条件会卡 join。


5. asyncio 协程

5.1 异步并发(asyncio.sleep 模拟 IO)

考点:async def + await + asyncio.gather;协程在 await 处让出控制权,IO 期间切换执行其他协程——总耗时 ≈ 最慢任务,而非任务之和。

# asyncio_basic.py —— 协程并发模拟爬虫
import asyncio

async def fetch_page(name: str, cost: float) -> str:
    print(f"开始抓取 {name}")
    await asyncio.sleep(cost)        # 模拟 IO 等待,期间让出 CPU
    print(f"抓取完成 {name}")
    return f"{name}:{cost}"

async def main():
    # gather:并发执行 3 个协程,总耗时 ≈ max(0.1,0.2,0.05)=0.2s 而非 0.35s
    results = await asyncio.gather(
        fetch_page("a.com", 0.1),
        fetch_page("b.com", 0.2),
        fetch_page("c.com", 0.05),
    )
    print(results)

asyncio.run(main())
# 时间:O(max(各任务耗时)) 并发摊薄;空间:每个协程栈 O(1) 级别
# 考点:await 是"交出控制权"的挂起点,asyncio.sleep 模拟真实 IO 让事件循环周转

5.2 asyncio.Queue 消费者模型

💡 心法(一句话):和线程版长得几乎一样,只是 put/get 变成可 await 的协程——队列空/满时不是阻塞线程,而是「挂起让位」给别的协程。

🏷️ 类比:流水线工位:机器(协程)发现料槽(队列)空了,不是傻站着占工位,而是先去做别的事(await 让出),料到了再回来。

考点:asyncio.Queue 是协程版队列,put/get 自身是协程可 await;用于协程间解耦——生产者放、消费者取。

# asyncio_queue.py —— 异步生产者/消费者
import asyncio, random

async def producer(q: asyncio.Queue, n: int):
    for i in range(n):
        await q.put(i)                       # 满则挂起
        print(f"producer 放入 {i}")
        await asyncio.sleep(0.02)

async def consumer(q: asyncio.Queue, name: str):
    while True:
        item = await q.get()                 # 空则挂起
        if item is None:                     # 毒丸:退出信号
            q.task_done()
            break
        print(f"consumer-{name} 取出 {item}")
        q.task_done()
        await asyncio.sleep(0.03)

async def main():
    q = asyncio.Queue(maxsize=3)
    pro = asyncio.create_task(producer(q, 6))
    cons = [asyncio.create_task(consumer(q, str(i))) for i in range(2)]
    await pro
    await q.join()                           # 等真实任务全部 task_done
    for _ in cons:
        await q.put(None)                    # 毒丸:向队列放 None,每个消费者一个
    await asyncio.gather(*cons)              # 等所有消费者协程退出

asyncio.run(main())
# 时间:生产 6 项 ≈ 6×0.02 与消费并行,总耗受众消费速度影响
# 规范收尾:每消费者一个毒丸 None(或 task.cancel()),否则 q.join()/gather 永不返回

5.3 面试追问

Q1:协程和线程的区别?

协程是用户态调度、单线程内协作式切换,没有内核态切换与锁竞争开销;线程是内核态抢占式调度。协程适合大量 IO 等待,不适合 CPU 密集。

Q2:asyncio.run() 做了哪些事?

创建并运行事件循环、执行主协程、最后关闭循环与默认执行器;Python 3.7+ 统一入口,替代手动的 loop.run_until_complete()。

Q3:真正的网络 IO 用什么库?

aiohttp(HTTP)、httpx.AsyncClient;asyncio.sleep 只用于面试演示"挂起点让出"的机制。

易错点:忘了 await(协程不执行返回 coroutine 对象);在同步函数里 asyncio.run 会报"在运行中的事件循环";消费者退出条件缺失导致 q.join() 永不返回。


6. 轮子题(缓存/栈经典实现)

6.1 手写 LRU Cache(OrderedDict)

考点:LRU(最近最少使用):容量满时淘汰最久未访问的键。用 OrderedDict:get/move_to_end 实现"访问即置顶";popitem(last=False) 弹出"最久未使用"。

# lru_cache.py —— LRU Cache(OrderedDict 版,标准答案)
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()           # 插入序 = 访问序

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)          # 访问过 → 移到末尾 = 最新
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)      # 更新也视为"最新访问"
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # 弹出最旧的(队首)

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1))                          # 1 → 键 1 变最新,键 2 变最旧
cache.put(3, 3)                              # 容量满 → 淘汰 2
print(cache.get(2))                          # -1
# 时间:get/put 均 O(1);空间:O(capacity)
# 进阶问法:不用 OrderedDict 怎么实现?→ dict + 双向链表 + 哈希表,同样 O(1)

6.2 手写 LFU

💡 心法(一句话):LFU = 「谁用得最少淘汰谁」:每个键记访问频率,满了就踢掉「频率最低 + 最早进来」的那个。

🏷️ 类比:健身房储物柜:天天来的人(高频)保留;只来过一次的人(低频)先清走;频率一样时,先占柜子的人先走(时间早的淘汰)。

🔍 逐步走查:容量 2:① put(1,1) → key_val={1:(1,1)},freq_map={1:{1}},min_freq=1;② put(2,2) → key_val={1:(1,1), 2:(2,1)},freq_map={1:{1,2}};③ get(1) → _touch(1):从 freq=1 桶删 1,该桶空且 freq==min_freq → min_freq=2,1 进入 freq=2 桶(随后 put 时 min_freq 会被重置为 1);④ put(3,3) 容量满 → 从 freq_map[1] 队首挑 victim=2 删掉,把 3 放进 freq=1 桶;⑤ get(2) → -1。

考点:LFU(最不频繁使用):淘汰"访问频率最低"的键,频率相同淘汰最早。频率桶结构:freq -> OrderedDict(键值),维护 min_freq。

# lfu_cache.py —— LFU Cache(频率桶 + OrderedDict,O(1) 版本思路)
from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_val = {}                    # key -> (value, freq)
        self.freq_map = defaultdict(OrderedDict)  # freq -> OrderedDict<key, None>
        self.min_freq = 0

    def _touch(self, key: int) -> None:
        """key 访问频率 +1,并移动频率桶"""
        value, freq = self.key_val[key]
        del self.freq_map[freq][key]         # 从旧频率桶移除
        if not self.freq_map[freq] and freq == self.min_freq:
            self.min_freq += 1               # 旧最小桶空了 → 提升
        self.key_val[key] = (value, freq + 1)
        self.freq_map[freq + 1][key] = None  # 放入新频率桶尾部

    def get(self, key: int) -> int:
        if key not in self.key_val:
            return -1
        self._touch(key)
        return self.key_val[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_val:
            self.key_val[key] = (value, self.key_val[key][1])
            self._touch(key)
            return
        if len(self.key_val) >= self.capacity:
            victim = next(iter(self.freq_map[self.min_freq]))  # 最小频率桶的队首
            self.freq_map[self.min_freq].popitem(last=False)
            del self.key_val[victim]
        self.key_val[key] = (value, 1)
        self.freq_map[1][key] = None
        self.min_freq = 1

lfu = LFUCache(2)
lfu.put(1, 1); lfu.put(2, 2)
lfu.get(1)                                   # 键 1 freq=2
lfu.put(3, 3)                                # 淘汰 freq=1 的键 2
print(lfu.get(2))                            # -1
# 时间:get/put 均摊 O(1);空间:O(capacity)
# 追问:为何 LFU 要"频率相同再按时间"淘汰 → 防止一个冷键刷两次频率霸占缓存

6.3 手写最小栈

💡 心法(一句话):空间换时间:再开一个「最小值栈」,它的栈顶永远记录当前数据栈里的最小值,于是 get_min 和 push/pop 一样都是 O(1)。

🏷️ 类比:登山队每走一步都记一张「当前最低海拔」便签,叠成一摞;往下撤一步就撕掉一张便签,随时知道此刻的海拔最低点。

🔍 逐步走查:依次 push 3、5、2、1:

操作 stack min_stack get_min
push 3 [3] [3] 3
push 5 [3,5] [3](5>3 不压) 3
push 2 [3,5,2] [3,2] 2
push 1 [3,5,2,1] [3,2,1] 1
pop(弹 1) [3,5,2] [3,2] 2

关键:pop 时若 stack.pop() 的值 == min_stack 栈顶,两个栈一起弹。比较用 <= 而非 <——多个相同最小值必须都记录,否则弹掉一个后 get_min 会「假变」大。

考点:O(1) 取最小值的栈:辅助栈同步记录"当前栈状态下的最小值",入栈时 min_stack 只压更小的。

# min_stack.py —— 最小栈(辅助栈同步法)
class MinStack:
    def __init__(self):
        self.stack = []                      # 数据栈
        self.min_stack = []                  # 辅助栈:栈顶永远是当前最小值

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)       # 新最小值入辅助栈

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()             # 弹出的是当前最小值 → 同步弹

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]

ms = MinStack()
for v in (3, 5, 2, 1):
    ms.push(v)
print(ms.get_min())                          # 1
ms.pop(); print(ms.get_min())                # 2
# 时间:四个操作均 O(1);空间:O(n)(最坏辅助栈同数据栈等长)
# 追问:不借助辅助栈?→ 差值法/存 (value, min) 元组,本质一样

6.4 手写单例装饰器(复用 3.3,快速背诵版)

# singleton_quick.py —— 10 秒默写版:装饰器单例
import threading

def singleton(cls):
    _instances, _lock = {}, threading.Lock()
    def get(*args, **kwargs):
        if cls not in _instances:
            with _lock:
                if cls not in _instances:
                    _instances[cls] = cls(*args, **kwargs)
        return _instances[cls]
    return get

@singleton
class C:
    pass

assert C() is C()
print("单例 OK")
# 时间 O(1),空间 O(类数);双检锁保证线程安全

6.5 面试追问

Q1:LRU 为什么用双向链表 + 哈希表?(不用 OrderedDict 时)

哈希表 O(1) 定位节点,双向链表 O(1) 把节点摘到表头(单向链表删除需要前驱,做不到 O(1));在 Python 里 OrderedDict 底层就是"dict + 双向链表"。

Q2:LRU 和 LFU 应用场景差异?

LRU 适合"时间局部性"(新闻热点、图片缓存);LFU 适合"频率局部性"(广告点击、用户画像统计)。LFU 实现复杂度更高,且存在"旧热点占位"问题,业界常用 LRU-K / TinyLFU(如 Redis 近似 LFU) 折中。

Q3:get_min 的等号为什么是 <=?

多个相同最小值时,辅助栈必须都记录;如果只压 <,弹出其中一个 2 时把辅助栈的 2 弹掉,另一个 2 还在栈中但 get_min 会错误变 3。

易错点:LRU 忘 move_to_end(get 不刷新序 = 白写);LFU 忘维护 min_freq;最小栈 pop 判断用值相等而不用下标。


7. 常用数据结构实现

7.1 用栈实现队列

考点:两个栈(in/out)倒腾:入队进 in;出队时若 out 空,把 in 全部倒入 out(倒一次的反转保证 FIFO),均摊 O(1)。

# stack_to_queue.py —— 两个栈实现队列(LeetCode 232)
class MyQueue:
    def __init__(self):
        self.in_stack = []       # 入队专用
        self.out_stack = []      # 出队专用

    def _transfer(self):
        if not self.out_stack:               # 只有 out 空了才倒,保护顺序
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

q = MyQueue()
for i in (1, 2, 3):
    q.push(i)
print(q.pop(), q.pop(), q.pop())             # 1 2 3(FIFO)
# 时间:push O(1);pop/peek 均摊 O(1)(每个元素最多被搬一次);空间 O(n)

7.2 用队列实现栈

💡 心法(一句话):队列是「先进先出」,要伪装成栈(后进先出)——每次 push 后把新元素前面的人全部挪到队尾,让新元素「插队」到队首。

🏷️ 类比:食堂排队打饭,想让最后来的人先打——管理员让新来的站队首,原来排队的人全体绕一圈站到新来的人后面。

🔍 逐步走查:push 1 → q=[1];push 2 → 先 [1,2],再把前 1 个挪到队尾 → [2,1];push 3 → 先 [2,1,3],把前 2 个挪到队尾 → [3,2,1]。此时 pop() 直接 popleft() 得 3 → 依次 3、2、1,后进先出 ✅。代价:push 是 O(n)。

考点:单队列即可:push 时把新元素放队尾,再把前面 n-1 个元素依次挪到队尾,让新元素"垫底"变队首,pop 直接出队首。

# queue_to_stack.py —— 单个队列实现栈(LeetCode 225)
from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):     # 把队首 n-1 个转到队尾
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()              # 队首就是"最后 push"的元素

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

s = MyStack()
for i in (1, 2, 3):
    s.push(i)
print(s.pop(), s.pop(), s.pop())             # 3 2 1(LIFO)
# 时间:push O(n)(挪 n-1 次)、pop O(1);空间 O(n)

7.3 字符串匹配 KMP

💡 心法(一句话):KMP = 主串指针永不下台阶,失配时只让模式串按 next 数组「聪明地后退」,把暴力法 O(mn) 的重复比较省成 O(m+n)。

🏷️ 类比:翻词典找词:翻到「ababaca」中 c 对不上时,你不会退回开头重翻(暴力法),而是根据「已经对齐的部分」直接滑到下一个可能的位置——next[i] 记的就是「这一格已经对上了几个字符,可以放心跳过」。

🔍 逐步走查:next 数组怎么来的?p = "ababaca",nxt[i] = p[:i] 的最长相等真前后缀长度,j 是「已对齐前缀长度」:

i p[i] 比较过程 新 j nxt[i]
1 b b ≠ a,j=0 无需回退 0 0
2 a a == a → j=1 1 1
3 b b == b → j=2 2 2
4 a a == a → j=3 3 3
5 c c≠b → j=nxt[2]=1;c≠b → j=nxt[0]=0;c≠a 0 0
6 a a == a → j=1 1 1

得到 nxt = [0, 0, 1, 2, 3, 0, 1]。匹配阶段同理:主串 abcababacabd 遇失配只做 j = nxt[j-1],主串下标 i 永远只前进不后退 → 线性。完整匹配时返回 i - len(p) + 1。

考点:核心是 next 数组(部分匹配表):模式串失配时,主串指针不回溯,模式串跳到 next 处继续。构建 next 与匹配两段都是双指针。

# kmp.py —— KMP 字符串匹配(返回模式串在主串中首次出现的位置)
def build_next(p: str) -> list:
    """next[i] = p[:i] 的最长相等真前后缀长度(失配时跳转的偏移)"""
    nxt = [0] * len(p)
    j = 0                                    # 已匹配前缀长度
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:        # 失配回退
            j = nxt[j - 1]
        if p[i] == p[j]:                     # 匹配成功,公共前后缀 +1
            j += 1
        nxt[i] = j
    return nxt

def kmp_search(text: str, p: str) -> int:
    if not p:
        return 0
    nxt = build_next(p)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != p[j]:
            j = nxt[j - 1]                   # 主串不回溯,只回溯模式串
        if text[i] == p[j]:
            j += 1
        if j == len(p):                      # 完整匹配
            return i - len(p) + 1
    return -1

print(build_next("ababaca"))                 # [0,0,1,2,3,0,1]
print(kmp_search("abcababacabd", "ababaca")) # 3
# 时间:O(m + n)(m=主串长,n=模式串长),最坏也是线性;空间 O(n)

7.4 最长回文子串(中心扩展)

💡 心法(一句话):把字符串想成以每个位置(含两字符中间的空隙)为中心「向两边照镜子」,能照多远回文就有多长——一共 2n-1 面镜子。

🏷️ 类比:站在两面平行镜中间照自己:以你(单个字符)为中心看奇数长度镜像;把镜缝对准你俩中间(空隙)看偶数长度镜像。

🔍 逐步走查:s = "babad",只跟 i=1(字符 a):① expand(1,1):s[1]==s[1] → 扩到 s[0]='b' vs s[2]='b' 相等 → 再扩越界 → 返回 (0,3) → 「bab」,长 3;② expand(1,2):'a' vs 'b' 不等 → 返回 (1,1) 无效;③ i=2 的 expand(2,2) 得「aba」也是长 3,没超过就保留第一个 → 最终返回「bab」。注意 return lo+1, hi 是因为多扩了一步要回退一格。

考点:中心扩展:每个字符(及相邻空隙)作为回文中心向两边扩;总共有 2n-1 个中心(含字符间空隙),O(n²)。Manacher 是进阶 O(n),先背中心扩展。

# longest_palindrome.py —— 最长回文子串:中心扩展
def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    def expand(lo: int, hi: int) -> tuple:
        """从 (lo,hi) 中心向外扩,返回 (起点, 终点) 左闭右开"""
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi                    # 多扩了一步,回退一格

    best = (0, 0)
    for i in range(len(s)):
        odd = expand(i, i)                   # 奇数长度中心:字符本身
        even = expand(i, i + 1)              # 偶数长度中心:字符间空隙
        for cand in (odd, even):
            if cand[1] - cand[0] > best[1] - best[0]:
                best = cand
    return s[best[0]:best[1]]

for t in ("babad", "cbbd", "abba", "a"):
    print(t, "->", longest_palindrome(t))    # bab/aba、bb、abba、a
# 时间:O(n²)(2n-1 个中心 × 每次最坏扩 n);空间 O(1)
# 追问:O(n) 解法?→ Manacher:回文半径数组 + 最右臂界镜像对称优化

7.5 对比表格

题目 核心技巧 时间 空间
栈→队列 双栈倒腾,均摊 push O(1) / pop 均摊 O(1) O(n)
队列→栈 入队后把队首转到队尾 push O(n) / pop O(1) O(n)
KMP next 数组,主串不回溯 O(m+n) O(n)
最长回文 中心扩展 / Manacher O(n²) / O(n) O(1) / O(n)

7.6 面试追问

Q1:KMP 的 next 数组和"暴力"差在哪?

暴力失配时主串指针 i 回到 i-j+1 重新比(O(mn));KMP 利用模式串自身的"最长公共前后缀"信息,失配只回溯模式串指针 j 到 next[j-1],主串 i 不回退,所以线性。

Q2:中心扩展为什么有 2n-1 个中心?

n 个字符各是 1 个"奇数中心",相邻字符之间有 n-1 个"偶数中心"(空隙),共 2n-1。

Q3:栈实现队列里,为什么 out 为空才转移?

若 out 非空时也转移,会把上层还没出完的元素顺序打乱;只在 out 为空时整批倒入,保证"批内先进先出、批间顺序衔接",均摊 O(1)。

易错点:KMP 构建 next 与匹配的 while 逻辑复制粘贴易错,背熟构建段;中心扩展 return 前要"回退一步"(lo+1, hi),否则多扣边界字符。


8. 设计模式(每段可运行)

8.1 观察者模式

考点:发布-订阅:主题维护监听者列表,状态变化时通知所有订阅者;解耦"事件的产生方"与"事件的消费方"。

# observer.py —— 观察者模式(订阅-发布)
class Subject:
    """被观察的主题"""
    def __init__(self):
        self._observers = []                 # 订阅者列表

    def attach(self, observer):
        self._observers.append(observer)

    def detach(self, observer):
        self._observers.remove(observer)

    def notify(self, msg):
        for obs in self._observers:
            obs.update(msg)                  # 广播消息

class EmailNotifier:
    def update(self, msg):
        print(f"[邮件通知] {msg}")

class SmsNotifier:
    def update(self, msg):
        print(f"[短信通知] {msg}")

subject = Subject()
subject.attach(EmailNotifier())
subject.attach(SmsNotifier())
subject.notify("订单已支付")                  # 两个订阅者同时收到
# 时间:通知 O(订阅者数),空间 O(订阅者数)
# 追问:改进版 → 事件总线/回调函数列表;Python 也可用回调代替类接口

8.2 策略模式(含注册表字典版)

💡 心法(一句话):把「算运费、算折扣」这类可变算法抽成独立对象/函数,运行时像换电池一样换策略,而不是写一堆 if/elif。

🏷️ 类比:点外卖选配送方式:「标准配送」「同城急送」是两个可替换的策略,选中哪个就用哪套计价规则,APP 主体逻辑不用改。

考点:把算法族封装成可替换的策略对象,运行时切换;注册表字典是 Python 实用变体——用 dict 把策略名映射到实现,免去 if/elif 分支。

# strategy.py —— 策略模式 + 注册表字典版
class ShippingFee:
    def calc(self, weight): raise NotImplementedError

class StandardFee(ShippingFee):
    def calc(self, weight): return 10 + 2 * weight

class ExpressFee(ShippingFee):
    def calc(self, weight): return 20 + 5 * weight

# 注册表字典:策略名 -> 策略实例(替代 if/elif 链)
REGISTRY = {"standard": StandardFee(), "express": ExpressFee()}

def calc_fee(weight: float, strategy: str) -> float:
    if strategy not in REGISTRY:
        raise ValueError(f"未知策略: {strategy}")
    return REGISTRY[strategy].calc(weight)

print(calc_fee(5, "standard"))                # 20.0
print(calc_fee(5, "express"))                 # 45.0
# 开闭原则:新增策略只需往 REGISTRY 注册,不改调用方
# 追问:另一种实现 → 函数直接作为策略(Python 一等公民):REGISTRY = {"standard": fn}

8.3 工厂模式(简单工厂 / 工厂方法)

💡 心法(一句话):把「创建对象」的细节收进工厂:简单工厂一个函数按名字造产品;工厂方法把「造哪种产品」的决定权交给子类,扩展新产品不改旧代码。

🏷️ 类比:点餐柜台:简单工厂 = 一个服务员按你点的菜名做菜;工厂方法 = 每个厨师(子工厂)只负责自己拿手的一道菜,加新菜只需多雇一个厨师。

考点:简单工厂:一个工厂函数按参数返回不同产品(if/elif 集中一处);工厂方法:把"创建逻辑"下沉到子类(每个工厂子类只创建一种产品),符合开闭原则。

# factory.py —— 简单工厂 + 工厂方法
class Animal:
    def speak(self): raise NotImplementedError

class Dog(Animal):
    def speak(self): return "汪汪"

class Cat(Animal):
    def speak(self): return "喵喵"

# ---- 简单工厂:一个函数按名称创建不同产品 ----
class SimpleFactory:
    @staticmethod
    def create(kind: str) -> Animal:
        if kind == "dog":
            return Dog()
        if kind == "cat":
            return Cat()
        raise ValueError(kind)

# ---- 工厂方法:每个子工厂只负责一种产品,扩展新动物不改旧代码 ----
class AnimalFactory:
    def create(self) -> Animal:
        raise NotImplementedError

class DogFactory(AnimalFactory):
    def create(self) -> Animal:
        return Dog()

class CatFactory(AnimalFactory):
    def create(self) -> Animal:
        return Cat()

f1 = SimpleFactory()
print(f1.create("dog").speak())                # 汪汪
for factory in (DogFactory(), CatFactory()):   # 工厂方法:面向基类编程
    print(factory.create().speak())            # 汪汪 / 喵喵
# 简单工厂违反开闭(加产品要改 create);工厂方法用多态扩展,不改旧类

8.4 面试追问

Q1:观察者和"直接调用"区别?

直接调用是编译期绑定、耦合;观察者把"谁关心"延迟到运行时注册,事件源不关心订阅者细节,方便动态增删(消息队列、事件总线都是它的宏观形态)。

Q2:策略模式和 if/elif 相比好在哪?

if/elif 每次新增策略都要改业务代码(违反开闭原则);策略模式把每个算法独立成类,配合注册表可以做到"新增策略只加一行注册",且可组合、可测试。

Q3:简单工厂 / 工厂方法 / 抽象工厂区别?

简单工厂:一个函数按参数造一种产品;工厂方法:子类决定创建一种产品;抽象工厂:一个接口创建一族产品(如 Android 主题工厂同时生成按钮+输入框)。复杂度递增,按需选型。

易错点:观察者 notify 时列表被修改(遍历时增删订阅者)→ 先拷贝 list;策略注册表 key 拼写错误被静默忽略 → 显式 raise ValueError。


9. 工具类三件套

9.1 retry 装饰器(指数退避)

💡 心法(一句话):调用不稳定的远程服务失败时,「等一会儿再试」,且每次等待翻倍(1s→2s→4s)并加随机抖动,防止所有失败者同时重试把服务打崩。

🏷️ 类比:打不进客服电话就过一会儿再打,而且越等越久(指数退避);故意错开时间打(抖动),避免所有人同一秒一起拨号造成占线风暴。

考点:重试 + 指数退避(每次等待翻倍 + 抖动),限制次数与最终异常抛出;这是线上调用任何远程服务的标配脚手架。

# retry_deco.py —— 重试装饰器(指数退避)
import time, random

def retry(max_tries: int = 3, base_delay: float = 0.1, backoff: float = 2.0):
    """max_tries: 最多尝试次数;base_delay: 首次等待;backoff: 退避倍数"""
    def decorator(func):
        def wrapper(*args, **kwargs):
            for attempt in range(1, max_tries + 1):
                try:
                    return func(*args, **kwargs)
                except Exception as e:
                    if attempt == max_tries:
                        raise                      # 最后一次失败,抛出原异常
                    wait = base_delay * (backoff ** (attempt - 1))  # 0.1, 0.2, 0.4...
                    wait += random.uniform(0, wait * 0.2)           # 加抖动防"惊群"
                    print(f"第 {attempt} 次失败({e}),{wait:.2f}s 后重试")
                    time.sleep(wait)
        return wrapper
    return decorator

@retry(max_tries=3)
def flaky_call():
    if random.random() < 0.6:                  # 60% 概率失败
        raise ConnectionError("网络抖动")
    return "成功"

print(flaky_call())
# 时间:最多 O(3) 次 × 退避等待;经典退避序列 0.1 → 0.2 → 0.4
# 追问:何时不该无脑重试 → 4xx 业务错误(幂等性/参数错误)不重试,5xx/超时才重试

9.2 计时器上下文管理器(contextmanager)

💡 心法(一句话):把「进入 with 前」和「退出 with 后」的代码用生成器拼起来:yield 之前是 __enter__,之后是 __exit__,天然适合计时、加锁、关文件。

🏷️ 类比:健身房存包:进门(with 进入)按秒表,出门(with 结束)停表并广播耗时——用 try/finally 保证「中途摔倒」(异常)也会停表。

考点:@contextmanager 把生成器变成上下文管理器:yield 前是 __enter__,yield 后是 __exit__(异常时也会执行 yield 后代码,可用 try/finally 包住)。

# timer_ctx.py —— 计时器上下文管理器
from contextlib import contextmanager
import time

@contextmanager
def timer(name: str = "block"):
    start = time.perf_counter()
    try:
        yield                                # 进入 with 体的位置
    finally:
        print(f"[{name}] 耗时 {time.perf_counter() - start:.4f}s")

with timer("查询数据库"):
    time.sleep(0.2)                          # 模拟业务

try:
    with timer("批量写入"):
        time.sleep(0.1)
        raise RuntimeError("写入失败")       # 异常也会走 finally 打印耗时
except RuntimeError as e:
    print("捕获异常:", e)                    # 演示异常路径,脚本不崩溃
# 时间 O(任务耗时);用 try/finally 保证异常路径也能打印
# 追问:手写 __enter__/__exit__ 类版也行,contextmanager 是生成器版捷径

9.3 参数校验装饰器

考点:装饰器做前置校验:限制参数类型/取值范围/必填;校验失败抛 ValueError/TypeError,把"防御式检查"从业务代码里剥离。

# validate_deco.py —— 参数校验装饰器
def require_types(**expected):
    """校验关键字参数类型,如 @require_types(age=int, name=str)"""
    def decorator(func):
        def wrapper(*args, **kwargs):
            for k, t in expected.items():
                if k in kwargs and not isinstance(kwargs[k], t):
                    raise TypeError(f"参数 {k} 期望 {t.__name__},得到 {type(kwargs[k]).__name__}")
            return func(*args, **kwargs)
        return wrapper
    return decorator

def require_range(name: str, lo: float, hi: float):
    """校验数值参数取值区间"""
    def decorator(func):
        def wrapper(*args, **kwargs):
            if name in kwargs and not (lo <= kwargs[name] <= hi):
                raise ValueError(f"参数 {name} 需在 [{lo}, {hi}] 内")
            return func(*args, **kwargs)
        return wrapper
    return decorator

@require_types(age=int)
@require_range("age", 0, 150)
def register(name: str, age: int) -> str:
    return f"注册成功: {name}, {age} 岁"

print(register(name="Alice", age=25))        # 注册成功
try:
    register(name="Bob", age="二十五")        # TypeError
except TypeError as e:
    print("校验拦截:", e)
# 时间 O(校验参数个数),空间 O(参数个数)

9.4 面试追问

Q1:指数退避为什么还要加抖动(jitter)?

所有客户端同时失败会同时重试,等待序列一致形成重试风暴(惊群);加随机抖动让重试时刻分散,这是 AWS/Google 通用实践。

Q2:@contextmanager 的 yield 前后代码分别在什么时候执行?

yield 前在 with 进入时执行(相当于 __enter__);yield 后在 with 块结束(含异常)时执行(相当于 __exit__);用 try/finally 包住 yield 可以保证异常时清理资源。

Q3:校验装饰器放业务里还是框架层?

校验是横切关注点,应收敛在装饰器/中间件统一实现(DRY);但类型校验 Python 更常用 pydantic、dataclass 等声明式方案,装饰器适合轻量场景。

易错点:retry 最后一次失败忘了 raise(把异常吞成 None);contextmanager 版本忘了 try/finally(异常时不打印耗时);校验装饰器只查 kwargs 漏掉位置参数导致误判。


附录:冲刺检查清单

☐ 装饰器:3 层(带参) / 2 层(无参) / @wraps / return result
☐ 生成器:yield 挂起 / take 截断无限序列 / yield from 透传
☐ 单例:模块级(推荐) / __new__ 双检锁 / 装饰器 dict 缓存
☐ 线程:queue.Queue + task_done/join;进程池 Windows 要 __main__ 保护
☐ asyncio:gather 并发 / Queue 毒丸退出 / asyncio.run
☐ LRU:move_to_end + popitem(last=False);LFU:频率桶 + min_freq
☐ 最小栈:辅助栈同步最值;队列/栈互转:倒腾法
☐ KMP:next 数组构建段单独默写;最长回文:中心扩展 2n-1
☐ 观察者/策略/工厂:注册表字典 / 简单 vs 工厂方法
☐ retry 指数退避 + 抖动、contextmanager 计时、参数校验

所有代码均可用 python 文件名.py 直接运行;每个文件的运行结果已写在注释行中。

教程来源:Akun-python/autumn-recruitment。 MIT 许可证全文。