应用岗算法核心：窗口、二分、BFS、堆、DP 与 LRU
用六个可运行模板串起应用岗通用编码基础，逐项说明不变量、复杂度和边界，避免只记题号。
发布于 2026-09-07 · 更新于 2026-09-07
本文目录
图：算法练习先明确状态与依赖关系；图中展示的是计算依赖示意，不是下方各算法的流程图。 来源：Compute graph and automatic differentiation，作者 Aston Zhang、Zachary C. Lipton、Mu Li、Alexander J. Smola（D2L.ai），许可 CC BY-SA 4.0。
识别信号
连续区间且可增量维护约束，考虑滑动窗口；有序边界或答案满足单调判定，考虑二分；无权图最短步数，考虑 BFS；只保留最优 k 项，考虑堆；重叠子问题与最优子结构，考虑 DP；需要按最近访问淘汰，考虑哈希加有序结构。
这六类是建议先练熟的编码基础，不是某家公司的题频统计。面试仍要先澄清输入范围、排序条件、是否允许修改输入以及返回值要求。
核心思路
每种模式先说一句不变量。窗口内无重复字符；二分的答案在半开区间内；BFS 出队顺序按最短层数递增；小根堆保存当前最大的 k 项；DP 状态保存已经解决的子问题；LRU 的最左端是最久未访问键。
能写模板只是第一步，必须解释不变量如何由每次更新维持，以及终止时为什么得到答案。
实现模板
整段使用标准库，包含独立断言。LRU 用 OrderedDict 展示业务行为；若题目要求 O(1) 并且禁止这个容器，应手写哈希表加双向链表。
from collections import deque, OrderedDict
import heapq
def longest_unique(s):
left, best, last = 0, 0, {}
for right, ch in enumerate(s):
left = max(left, last.get(ch, -1) + 1)
last[ch] = right
best = max(best, right - left + 1)
return best
def lower_bound(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def shortest_steps(graph, start, goal):
queue = deque([(start, 0)])
seen = {start}
while queue:
node, dist = queue.popleft()
if node == goal:
return dist
for nxt in graph.get(node, []):
if nxt not in seen:
seen.add(nxt)
queue.append((nxt, dist + 1))
return None
def largest_k(values, k):
if k < 0:
raise ValueError("k must not be negative")
if k == 0:
return []
heap = []
for value in values:
if len(heap) < k:
heapq.heappush(heap, value)
elif value > heap[0]:
heapq.heapreplace(heap, value)
return sorted(heap, reverse=True)
def coin_change(coins, amount):
if amount < 0 or any(c <= 0 for c in coins):
raise ValueError("invalid coins or amount")
dp = [0] + [float("inf")] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total:
dp[total] = min(dp[total], dp[total - coin] + 1)
return -1 if dp[amount] == float("inf") else dp[amount]
class LRU:
def __init__(self, capacity):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
assert longest_unique("abba") == 2
assert longest_unique("") == 0
assert lower_bound([1, 2, 2, 4], 2) == 1
assert lower_bound([], 5) == 0
assert lower_bound([1, 2], 3) == 2
assert shortest_steps({0: [1], 1: [0, 2]}, 0, 2) == 2
assert shortest_steps({}, 0, 1) is None
assert shortest_steps({}, 0, 0) == 0
assert largest_k([3, 1, 3, 2], 2) == [3, 3]
assert largest_k([1], 0) == []
assert coin_change([1, 3, 4], 6) == 2
assert coin_change([2], 3) == -1
assert coin_change([], 0) == 0
cache = LRU(2)
cache.put("a", 1)
cache.put("b", 2)
assert cache.get("a") == 1
cache.put("c", 3)
assert cache.get("b") == -1
cache.put("a", 9)
assert cache.get("a") == 9复杂度
窗口每个位置只处理一次，O(n) 时间、O(字符种类) 空间。二分 O(log n) 时间、O(1) 空间。BFS 为 O(V+E) 时间、O(V) 空间，visited 在入队时设置，避免重复入队。
堆模板为 O(n log k + k log k) 时间、O(k) 空间；若 k 大于数据量则按实际规模计。零钱兑换为 O(amount × 币种数) 时间、O(amount) 空间，金额很大时未必可行。LRU 在哈希平均性能假设下，get／put 平均 O(1)，空间 O(capacity)。
边界条件
滑动窗口不能无条件用于含负数的“和至少为目标”问题，因为扩展与收缩的单调性可能消失。二分必须确认输入有序或判定单调；BFS 不处理一般带权最短路，带权需要其他方法。
零钱问题贪心不总正确：币种 [1,3,4]、金额 6，贪心取 4+1+1 用三枚，最优 3+3 用两枚。LRU 不是 TTL；最近访问不代表数据仍有效，更不代表权限仍有效。
常见变体
窗口扩展到最小覆盖子串时维护计数缺口；二分变成 upper_bound 时修改比较条件；BFS 扩展到拓扑排序要增加入度；堆扩展到合并有序流要保存来源位置；DP 扩展到 0/1 背包时循环方向影响能否重复取物品。
这些变化必须重新解释不变量。框架名字相同不代表原模板可以直接复制。
测试用例
代码覆盖空输入、重复元素、环、不可达、k=0、无法凑金额和缓存淘汰。练习顺序：先写思路与复杂度，20–30 分钟内独立实现，再解释一个反例。这个时间只是自测目标，不是招聘方统一标准。
针对应用岗位，再追问：缓存如何加 TTL 和线程安全；top-k 怎样处理分布式分片；BFS 状态如何限制爆炸；异步任务队列怎样取消。通用算法与工程设计因此能相互衔接。