模式识别速查表
将 15 个常见问题信号（有序数组、需要所有组合、在约束下最大化价值等）对应到能最快解决它们的算法模式。
模式识别速查表 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
60 秒模式识别游戏
在真实面试中，您在读完问题后大约有 60 秒 来识别适用的算法模式，然后面试官就会期待您开始编写代码。这里最重要的技能不是背诵实现，而是识别应该使用哪个工具。
模式识别来自将问题信号（问题描述中的词语和约束）映射到已知的算法族。确定模式后，实现就变成套用模板的练习。本课是一份系统化的速查表，涵盖 15 个最常见的问题信号及其对应模式。
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)信号 1-3：数组与字符串模式
数组和字符串中最常见的问题信号：
- 已排序数组 + 查找目标值 → 二分查找 O(log n)
- 查找和为目标值的数对/三元组 → 已排序时使用双指针 O(n)，未排序时使用哈希映射 O(n)
- 满足条件的最长/最短子数组/子串 → 滑动窗口 O(n)
- 连续子数组的最大/最小和 → Kadane 算法 O(n)
- 重复项检测 → 哈希集合 O(n) 或 sort O(n log n)
如果数组已经排序，请始终先考虑二分查找。未排序 + 目标和 + O(n) = 几乎总是使用哈希映射查找补数。
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')信号 4-6：树与图模式
树和图的问题信号及其模式：
- 逐层遍历 / 无权图中的最短路径 → 使用双端队列的 BFS，O(V+E)
- 探索所有路径 / 环检测 / DFS 顺序 → 递归或迭代式 DFS，O(V+E)
- BST + 中序性质（第 k 个元素、排序顺序） → 中序 DFS，O(n)
- 最低公共祖先 → 跟踪路径的递归下降，O(n)
- 连通分量 / 合并两个集合 → DSU，O(n × α(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')信号 7-9：动态规划信号
DP 信号最难识别。请留意以下关键词：
- “……的方法数” → 计数 DP（累加子问题的计数）
- “达到……的最小/最大成本” → 优化 DP（对各子问题取最小值/最大值）
- “我们能否达到……”（可行性） → 布尔 DP（对各子问题进行 OR）
- 由两个字符串索引定义的子问题 → 二维 DP（LCS、编辑距离）
- 在容量约束下选择或跳过项目 → 背包 DP
- 最优子结构 + 重叠子问题 → 检查递归树中是否有重复调用 → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')信号 10-12：堆、栈与贪心信号
堆、单调栈和贪心问题的信号：
- 前 K 个元素 / 第 k 大或第 k 小 → 堆（前 K 大使用小根堆，第 k 小使用大根堆），O(n log k)
- 流式中位数 → 两个堆（较小一半使用大根堆 + 较大一半使用小根堆）
- 下一个更大/更小元素 → 单调栈 O(n)
- 最大矩形面积 / 接雨水 → 单调栈 O(n)
- 区间调度 / 最大化互不重叠的区间 → 贪心（按结束 time 进行 sort）
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')信号 13-15：回溯与位运算
回溯和位运算的信号：
- 生成所有子集 / 排列 / 组合 → 回溯，O(2^n 或 n!)
- 约束满足问题（N 皇后、数独） → 带剪枝的回溯
- 找出一个缺失元素/唯一元素 → XOR，O(n)，空间 O(1)
- 枚举小集合的所有子集（n ≤ 20） → 位掩码枚举 2^n 种情况
- 统计置位位数 / 检查是否为 2 的幂 → 位运算技巧（n & (n-1)）
- 使用小集合进行状态压缩 DP → 位掩码 DP，O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')约束分析：N 告诉您的信息
输入规模约束 n 会直接告诉您可接受的 time 复杂度，进而告诉您应选择哪一类算法：
- n ≤ 20：O(2^n) 或 O(n!) 可接受——位掩码 DP、回溯
- n ≤ 500：O(n³) 可接受——Floyd-Warshall、暴力 DP
- n ≤ 5000：O(n²) 可接受——朴素 DP、二次复杂度 sort
- n ≤ 10^6：需要 O(n log n)——归并 sort、堆、二分查找
- n ≤ 10^8：需要 O(n)——双指针、滑动窗口、线性 DP
读完问题后，您首先应该进行约束分析，然后再决定使用哪种算法。
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')问题 → 模式：快速练习
请练习这种映射，直到它变成自动反应。阅读每个问题描述，在查看解法之前识别模式。速度很重要——面试中您应在 60 秒内识别出模式：
- “给定一个已排序数组，判断是否有两个元素之和为 K”
- “给定一棵树，找出其直径（任意两个节点之间的最长路径）”
- “给定 n 个带冷却时间 k 的任务，找出最少的 CPU 时间片”
- “给定一个字符串，找出最长回文子串”
- “给定 1..n，其中缺少一个数，找出缺失的数字”
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')警示信号：模式失效时怎么办
即使经验丰富的工程师也会一开始选择错误的模式。请识别出表明当前方法有误的信号，并及时转向：
- 您的 O(n²) 方法能通过小规模测试，但在大规模输入上超时 → 需要哈希映射、二分查找或单调结构
- 您的贪心方法被反例否定 → 尝试 DP
- 您的 DP 状态空间太大 → 寻找贪心证明或更聪明的状态定义
- 您的 BFS 得出错误答案 → 检查是否应使用 Dijkstra（加权图），而不是 BFS（无权图）
- 您遇到了空指针异常 → 在编写代码前添加基本情况和边界条件保护
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')在面试中表达模式识别
在面试中，用语言说明您的模式识别过程可以展现专业能力；如果您的思路有误，也能让面试官有机会引导您。请使用以下表达结构：
- “我注意到数组已经排序，所以我在考虑使用二分查找……”
- “题目要求寻找最大子数组，这是一个经典的 Kadane 算法问题……”
- “我们需要所有可能的子集，这说明可以使用带递归树的回溯法……”
- “约束 n ≤ 20 告诉我 2^n = 1M 是可接受的，因此位掩码 DP 可能可行……”
说明模式后，在编写任何一行代码之前，先提及 time 和空间复杂度。这表明您在实现之前就已经考虑了效率。
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)构建您的模式识别词汇
构建模式识别能力最快的方法，是通过按主题分组来解题，而不是随机练习。用一周时间只练习滑动窗口问题，然后练习双指针问题，再练习 DP 问题。快速完成 20 道同类型题目，能够培养您一眼识别该模式的直觉。
每道题之后，写下一条“模式笔记”：记录问题信号以及它触发的模式。构建您自己的速查表。按主题分组解决 200 道题后，您将在 30 秒内识别出约 90% 的面试题——剩下的 10% 即使对经验丰富的工程师来说，也需要仔细分析。
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')快速检查
测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
您在本课中学到了：模式识别会将问题信号映射到算法族——已排序数组意味着二分查找，“所有子集”意味着回溯，“最小成本”意味着 DP，约束 n 会告诉您可接受的复杂度：n ≤ 20 时允许 O(2^n)，n ≤ 10^6 时则需要 O(n log n) 或更优复杂度，并且在编写代码前说明模式和复杂度，能够展现专业能力，也能让面试官及时提供反馈。接下来我们将通过限时模拟面试题，在简单和中等难度下实践模式识别。
常见问题解答
「模式识别速查表」课时是免费的吗？
是的 — 「模式识别速查表」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「模式识别速查表」这节课中我会学到什么？
将 15 个常见问题信号（有序数组、需要所有组合、在约束下最大化价值等）对应到能最快解决它们的算法模式。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「模式识别速查表」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。