08 · 高频手撕代码背诵手册(Python 3)¶
面向秋招算法/后端岗位的 背诵级手写代码合集。 所有代码均为 标准库实现、可直接运行,每段都带注释与 时间/空间复杂度标注。 结构:每个小节先给「考点」一句话 → 完整代码 → 「面试追问」。 背诵策略:先默写主框架,再补细节(边界条件、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 万能签名并保持返回值。
核心概念¶
(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["🛠️ 工具类三件套"]
Hand --> Sort["🔢 高频排序三件套"]
- 🎁 装饰器四件套:无参装饰器(两层函数)、带参装饰器(三层函数)、
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 的关系。 - 🔢 高频排序三件套:快排(分治 + 哨兵,平均 O(n log n))、归并(稳定、O(n) 空间)、堆排序(原地、O(n log n))要能手写并对比稳定性与适用场景;先背「答题模板 + 复杂度口诀」稳住节奏,再补排序细节。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# 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)
slow_add 耗时 0.1005s 3
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 层区分开
Hello, Alice Hello, Alice Hello, Alice
'Alice'
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 文档依赖它
bad : wrapper wrapper 自己的文档 good : sub 两数相减
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 次调用 ping pong:1 第 2 次调用 ping pong:2
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。
💬 答法提示:追问「装饰器开销多大」→ 答「O(1) 包装 + 每次调用多一个函数栈帧」;问「给装饰器加参数」→ 答「再包一层函数收参数,变为 3 层」。先答结构(几层、谁包谁)再答细节,节奏最快。
易错点:忘写 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);可无限生成,不占内存
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
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 项,而非全部序列)
[0, 1, 2, 3, 4] [0, 1, 2, 3, 4]
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(嵌套深度)(递归栈)
['outer-before', 'sub-start:1', 'sub-end:1', 'outer-after'] [1, 2, 3, 4, 5]
2.4 面试追问¶
Q1:生成器和普通函数区别?
① 生成器含
yield,调用不执行,返回生成器对象;② 每next执行到下一个yield并挂起,保存局部状态;③ 惰性求值内存占用小;④ 迭代一次即耗尽。
Q2:yield from 相比手动 for x in sub: yield x 的好处?
它还会处理返回值(
return的值变成yield from表达式的值),并能在双向通信时透传send/throw;手写 for 循环做不到这两点。
Q3:生成器有什么用(工程场景)?
① 处理超大数据/流式读取不爆内存;② 协程的基础;③ 惰性流水线(如日志解析管道)。
💬 答法提示:追问「生成器和迭代器区别」→ 迭代器是协议(
__iter__/__next__),生成器是它的便捷实现;追问「内存占用」→ O(1),每次只产一个值、用完即弃。
易错点:无限生成器忘截断 → 死循环;生成器复用后已耗尽(迭代过一次再迭代为空)。
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)
True x
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(类数)
True
3.4 对比表格¶
| 版本 | 实现 | 线程安全 | 适用 |
|---|---|---|---|
| 模块级 | import 机制 | ✅ 天然安全 | 生产首选,最简单 |
__new__ |
类属性缓存 + 双检锁 | ✅ | 必须用类封装时 |
| 装饰器 | 闭包 dict 缓存 | ✅(加锁) | 不想侵入类内部时 |
3.5 面试追问¶
Q1:__new__ 和 __init__ 区别?
__new__是创建实例的静态方法(cls 参数,返回实例);__init__是初始化实例(self 参数,返回 None)。单例应重写__new__控制创建,__init__可用幂等标记防止重复初始化覆盖属性。
Q2:单例真的线程安全吗?怎么保证?
不加锁的"判断 + 赋值"两步在并发下可能建多个实例;标准做法是双检锁(先查后锁再查)或模块级(Python import 锁保证只执行一次)。
Q3:单例的缺点?
全局状态难测试、隐蔽依赖、违背开闭原则;"单例 vs 依赖注入"是经典的架构选择题,可答"并发安全的模块级单例 + 显式传参"折中。
💬 答法提示:问「为什么不用全局变量」→ 答「全局变量人人可改、没有初始化时机控制;单例把创建收敛到一处」;进阶加分:元类重写
__call__也能实现单例,Python 3.6+ 模块级天然单例最推荐。
易错点:__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)显式退出,否则卡死
[生产者P] 放入 P-0, 队列大小=1 [消费者C0] 取出 P-0
[生产者P] 放入 P-1, 队列大小=1[消费者C1] 取出 P-1
[生产者P] 放入 P-2, 队列大小=1
[消费者C0] 取出 P-2
[生产者P] 放入 P-3, 队列大小=1
[消费者C1] 取出 P-3
[生产者P] 放入 P-4, 队列大小=1[消费者C0] 取出 P-4
[生产者P] 放入 P-5, 队列大小=1 [消费者C1] 取出 P-5
[生产者P] 放入 P-6, 队列大小=1 [消费者C0] 取出 P-6
[生产者P] 放入 P-7, 队列大小=1
[消费者C1] 取出 P-7
全部线程已优雅退出
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(任务数)
完成: http://site2.com -> ok 完成: http://site1.com -> ok 完成: http://site0.com -> ok 完成: http://site3.com -> ok 完成: http://site4.com -> ok 顺序结果: ['http://site0.com -> ok', 'http://site1.com -> ok', 'http://site2.com -> ok', 'http://site3.com -> ok', 'http://site4.com -> ok']
4.3 进程池 ProcessPoolExecutor¶
考点:进程池绕开 GIL 并行 CPU 密集任务;Windows 下必须 if __name__ == '__main__': 保护,否则递归创建子进程。
🔬 示例代码(需在独立环境中运行):
multiprocessing/socket等需要独立进程或对端,notebook 单进程环境无法演示(Jupyter 中__name__ == '__main__'恒成立,进程池会挂起),请保存为.py文件运行。
# 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) 通知消费者退出,避免死等。
💬 答法提示:问「GIL 能去掉吗」→ 答「去掉会拖慢单线程并破坏 C 扩展兼容,所以 CPython 保留;IO 密集用线程、CPU 密集用进程/协程」;问「队列容量设多大」→ 答「按生产者速度 × 最长容忍延迟估算,满了就阻塞形成背压,这本身是流控手段」。
易错点: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)
await main()
# 时间:O(max(各任务耗时)) 并发摊薄;空间:每个协程栈 O(1) 级别
# 考点:await 是"交出控制权"的挂起点,asyncio.sleep 模拟真实 IO 让事件循环周转
开始抓取 a.com 开始抓取 b.com 开始抓取 c.com 抓取完成 c.com
抓取完成 a.com
抓取完成 b.com ['a.com:0.1', 'b.com:0.2', 'c.com:0.05']
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) # 等所有消费者协程退出
await main()
# 时间:生产 6 项 ≈ 6×0.02 与消费并行,总耗受众消费速度影响
# 规范收尾:每消费者一个毒丸 None(或 task.cancel()),否则 q.join()/gather 永不返回
producer 放入 0 consumer-0 取出 0 producer 放入 1 consumer-1 取出 1 producer 放入 2 consumer-1 取出 2
producer 放入 3 consumer-1 取出 3 producer 放入 4 consumer-0 取出 4 producer 放入 5 consumer-0 取出 5
5.3 面试追问¶
Q1:协程和线程的区别?
协程是用户态调度、单线程内协作式切换,没有内核态切换与锁竞争开销;线程是内核态抢占式调度。协程适合大量 IO 等待,不适合 CPU 密集。
Q2:asyncio.run() 做了哪些事?
创建并运行事件循环、执行主协程、最后关闭循环与默认执行器;Python 3.7+ 统一入口,替代手动的
loop.run_until_complete()。
Q3:真正的网络 IO 用什么库?
aiohttp(HTTP)、httpx.AsyncClient;asyncio.sleep只用于面试演示"挂起点让出"的机制。
💬 答法提示:问「协程能取代线程吗」→ 答「不能,CPU 密集仍需线程/进程;协程解决的是高并发 IO」;问「asyncio 有锁吗」→ 答「有
asyncio.Lock/Semaphore,用法与 threading 一致,只是要 await」。
易错点:忘了 await(协程不执行返回 coroutine 对象);在同步函数里 asyncio.run 会报"在运行中的事件循环";消费者退出条件缺失导致 q.join() 永不返回。
6. 轮子题(缓存/栈经典实现)¶
6.1 手写 LRU Cache(OrderedDict)¶
考点:LRU(最近最少使用):容量满时淘汰最久未访问的键。用 OrderedDict:get/move_to_end 实现"访问即置顶";popitem(last=False) 弹出"最久未使用"。
配图来源:手绘 SVG(images/hand_lru.svg)
# 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)
1 -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 要"频率相同再按时间"淘汰 → 防止一个冷键刷两次频率霸占缓存
-1
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) 元组,本质一样
1 2
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(类数);双检锁保证线程安全
单例 OK
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 追问「还有什么淘汰策略」→ 答 LRU-K、FIFO、TinyLFU(Redis 近似 LFU);问「为什么 get 也要刷新顺序」→ 因为访问也代表「最近使用」。按「为什么这么设计」答,比背定义得分高。
易错点: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)
1 2 3
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)
3 2 1
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)
[0, 0, 1, 2, 3, 0, 1] 3
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:回文半径数组 + 最右臂界镜像对称优化
babad -> bab cbbd -> bb abba -> abba a -> a
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 还能优化吗」→ 答 nextval(失配时连续跳转);问「暴力复杂度怎么算」→ O(mn),最坏每次失配都退回开头重比。回文追问「Manacher 为什么 O(n)」→ 复用已算过的回文半径、镜像对称跳过重复扩展。
易错点: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}
20 45
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 主题工厂同时生成按钮+输入框)。复杂度递增,按需选型。
💬 答法提示:问「什么场景别用工厂」→ 答「创建没有变化点、Python 直接传类/函数更符合惯例时,工厂反而多一层抽象」。策略 + 工厂连答:工厂负责「造出策略对象」,策略负责「算法不同」,注册表字典是 Python 特色加分写法。
易错点:观察者 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 "成功"
random.seed(1) # 固定种子:演示确定性通过(第 2 次成功)
print(flaky_call())
# 时间:最多 O(3) 次 × 退避等待;经典退避序列 0.1 → 0.2 → 0.4
# 追问:何时不该无脑重试 → 4xx 业务错误(幂等性/参数错误)不重试,5xx/超时才重试
第 1 次失败(网络抖动),0.12s 后重试
成功
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 是生成器版捷径
[查询数据库] 耗时 0.2002s [批量写入] 耗时 0.1008s 捕获异常: 写入失败
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(参数个数)
注册成功: Alice, 25 岁 校验拦截: 参数 age 期望 int,得到 str
9.4 面试追问¶
Q1:指数退避为什么还要加抖动(jitter)?
所有客户端同时失败会同时重试,等待序列一致形成重试风暴(惊群);加随机抖动让重试时刻分散,这是 AWS/Google 通用实践。
Q2:@contextmanager 的 yield 前后代码分别在什么时候执行?
yield 前在
with进入时执行(相当于__enter__);yield 后在with块结束(含异常)时执行(相当于__exit__);用 try/finally 包住 yield 可以保证异常时清理资源。
Q3:校验装饰器放业务里还是框架层?
校验是横切关注点,应收敛在装饰器/中间件统一实现(DRY);但类型校验 Python 更常用
pydantic、dataclass等声明式方案,装饰器适合轻量场景。
💬 答法提示:问「重试对幂等的要求」→ 答「重试只对幂等操作安全:GET/PUT 可重试,扣款 POST 需要幂等键」;问「退避上限」→ 答「设 max_delay 封顶 + 抖动,如 1s→2s→4s→8s→封顶 10s」。
易错点: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直接运行;每个文件的运行结果已写在注释行中。
10. 高频手撕排序(🔴 必背三件套 + 对比表)¶
💡 **心法(一句话):**排序三件套的本质都是「分而治之」:快排「选基准,小的去左、大的去右」;归并「先切碎再按序拼回」;堆排「先堆出最大值,再逐个摘走」。
🏷️ **类比:**快排像分拣扑克牌(抽一张当界,小的放左、大的放右);归并像把两摞已排好的牌一张张比大小合成一摞;堆排像把牌搭成「顶最大」的三角形,每次取走塔尖再重新扶正。
| 算法 | 平均 | 最坏 | 空间 | 稳定 | 特点 |
|---|---|---|---|---|---|
| 快排 | O(n log n) | O(n²) | O(log n) | 否 | 原地、常数小、实际最快 |
| 归并 | O(n log n) | O(n log n) | O(n) | 是 | 稳定、外排、逆序对 |
| 堆排 | O(n log n) | O(n log n) | O(1) | 否 | 原地、不稳定、TopK |
默写顺序建议:快排(挖坑法/双指针法)→ 归并(含逆序对)→ 堆排(sift_down 背熟)。
10.1 快速排序(原地双指针版)¶
💡 **心法(一句话):**选一个「基准 pivot」,把比它小的都换到左边、大的换到右边(分区),然后左右两边各自重复——分而治之,平均 O(n log n)。
🏷️ **类比:**整理一摞卷子:抽一张当「分数线」(pivot),低于它的放左边、高于它的放右边;左右两摞再用同样方法各抽一张继续分,直到每摞只剩一张。
🔍 逐步走查:
nums = [6, 1, 3, 5, 2],pivot = nums[2] = 3,左右指针i=0, j=4:| 步骤 | 动作 | 数组状态 | |---|---|---| | 0 | 初始 | [6, 1, 3, 5, 2],pivot=3 | | 1 | i 停在 6(不小于 3),j 停在 2(不大于 3),交换 | [2, 1, 3, 5, 6],i=1, j=3 | | 2 | i 走:1<3 → i=2,3 不小于 3 停;j 走:5>3 → j=2,3 不大于 3 停 | i=2, j=2 | | 3 | i<=j 成立 → swap(3,3) 无变化 → i=3, j=1,外层 while 退出 | [2, 1, 3, 5, 6] | | 4 | 递归左半 [2,1]:基准 2 → 交换得 [1,2];递归右半 [5,6] 同样排好 | [1, 2, 3, 5, 6] ✅ |
边界口诀:外层
while i <= j保证交换后两指针不相交;递归出口是lo >= hi(空或单元素直接返回)。最坏 O(n²) 出现在每次基准把数组切成 1 和 n-1(如已有序),随机基准/三数取中可缓解。
# quick_sort.py —— 原地快排(Hoare 双指针法, 面试默写版)
def quick_sort(nums, lo, hi):
if lo >= hi:
return
pivot = nums[(lo + hi) // 2]
i, j = lo, hi
while i <= j:
while nums[i] < pivot:
i += 1
while nums[j] > pivot:
j -= 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
quick_sort(nums, lo, j)
quick_sort(nums, i, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print('快排结果:', arr)
print('注意: 最坏 O(n²) 出现在已有序输入(基准总取中间可缓解); 可用随机基准/三数取中')
快排结果: [1, 1, 2, 3, 6, 8, 10] 注意: 最坏 O(n²) 出现在已有序输入(基准总取中间可缓解); 可用随机基准/三数取中
10.2 归并排序 + 逆序对计数¶
💡 **心法(一句话):**先把数组「一分为二、二分为四」切到单个元素,再两两「按大小合并」成一整个有序数组——稳定排序,O(n) 额外空间。
🏷️ **类比:**整理两摞已排好的扑克牌:反复比较两摞牌顶,谁小先抽谁放下面,最后合出一摞有序牌。
🔍 逐步走查(顺便数逆序对):
[3, 1, 2]:| 阶段 | 内容 | |---|---| | 切分 | [3,1,2] → [3] 与 [1,2];[1,2] → [1] 与 [2](递归到底,单元素天然有序) | | 合并 1 | [1] 与 [2]:1≤2 → merged=[1,2] | | 合并 2 | [3] 与 [1,2]:3>1 → 取 1,逆序对 +1(左边还剩 1 个元素)→ [1];3>2 → 取 2,再 +1 → [1,2];最后取 3 → [1,2,3] |
逆序对共 2 个。代码里
c3 += len(left) - i就是「右边被取走的小元素,与左边剩余每个都构成逆序对」。切分时左右各自递归、合并时同时累计。
# merge_sort.py —— 归并排序 + 逆序对计数(LeetCode 剑指 Offer 51)
def merge_sort(a):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, c1 = merge_sort(a[:mid])
right, c2 = merge_sort(a[mid:])
merged, c3, i, j = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
c3 += len(left) - i # 左边剩余元素都大于 right[j] → 都是逆序对
merged += left[i:] + right[j:]
return merged, c1 + c2 + c3
arr = [5, 2, 4, 6, 1, 3]
sorted_arr, inv = merge_sort(arr)
print('归并结果:', sorted_arr, ' 逆序对数:', inv)
print('追问: 逆序对=相邻交换次数; 冒泡排序的交换次数就是逆序对')
归并结果: [1, 2, 3, 4, 5, 6] 逆序对数: 9 追问: 逆序对=相邻交换次数; 冒泡排序的交换次数就是逆序对
10.3 堆排序(大顶堆 + 原地下沉)¶
💡 **心法(一句话):**把数组看成一棵「完全二叉树」并调整成「父 ≥ 子」的大顶堆,再反复「把堆顶最大值换到末尾 + 缩小堆范围 + 下沉修复」,O(n log n) 且原地。
🏷️ **类比:**健身举哑铃:每次把「最重的哑铃」(堆顶)单独拎出来放好,剩下的重新码成最重在上的堆,再拎下一个最重的。
🔍 逐步走查:
[4, 10, 3, 5, 1],节点下标规律:节点 i 的左右孩子是2i+1、2i+2。建堆(自底向上,
i从n//2-1 = 1到 0):① i=1:10 已比两个孩子 5、1 大 → 不动;② i=0:4 与孩子 10、3 比 → 换 10;继续下沉:4 与 5、1 比 → 换 5。堆变成 [10, 5, 3, 4, 1],堆顶最大 ✅。排序(堆顶与末尾交换,再对缩小的堆下沉):
| 步 | 交换后 | 下沉修复后 | |---|---|---| | 1 | [1,5,3,4,10] | [5,4,3,1,10] | | 2 | [1,4,3,5,10] | [4,1,3,5,10] | | 3 | [3,1,4,5,10] | [3,1,4,5,10] | | 4 | [1,3,4,5,10] | 完成 ✅ |
下沉出口:
largest == i(该节点已不比两个孩子小)就 break,否则换下去。
# heap_sort.py —— 堆排序(大顶堆, O(1) 空间)
def sift_down(a, n, i):
while True:
largest = i
l, r = 2 * i + 1, 2 * i + 2
if l < n and a[l] > a[largest]:
largest = l
if r < n and a[r] > a[largest]:
largest = r
if largest == i:
break
a[i], a[largest] = a[largest], a[i]
i = largest
def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # 自底向上建堆
sift_down(a, n, i)
for i in range(n - 1, 0, -1): # 堆顶与末尾交换, 缩小堆
a[0], a[i] = a[i], a[0]
sift_down(a, i, 0)
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print('堆排序:', arr)
print('场景: 前 K 大用最小堆 O(n log K); 堆排序本身面试频率低于快排/归并')
堆排序: [1, 3, 4, 5, 10] 场景: 前 K 大用最小堆 O(n log K); 堆排序本身面试频率低于快排/归并
10.4 二分查找三件套(标准 / 左边界 / 右边界)¶
💡 **心法(一句话):**有序数组里「每次猜中间,大了去左边、小了去右边」,每轮砍掉一半 → O(log n);三种写法只差「边界怎么收」。
🏷️ **类比:**猜数字游戏:裁判说「1~100 里猜一个数」,你每次都猜正中间,「大了」把上限压到中间,「小了」把下限抬到中间,10 次内必中。
🔍 逐步走查:
a = [1,2,3,3,3,5,7],目标 3:| 写法 | 区间 | 循环条件 | mid 取法 | 走查 | |---|---|---|---|---| | 标准
bs| [lo, hi] 闭区间 |while lo <= hi|(lo+hi)//2| mid=3 → a[3]==3 → 直接返回下标 3 | | 左边界bs_left| [lo, hi) 半开 |while lo < hi|(lo+hi)//2(偏左) | a[3]≥3 → hi=3;a[1]=2<3 → lo=2;a[2]≥3 → hi=2;返回 2 | | 右边界bs_right| [lo, hi) 半开 |while lo < hi|(lo+hi+1)//2(偏右,防死循环) | a[4]≤3 → lo=4;a[6]=7>3 → hi=5;a[5]=5>3 → hi=4;返回 4 |关键区别:找左边界满足条件就
hi = mid(往左收);找右边界满足条件就lo = mid(往右推),此时 mid 必须取上整,否则lo永远不动 → 死循环。这就是「为什么有人写l<r有人写l<=r」的答案:闭区间精确查找用<=,半开区间找边界用<。
# binary_search.py —— 标准二分 + 左边界 + 右边界(三件套一次背全)
def bs(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
return mid
if a[mid] < t:
lo = mid + 1
else:
hi = mid - 1
return -1
def bs_left(a, t): # 第一个 >= t (lower_bound)
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] >= t:
hi = mid
else:
lo = mid + 1
return lo
def bs_right(a, t): # 最后一个 <= t (upper_bound - 1)
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi + 1) // 2
if a[mid] <= t:
lo = mid
else:
hi = mid - 1
return lo
a = [1, 2, 3, 3, 3, 5, 7]
print('标准二分 找3:', bs(a, 3), ' 左边界:', bs_left(a, 3), ' 右边界:', bs_right(a, 3))
print('要点: 左/右边界用 [lo, hi) 半开区间 + 各自防死循环的 mid 取法')
标准二分 找3: 3 左边界: 2 右边界: 4 要点: 左/右边界用 [lo, hi) 半开区间 + 各自防死循环的 mid 取法
10.5 链表三连:反转 / 判环 / 找环入口¶
💡 **心法(一句话):**链表题核心就两个模型:反转用「三指针 prev-cur-nxt 挨个掉头」;判环用「快慢指针,快的走两步、慢的走一步,有环必相遇」。
🏷️ **类比:**反转 = 一串手拉手的人原地转身(每个人改指身后的人);判环 = 环形跑道上快的人多跑一圈,一定会在某处追上慢的人。
🔍 **逐步走查:**反转
1→2→3→4(prev=None,head=1):| 步 | 动作(先存 nxt,再掉头指 prev,再整体前进) | 状态 | |---|---|---| | 1 | nxt=2;1.next=None;prev=1;head=2 | 1→None;待处理 2→3→4 | | 2 | nxt=3;2.next=1;prev=2;head=3 | 2→1;待处理 3→4 | | 3 | nxt=4;3.next=2;prev=3;head=4 | 3→2→1 | | 4 | 4.next=3;prev=4;head=None | 4→3→2→1 ✅ |
判环走查(1→2→3→1):slow=1, fast=1 → slow=2, fast=3 → slow=3, fast=2 → slow=1, fast=1 相遇 → 有环。找入口:相遇后
ptr = head,ptr 与 slow 同速走,再次相遇处就是环入口(数学结论:头到入口距离 = 相遇点到入口距离,背住即可)。
# linked_list.py —— 反转链表 + 环形检测(快慢指针)+ 找环入口
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev, head = head, nxt
return prev
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
def detect_cycle(head): # 相遇后: 快指针回头部, 同速走, 再次相遇即入口
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
ptr = head
while ptr is not slow:
ptr, slow = ptr.next, slow.next
return ptr
return None
a = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
r = reverse(a)
vals = []
while r:
vals.append(r.val)
r = r.next
print('反转:', vals)
n1, n2, n3 = ListNode(1), ListNode(2), ListNode(3)
n1.next, n2.next, n3.next = n2, n3, n1
print('有环:', has_cycle(n1), ' 环入口节点值:', detect_cycle(n1).val)
反转: [4, 3, 2, 1] 有环: True 环入口节点值: 1
10.6 二叉树模板:层序 BFS + 最大深度¶
💡 **心法(一句话):**层序 = 用队列「一层一层吐」:弹出队首节点、把它左/右孩子塞进队尾;深度 = 递归「子树深度 + 1」,空树深度是 0。
🏷️ **类比:**层序像叫号排队:叫一个号(弹出队首),把它的「左邻居、右邻居」(孩子)排到队尾,一批一批处理;深度像量楼层:从地面(空)往上每层 +1。
🔍 **逐步走查:**树 = 1(左 2(左 4),右 3(右 5)):① 队=[1] → 弹 1,入 2、3 → level=[1];② 弹 2(入 4)、弹 3(入 5)→ level=[2,3];③ 弹 4、5(无孩子)→ level=[4,5]。输出 [[1],[2,3],[4,5]]。深度 = 1 + max(2 的深度, 3 的深度) = 1 + max(2, 2) = 3 ✅。
# binary_tree.py —— 层序遍历 + 最大深度 + 前序(回溯式)
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
print('层序:', level_order(root), ' 最大深度:', max_depth(root))
print('变体: 前/中/后序递归 10 秒默写; 迭代用栈模拟')
层序: [[1], [2, 3], [4, 5]] 最大深度: 3 变体: 前/中/后序递归 10 秒默写; 迭代用栈模拟
10.7 前缀树 Trie(字典树)¶
💡 **心法(一句话):**把单词按字母「逐层挂到树上」,公共前缀共用相同的树路径,查询某个词 / 某个前缀就是沿路径走一遍,O(单词长度)。
🏷️ **类比:**手机通讯录按拼音分组:「apple」和「apply」前四个字母共用一个分组;想找「app 开头的联系人」,走进 app 这个节点数一数下面挂了多少人就够了。
🔍 逐步走查:插入 apple、app、apply、apricot 后,a→p→p 这条路径上:
cnt(以该节点结尾的单词数)= 1(只有 app 自己),prefix(经过该节点的单词数)= 3(apple / app / apply)。所以search("app") = 1,而starts_with("app") = 3。二者区别就是「精确匹配」还是「前缀匹配」。
# trie.py —— 前缀树(插入 / 精确搜索 / 前缀统计)
class Trie:
def __init__(self):
self.child = {}
self.cnt = 0 # 以该节点结尾的单词数
self.prefix = 0 # 经过该节点的单词数
def insert(self, w):
node = self
for ch in w:
node = node.child.setdefault(ch, Trie())
node.prefix += 1
node.cnt += 1
def search(self, w):
node = self
for ch in w:
if ch not in node.child:
return 0
node = node.child[ch]
return node.cnt
def starts_with(self, p):
node = self
for ch in p:
if ch not in node.child:
return 0
node = node.child[ch]
return node.prefix
t = Trie()
for w in ['apple', 'app', 'apply', 'apricot']:
t.insert(w)
print('搜索 app:', t.search('app'), ' 前缀 app 的单词数:', t.starts_with('app'))
搜索 app: 1 前缀 app 的单词数: 3
10.8 并查集(判连通 / 判环)¶
💡 **心法(一句话):**并查集只干两件事:「查」(find:我的老大是谁)和「并」(union:两个小弟认一个老大);加一条边时两端已同老大 → 成环。
🏷️ **类比:**帮派认亲:每个人先记住「我的上级是谁」(par 数组);
find一路问到帮主,顺路让中间人都直接认帮主(路径压缩);两家帮派歃血为盟(union),小帮派并入大帮派(按秩合并)。🔍 逐步走查:
union(0,1):0、1 各自是老大 → par[1]=0 → True;union(1,2):find(1)=0,find(2)=2 → par[2]=0 → True;union(2,0):find(2)=0,find(0)=0 → 同一个老大 → 返回 False = 检测到环 ✅。Kruskal 求最小生成树正是靠它跳过成环的边。
# union_find.py —— 并查集(路径压缩 + 按秩合并), 判连通/成环
class UnionFind:
def __init__(self, n):
self.par = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.par[x] != x: # 路径压缩(迭代折叠)
self.par[x] = self.par[self.par[x]]
x = self.par[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # 已连通 → 再加这条边就成环
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.par[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
uf = UnionFind(4)
print('加边 (0,1):', uf.union(0, 1), ' (1,2):', uf.union(1, 2), ' (2,0):', uf.union(2, 0))
print('→ 第三条边两个端点已连通: 返回 False, 即检测到环(图的判环/最小生成树 Kruskal 都用它)')
加边 (0,1): True (1,2): True (2,0): False → 第三条边两个端点已连通: 返回 False, 即检测到环(图的判环/最小生成树 Kruskal 都用它)
10.9 拓扑排序(Kahn 入度法)¶
💡 心法(一句话):「先修课排序」:反复找出**当前没有前置课(入度为 0)**的课上掉,再把它指向的后继课入度 -1;最终能上的课不够 n 门就说明有环。
🏷️ **类比:**考驾照流程:科一没有前置 → 先考;考完科一解锁科二科三(入度减 1);哪门课的前置都清零了,哪门就能去考。若所有前置清零后还有课排不上 → 前置关系里有环(永远毕不了业)。
🔍 **逐步走查:**先修 (0,1)、(2,0)、(3,1)、(3,2)(上 a 需先修 b)。入度 indeg = [1, 0, 1, 2]:① 入度为 0 的只有 1 → 上 1,令 indeg[0]-1=0、indeg[3]-1=1;② 上 0(入度 0)→ indeg[2]-1=0;③ 上 2 → indeg[3]-1=0;④ 上 3。顺序 [1,0,2,3] ✅,恰好 4 门 = n → 无环。若 order 长度 < n → 返回 None(有环)。
# topo_sort.py —— 拓扑排序(Kahn BFS 入度法): 课程表问题
from collections import deque
def can_finish(prereqs, n):
"""prereqs: [(课程a, 先修b)] 表示 toma b 后才能上 a"""
g = [[] for _ in range(n)]
indeg = [0] * n
for a, b in prereqs:
g[b].append(a)
indeg[a] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
order = []
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else None # None = 有环, 无法排课
print('合法排课:', can_finish([(0, 1), (2, 0), (3, 1), (3, 2)], 4))
print('有环(1→0→1):', can_finish([(0, 1), (1, 0)], 2))
合法排课: [1, 0, 2, 3] 有环(1→0→1): None
10.10 Dijkstra 最短路(堆优化)¶
💡 **心法(一句话):**从起点出发,每次挑「当前距离最短」的点确定下来(贪心),用它的边去「松弛」邻居;小顶堆保证每次 O(log n) 拿到最近点。
🏷️ **类比:**外卖送餐:先送最近的一单(确定),送完顺手问那家店「顺路还能捎哪些订单」——每单都找当前最近未送的点,绝不回头改已确定的距离。
🔍 **逐步走查(从 0 出发):**dist=[0,∞,∞,∞,∞],堆 [(0,0)]:① 弹 0 → 松 1(0+4=4)、松 2(0+2=2);② 弹 2(距离 2)→ 松 1(2+1=3<4 → 更新 3)、松 3(10)、松 4(12);③ 弹 1(3)→ 松 3(3+5=8<10 → 更新 8);④ 弹 3(8)→ 松 4(8+2=10<12 → 更新 10);⑤ 弹 4(10)。最终 dist=[0,3,2,8,10] ✅。
if d > dist[u]: continue的作用是跳过堆里已过期的旧记录。
# dijkstra.py —— 单源最短路(堆优化, 稠密图可用朴素版)
import heapq
def dijkstra(n, edges, src):
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 已更新的旧记录, 跳过
for v, w in g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
print('从 0 出发最短路:', dijkstra(5, edges, 0))
print('注意: 不能处理负权边; 负权用 Bellman-Ford / SPFA')
从 0 出发最短路: [0, 3, 2, 8, 10] 注意: 不能处理负权边; 负权用 Bellman-Ford / SPFA
10.11 动态规划模板(爬楼梯 / 编辑距离)¶
💡 **心法(一句话):**把大问题拆成「最后一步怎么来」:爬第 n 阶 = 从第 n-1 阶跨 1 步 + 从第 n-2 阶跨 2 步;配好边界后,状态只跟前两个有关就用两个变量滚动。
🏷️ **类比:**爬楼梯:想到达第 10 级,要么从第 9 级跨 1 步,要么从第 8 级跨 2 步——所以 f(10)=f(9)+f(8),一路从 f(0)=1、f(1)=1 推上来。
🔍 **逐步走查(滚动数组):**a=1(f(0))、b=1(f(1)),轮次 2~10 执行
a, b = b, a+b:| 轮 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---|---|---|---|---|---|---|---|---|---|---| | (a,b) | (1,2) | (2,3) | (3,5) | (5,8) | (8,13) | (13,21) | (21,34) | (34,55) | (55,89) |
返回 b=89 ✅。编辑距离则是二维表:
dp[i][j]表示 s 前 i 个字符变到 t 前 j 个字符的代价,字符相等直接继承左上角,不相等取「增 / 删 / 改」三者最小值 +1。
# dp_demo.py —— 爬楼梯(滚动数组) + 编辑距离(经典二维 DP)
def climb(n):
a, b = 1, 1 # f(0)=1, f(1)=1
for _ in range(2, n + 1):
a, b = b, a + b
return b
def edit_distance(s, t):
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
print('爬 10 阶:', climb(10))
print('编辑距离 horse→ros:', edit_distance('horse', 'ros'))
print('DP 要点: 明确状态定义 → 转移方程 → 边界; 能优化成滚动数组就滚')
爬 10 阶: 89 编辑距离 horse→ros: 3 DP 要点: 明确状态定义 → 转移方程 → 边界; 能优化成滚动数组就滚
10.12 回溯模板(全排列 / 子集 / 去重剪枝)¶
💡 **心法(一句话):**回溯 = 深度优先搜索 + 后悔药:「做选择 → 递归 → 撤销选择」,穷举所有路径;要避免重复结果就先排序,相邻同值直接跳过(剪枝)。
🏷️ **类比:**走迷宫到死胡同就原路退回上一个岔路口换条路走——「试当前格子 → 走下一步 → 走不通退回来擦掉脚印」,脚印就是
path,用used标记哪格已踩过。🔍 逐步走查:
permute([1,2,3])的递归树:① 选 1 → 剩余 [2,3]:得 1-2-3,撤销到 1-2,改选 3 → 得 1-3-2;② 退回空路径,改选 2 → 得 2-1-3、2-3-1;③ 改选 3 → 得 3-1-2、3-2-1。共 3! = 6 个 ✅。去重:比如 [1,1,2] 先排序,进入递归时若nums[i] == nums[i-1]且前一个同值本轮没被用过,就continue剪掉重复分支(也就是代码注释的「排序后 visited[i] 与 visited[i-1] 同值则剪枝」)。
# backtrack.py —— 全排列 / 子集(回溯模板: 选择→递归→撤销)
def permute(nums):
out, path, used = [], [], [False] * len(nums)
def bt():
if len(path) == len(nums):
out.append(path[:])
return
for i, x in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(x)
bt()
path.pop()
used[i] = False
bt()
return out
def subsets(nums):
out, path = [], []
def bt(i):
out.append(path[:])
for j in range(i, len(nums)):
path.append(nums[j])
bt(j + 1)
path.pop()
bt(0)
return out
print('全排列 [1,2,3]:', permute([1, 2, 3]))
print('子集个数(应=2^n):', len(subsets([1, 2, 3])))
print('去重模板: 排序后 visited[i] 与 visited[i-1] 同值则剪枝')
全排列 [1,2,3]: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 子集个数(应=2^n): 8 去重模板: 排序后 visited[i] 与 visited[i-1] 同值则剪枝
10.13 滑动窗口 + 双指针(最长无重复子串 / 三数之和)¶
💡 **心法(一句话):**窗口题 = 右指针扩张 + 左指针收缩:右指针把新字符拉进来,一旦窗口不合法(出现重复)就收缩左边界,全程只扫一遍 → O(n)。
🏷️ **类比:**火车上占座:右手一节节车厢往后退(右指针扩张窗口),左边有人重复占座就把最左边的人请下车(收缩左边界),随时记录队伍最长的一次有多长。
🔍 逐步走查:
"abcabcbb":right 依次扫到 a、b、c → 窗口「abc」,best=3;right=3 的 'a' 已出现过(下标 0 ≥ left=0)→ left 跳到 1,窗口「bca」;right=4 的 'b'(下标 1 ≥ left=1)→ left=2,「cab」;right=5 的 'c' → left=3,「abc」;right=6、7 的 'b' 连续触发 → left 一路右移。任何时刻窗口内都无重复字符,best 始终是 3 ✅。核心判断就是seen[ch] >= left:重复字符是否还在当前窗口内。
# sliding_window.py —— 滑动窗口(最长无重复子串) + 双指针(三数之和)
def length_of_longest(s):
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # 左边界跳到重复字符之后
seen[ch] = right
best = max(best, right - left + 1)
return best
def three_sum(nums, target=0):
nums.sort()
out = []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]:
continue # 去重
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
out.append((nums[i], nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return out
print('最长无重复子串 abcabcbb:', length_of_longest('abcabcbb'))
print('三数之和:', three_sum([-1, 0, 1, 2, -1, -4]))
print('滑窗模板: 右指针扩张 + 不满足条件收缩左指针; 双指针排序后双向夹逼')
最长无重复子串 abcabcbb: 3 三数之和: [(-1, -1, 2), (-1, 0, 1)] 滑窗模板: 右指针扩张 + 不满足条件收缩左指针; 双指针排序后双向夹逼
10.14 位运算模板(异或 / 汉明距离)¶
💡 **心法(一句话):**三个法宝:
a ^ a = 0(成对的数互相抵消)、x & (x-1)(把最低位的 1 抹掉)、x & (-x)(只留最低位的 1)。🏷️ **类比:**两人一组互相抵消:全班按「同号相消」配对的两人一起离场,最后留下的那个人就是「只出现一次」的异类(异或)。
🔍 逐步走查:
single_number([4,1,2,1,2]):4^1^2^1^2 = 4 ^ (1^1) ^ (2^2) = 4^0^0 = 4 ✅(1、2 各自成对抵消)。hamming(1,4):1^4 = 5(二进制 101);5 & 4 = 4(去掉最低位 1,计数 1),4 & 3 = 0(再去掉一个 1,计数 2)→ 汉明距离 2 ✅。
# bit_ops.py —— 位运算三连: 只出现一次 / 汉明距离 / 技巧清单
def single_number(nums):
x = 0
for n in nums:
x ^= n # a^a=0, 0^a=a → 出现两次的抵消
return x
def hamming(a, b):
x = a ^ b
cnt = 0
while x:
x &= x - 1 # 每次清除最低位 1
cnt += 1
return cnt
print('只出现一次的数字:', single_number([4, 1, 2, 1, 2]))
print('汉明距离(1,4):', hamming(1, 4))
print('技巧: n & (n-1) 清除最低位1; n & (-n) 取最低位1; 判断2的幂: n>0 and n&(n-1)==0')
只出现一次的数字:
4 汉明距离(1,4): 2 技巧: n & (n-1) 清除最低位1; n & (-n) 取最低位1; 判断2的幂: n>0 and n&(n-1)==0
11. 手撕题目答题模板 + 复杂度口诀(🔴 开场白)¶
💡 **心法(一句话):**面试手撕不是「从零想算法」,而是「开场白报套路 + 复述模板 + 把复杂度与数据规模对号入座」——本节就是你的开场白脚本。
🏷️ **类比:**和面试官同看一张「题目-套路对照表」:链表 → 快慢指针/哑节点,树 → BFS/递归,图 → 并查集/Dijkstra;看到题先对号入座再动手。
链表题¶
先问能否修改原链表? → 快慢指针/哑节点(dummy)/递归反转
环/交点 → 快慢指针; 反转 → 三指针prev-cur-nxt; 删除 → 哑节点
树题¶
递归语义: 子树答案 → 自底向上; 层序 → BFS deque
BST → 中序有序; 路径和 → 自顶向下带累计值
图题¶
连通/环 → 并查集/DFS 染色; 最短路 → Dijkstra(非负)/Bellman-Ford(负权)
拓扑 → Kahn 入度法; 双向 BFS 优化搜索
DP 题¶
状态: 一维(位置/剩余量) 二维(两串/两维) 背包(容量维度)
转移: 最后一步怎么来 → 枚举前一个状态; 边界: dp[0]/dp[i][0]
复杂度口诀(背)
| 数据规模 | 可接受复杂度 |
|---|---|
| n ≤ 20 | O(2ⁿ) / 阶乘(回溯/状压) |
| n ≤ 10⁵ | O(n log n)(排序/二分/堆/Trie/并查集) |
| n ≤ 10⁶ | O(n)(滑窗/双指针/单调栈/哈希) |
| n ≤ 10⁹ | O(log n)(二分/快速幂) |
面试追问速答¶
- Q:快排最坏情况?→ 每次基准把数组分成 1 和 n-1(已有序输入),O(n²),随机化基准缓解
- Q:TopK 怎么答?→ 堆 O(n log K) / 快排 partition 变形 O(n) 平均(BFPRT 最坏 O(n))
- Q:怎么判断链表有环并找入口?→ 快慢指针相遇 → 快指针回 head 同速走,再次相遇即入口
- Q:字符串匹配除了 KMP?→ 能说重点:next 数组=最长相等前后缀;还有 BM/Sunday(工程实用)
💬 答法提示:追问「TopK 的堆怎么做」→ 维护大小为 K 的最小堆,比堆顶大就替换,O(n log K);「死锁检测」→ 答「资源分配图找环 / 银行家算法」一句带过;「哲学家就餐」→ 答「限制同时拿叉子的人数 / 按编号顺序取叉子」。这几句背熟,冷门题也能撑住场面。