143 lines
5.1 KiB
Python
143 lines
5.1 KiB
Python
"""面试高频算法模式（只用标准库）。每个函数注明时间 / 空间复杂度；`python patterns.py` 运行自检，test_patterns.py 是测试。"""
|
||
from __future__ import annotations
|
||
|
||
import heapq
|
||
from collections import Counter, OrderedDict, deque
|
||
from typing import Hashable, Iterable
|
||
|
||
|
||
# 1. 哈希表：两数之和 O(n) / O(n)
|
||
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
|
||
seen: dict[int, int] = {}
|
||
for i, x in enumerate(nums):
|
||
if target - x in seen:
|
||
return seen[target - x], i
|
||
seen[x] = i
|
||
return None
|
||
|
||
|
||
# 2. 滑动窗口：无重复字符的最长子串 O(n) / O(字符集)
|
||
def longest_unique_substring(s: str) -> int:
|
||
last: dict[str, int] = {}
|
||
left = best = 0
|
||
for right, ch in enumerate(s):
|
||
if last.get(ch, -1) >= left:
|
||
left = last[ch] + 1 # 窗口左边界跳到重复字符的下一位
|
||
last[ch] = right
|
||
best = max(best, right - left + 1)
|
||
return best
|
||
|
||
|
||
# 3. 二分查找：第一个 >= target 的位置（lower_bound） O(log n) / O(1)
|
||
def lower_bound(arr: list[int], target: int) -> int:
|
||
lo, hi = 0, len(arr) # 左闭右开区间 [lo, hi)
|
||
while lo < hi:
|
||
mid = (lo + hi) // 2
|
||
if arr[mid] < target:
|
||
lo = mid + 1
|
||
else:
|
||
hi = mid
|
||
return lo
|
||
|
||
|
||
# 4. 堆：出现次数最多的 K 个（例如热门问题） O(n log k) / O(n)
|
||
def top_k_frequent(items: Iterable[Hashable], k: int) -> list[Hashable]:
|
||
counts = Counter(items)
|
||
return [x for _, x in heapq.nlargest(k, ((c, x) for x, c in counts.items()))]
|
||
|
||
|
||
# 5. BFS：网格最短路径（0 可走，1 障碍） O(行×列) / O(行×列)
|
||
def shortest_path(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> int:
|
||
rows, cols = len(grid), len(grid[0])
|
||
q = deque([(start, 0)])
|
||
seen = {start}
|
||
while q:
|
||
(r, c), d = q.popleft()
|
||
if (r, c) == end:
|
||
return d
|
||
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
|
||
nr, nc = r + dr, c + dc
|
||
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
|
||
seen.add((nr, nc))
|
||
q.append(((nr, nc), d + 1))
|
||
return -1
|
||
|
||
|
||
# 6. DFS + 拓扑排序：任务依赖的执行顺序（有环返回 None） O(V+E)
|
||
def topo_order(deps: dict[str, list[str]]) -> list[str] | None:
|
||
"""deps[a] = [b, c] 表示 a 依赖 b 和 c（b、c 要先执行）。"""
|
||
state: dict[str, int] = {} # 0/缺省 未访问，1 访问中，2 已完成
|
||
order: list[str] = []
|
||
|
||
def visit(n: str) -> bool:
|
||
if state.get(n) == 1:
|
||
return False # 回到“访问中”的节点：有环
|
||
if state.get(n) == 2:
|
||
return True
|
||
state[n] = 1
|
||
for m in deps.get(n, []):
|
||
if not visit(m):
|
||
return False
|
||
state[n] = 2
|
||
order.append(n)
|
||
return True
|
||
|
||
nodes = set(deps) | {m for ms in deps.values() for m in ms}
|
||
for n in sorted(nodes):
|
||
if not visit(n):
|
||
return None
|
||
return order
|
||
|
||
|
||
# 7. 动态规划：编辑距离（文本相似度、纠错） O(mn) / O(n)
|
||
def edit_distance(a: str, b: str) -> int:
|
||
prev = list(range(len(b) + 1))
|
||
for i in range(1, len(a) + 1):
|
||
cur = [i] + [0] * len(b)
|
||
for j in range(1, len(b) + 1):
|
||
cur[j] = prev[j - 1] if a[i - 1] == b[j - 1] else 1 + min(prev[j - 1], prev[j], cur[j - 1])
|
||
prev = cur
|
||
return prev[-1]
|
||
|
||
|
||
# 8. 设计题：LRU 缓存 get/put 均为 O(1)
|
||
class LRUCache:
|
||
def __init__(self, capacity: int):
|
||
self.capacity = capacity
|
||
self.data: OrderedDict[Hashable, object] = OrderedDict()
|
||
|
||
def get(self, key: Hashable) -> object | None:
|
||
if key not in self.data:
|
||
return None
|
||
self.data.move_to_end(key) # 最近使用的移到末尾
|
||
return self.data[key]
|
||
|
||
def put(self, key: Hashable, value: object) -> None:
|
||
self.data[key] = value
|
||
self.data.move_to_end(key)
|
||
if len(self.data) > self.capacity:
|
||
self.data.popitem(last=False) # 淘汰最久未使用的（头部）
|
||
|
||
|
||
# 9. 区间合并：合并重叠的时间段（排班、会议室） O(n log n)
|
||
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
|
||
out: list[tuple[int, int]] = []
|
||
for s, e in sorted(intervals):
|
||
if out and s <= out[-1][1]:
|
||
out[-1] = (out[-1][0], max(out[-1][1], e))
|
||
else:
|
||
out.append((s, e))
|
||
return out
|
||
|
||
|
||
if __name__ == "__main__":
|
||
assert two_sum([2, 7, 11, 15], 9) == (0, 1)
|
||
assert longest_unique_substring("abcabcbb") == 3
|
||
assert lower_bound([1, 3, 3, 5], 3) == 1
|
||
assert top_k_frequent(["退货", "发票", "退货", "物流", "退货", "物流"], 2) == ["退货", "物流"]
|
||
assert shortest_path([[0, 0, 0], [1, 1, 0], [0, 0, 0]], (0, 0), (2, 0)) == 6
|
||
assert topo_order({"deploy": ["test"], "test": ["build"]}) == ["build", "test", "deploy"]
|
||
assert edit_distance("kitten", "sitting") == 3
|
||
assert merge_intervals([(1, 3), (2, 6), (8, 10)]) == [(1, 6), (8, 10)]
|
||
print("全部自检通过")
|