14 种模式助您轻松应对任何编码面试问题

对许多开发者来说，准备编程面试的过程总是令人焦虑。面试内容太多，而且很多内容与开发者的日常工作似乎毫无关联，这只会增加他们的压力。

这种情况的后果之一是，现在开发者们常常要花数周时间在 LeetCode 等网站上梳理数百道面试题。我采访过一些焦虑的开发者，他们在面试前最常问的一个问题是：我做的练习题够多了吗？我还能做得更多吗？

这就是为什么我致力于帮助开发者掌握每个问题背后的潜在模式——这样他们就不必担心解决数百道题，也不必忍受 LeetCode 带来的疲劳。如果你理解了这些通用模式，就可以将它们作为模板，解决各种略有不同的其他问题。

这里，我列出了 14 种可用于解决任何编程面试问题的常见模式，以及如何识别每种模式，并提供了每种模式的一些示例问题。如果您有兴趣更详细地了解任何一种模式，请查看《深入理解编程面试：编程问题模式》。

以下模式假设你已经温习过数据结构。如果没有，请查看这些关于数据结构的课程。

以下是我们今天要研究的 14 种模式。

1. 滑动窗口
2. 两个指针或迭代器
3. 快速指针和慢速指针或迭代器
4. 合并间隔
5. 循环排序
6. 链表的就地反转
7. 树形 BFS
8. 树形深度优先搜索
9. 两堆
10. 子集
11. 改进的二分查找法
12. 前 K 个元素
13. K路合并
14. 拓扑排序

让我们开始吧！

1.滑动窗口

滑动窗口模式用于对给定数组或链表的特定窗口大小执行所需操作，例如查找包含所有 1 的最长子数组。滑动窗口从第一个元素开始，不断右移一个元素，并根据要解决的问题调整窗口的长度。在某些情况下，窗口大小保持不变，而在其他情况下，窗口大小会增大或缩小。

通过以下几种方法可以确定给定的问题可能需要滑动窗口：

• 问题输入是线性数据结构，例如链表、数组或字符串
• 你被要求找到最长/最短的子字符串、子数组或所需的值

使用滑动窗口模式的常见问题：

• 大小为“K”的最大和子数组（简单）
• 具有“K”个不同字符的最长子字符串（中等）
• 字符串字谜（困难）

2. 两个指针或迭代器

双指针是一种模式，其中两个指针串联地遍历数据结构，直到其中一个或两个指针满足特定条件。双指针通常在排序数组或链表中搜索对时很有用；例如，当你需要将数组中的每个元素与其他元素进行比较时。

需要两个指针是因为如果只使用指针，你就必须不断循环遍历数组才能找到答案。使用单个迭代器来回迭代对于时间和空间复杂度（即所谓的渐近分析）而言效率低下。虽然使用单个指针的暴力破解或简单解法可以奏效，但它会产生类似于 O(n²) 的复杂度。在很多情况下，两个指针可以帮助你找到具有更佳空间或运行时间复杂度的解决方案。

确定何时使用双指针方法的方法：

• 它将解决处理排序数组（或链接列表）并需要找到满足特定约束的一组元素的问题
• 数组中的元素集合是一对、一个三元组，甚至是一个子数组

以下是一些体现双指针模式的问题：

• 对排序数组求平方（简单）
• 三元组和为零（中等）
• 比较包含退格键的字符串（中等）

3. 快速和慢速指针或迭代器

快慢指针法，又称“龟兔赛跑算法”，是一种使用两个指针以不同的速度在数组（或序列/链表）中移动的指针算法。这种方法在处理循环链表或数组时非常有用。

通过以不同的速度移动（例如，在循环链表中），该算法证明两个指针必然会相遇。一旦两个指针都进入循环，快指针应该会追上慢指针。

如何确定何时使用快速和慢速模式？

• 问题将处理链接列表或数组中的循环
• 当你需要知道某个元素的位置或者链表的总长度时。

我什么时候应该使用它而不是上面提到的双指针方法？

• 在某些情况下，你不应该使用双指针方法，例如在单链表中，因为你不能反向移动。一个使用快慢模式的例子是，当你试图判断一个链表是否是回文时。

具有快速和慢速指针模式的问题：

• 链表循环（简单）
• 回文链表（中等）
• 循环排列（困难）

4. 合并间隔

合并区间模式是处理重叠区间的有效技巧。在很多涉及区间的问题中，你要么需要找到重叠的区间，要么在区间重叠时进行合并。该模式的工作原理如下：

给定两个区间（“a”和“b”），这两个区间可以有六种不同的相互关系：

理解和认识这六种情况将有助于您解决从插入间隔到优化间隔合并的各种问题。

如何确定何时使用合并间隔模式？

• 如果你被要求制作一个仅包含互斥间隔的列表
• 如果您听到“重叠间隔”这个术语。

合并区间问题模式：

• 间隔交叉口（中等）
• 最大 CPU 负载（硬）

5.循环排序

此模式描述了一种处理包含给定范围内数字的数组问题的有趣方法。循环排序模式每次迭代数组中的一个数字，如果当前迭代的数字不在正确的索引处，则将其与正确索引处的数字交换。您可以尝试将数字放在正确的索引处，但这会产生 O(n^2) 的复杂度，这不是最优的，因此需要循环排序模式。

我如何识别这种模式？

• 它们将涉及具有给定范围内数字的排序数组的问题
• 如果问题要求你在排序/旋转数组中找出缺失/重复/最小的数字

具有循环排序模式的问题：

• 找出缺失的数字（简单）
• 找出最小的缺失正数（中等）

6. 链表的就地反转

在很多问题中，你可能会被要求反转链表中一组节点之间的链接。通常，约束是你需要就地执行此操作，即使用现有的节点对象并且不占用额外的内存。这就是上述模式的用武之地。

此模式每次反转一个节点，首先让一个变量（current）指向链表的头部，另一个变量（previous）指向已处理的上一个节点。以锁步的方式，在移动到下一个节点之前，先将当前节点指向“上一个”节点，从而反转当前节点。此外，还要更新变量“previous”，使其始终指向已处理的上一个节点。

我如何确定何时使用此模式：

• 如果你被要求在不使用额外内存的情况下反转链接列表

以链表模式的就地反转为特征的问题：

• 反转子列表（中等）
• 反转每个 K 元素子列表（中等）

7. 树形 BFS

此模式基于广度优先搜索 (BFS) 技术来遍历树，并使用队列跟踪当前层级的所有节点，然后再跳转到下一层级。任何涉及逐层遍历树的问题都可以使用此方法高效解决。

树形 BFS 模式的工作原理是将根节点推送到队列，然后不断迭代，直到队列为空。每次迭代时，我们都会移除队列头部的节点并“访问”该节点。移除每个节点后，我们还会将其所有子节点插入队列。

如何识别树状 BFS 模式：

• 如果要求你逐级遍历一棵树（或按级别顺序遍历）

具有树状 BFS 模式的问题：

• 二叉树层次遍历（简单）
• 之字形遍历（中等）

8.树状深度优先搜索

树 DFS 基于深度优先搜索 (DFS) 技术来遍历树。

您可以使用递归（或迭代方法的堆栈）来在遍历时跟踪所有先前（父）节点。

树形 DFS 模式从树的根开始工作，如果节点不是叶节点，则需要执行三件事：

• 决定是否立即处理当前节点（前序），或者在处理两个子节点之间处理（中序），或者在处理两个子节点之后处理（后序）。
• 对当前节点的两个子节点进行两次递归调用来处理它们。

如何识别树状 DFS 模式：

• 如果你被要求使用中序、前序或后序 DFS 遍历一棵树
• 如果问题需要搜索节点更靠近叶子的位置

具有树状 DFS 模式的问题：

• 路径数总和（中等）
• 所有路径求和（中等）

9. 两堆

在许多问题中，我们会得到一组元素，可以将它们分成两部分。为了解决这个问题，我们需要知道一部分中的最小元素和另一部分中的最大元素。这种模式是解决此类问题的有效方法。

此模式使用两个堆：一个最小堆用于查找最小元素，一个最大堆用于查找最大元素。该模式的工作原理是将前半部分数字存储在最大堆中，因为你想在前半部分找到最大的数字。然后将后半部分数字存储在最小堆中，因为你想在后半部分找到最小的数字。在任何时候，都可以根据两个堆的顶部元素计算出当前数字列表的中位数。

识别“双堆”模式的方法：

• 在优先级队列、调度等情况下很有用
• 如果问题指出你需要找到一个集合的最小/最大/中值元素
• 有时，对于二叉树数据结构的问题很有用

采用双堆模式的问题：

• 查找数字流的中位数（中等）

10.子集

大量的编程面试题都涉及处理给定元素集合的排列和组合。子集模式描述了一种高效的广度优先搜索 (BFS) 方法来处理所有这些问题。

该模式如下所示：

给定一组 [1, 5, 3]

• 从空集开始：[[]] *将第一个数字 (1) 添加到所有现有子集以创建新子集：[[], [1]]; *将第二个数字 (5) 添加到所有现有子集：[[], [1], [5], [1,5]]; *将第三个数字 (3) 添加到所有现有子集：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]]。

以下是子集模式的直观表示：

如何识别子集模式：

• 需要找到给定集合的组合或排列的问题

具有子集模式的问题：

• 有重复项的子集（简单）
• 通过改变大小写来实现字符串排列（中等）

11. 修改二分查找

每当你给定一个已排序的数组、链表或矩阵，并被要求查找某个元素时，你能使用的最佳算法就是二分查找。此模式描述了一种处理所有涉及二分查找问题的有效方法。

对于升序排列的集合，模式如下：

• 首先，找到起始和结束的中间值。一个简单的方法是：中间值 = (起始 + 结束) / 2。但这很容易导致整数溢出，因此建议将中间值表示为：中间值 = 起始 + (结束 — 起始) / 2
• 如果键等于索引中间的数字，则返回中间
• 如果“键”不等于索引中间：
  • 检查 key 是否小于 arr[middle]。如果是，则将搜索范围缩小至 end = middle - 1
  • 检查 key > arr[middle]。如果是，则将搜索范围缩小到 end = middle + 1

以下是修改后的二分搜索模式的直观表示：

如何识别修改后的二分搜索模式：

• 如果你被要求在数组、链表或矩阵中查找某个元素

采用修改后的二进制搜索模式的问题：

• 顺序无关的二分查找（简单）
• 在有序无限数组中搜索（中等）

12. 前 K 个元素

任何要求我们在给定集合中找到顶部/最小/频繁的“K”个元素的问题都属于这种模式。

跟踪“K”个元素的最佳数据结构是堆。此模式将利用堆来解决从给定元素集合中一次处理“K”个元素的多个问题。该模式如下所示：

• 根据问题将“K”个元素插入最小堆或最大堆。
• 遍历剩余的数字，如果发现一个数字大于堆中的数字，则删除该数字并插入较大的数字。

不需要排序算法，因为堆会为您跟踪元素。

如何识别前“K”元素模式：

• 如果你被要求找到给定集合中顶部/最小/频繁的“K”个元素
• 如果你被要求对数组进行排序以找到精确的元素

具有“前 K 个元素”模式的问题：

• 前“K”个数字（简单）
• 前“K”个常用数字（中等）

13. K路合并

K 路合并可帮助您解决涉及一组排序数组的问题。

每当给定“K”个排序数组时，您可以使用堆高效地对所有数组的所有元素进行排序遍历。您可以将每个数组的最小元素推送到最小堆中以获取整体最小值。获取整体最小值后，将同一数组中的下一个元素推送到堆中。然后，重复此过程以对所有元素进行排序遍历。

该模式如下所示：

• 将每个数组的第一个元素插入最小堆中。
• 之后，从堆中取出最小（顶部）元素并将其添加到合并列表中。
• 从堆中移除最小元素后，将同一列表的下一个元素插入到堆中。
• 重复步骤 2 和 3，按排序顺序填充合并列表。

如何识别K路合并模式：

• 问题将涉及排序数组、列表或矩阵
• 如果问题要求您合并排序列表，请找到排序列表中的最小元素。

采用 K 路合并模式的问题：

• 合并 K 个排序列表（中等）
• 求和最大的 K 对（困难）

14.拓扑排序

拓扑排序用于查找相互依赖的元素的线性顺序。例如，如果事件“B”依赖于事件“A”，则按拓扑顺序，“A”位于“B”之前。

该模式定义了一种简单的方法来理解对一组元素执行拓扑排序的技术。

该模式的工作原理如下：
1）初始化

• 使用 HashMap 将图形存储在邻接列表中
• 要查找所有源，请使用 HashMap 来保存入度计数

2）构建图并找到所有顶点的入度

• 根据输入构建图形并填充入度 HashMap。

3）查找所有来源

• 所有入度为“0”的顶点将成为源并存储在队列中。

4）排序

• 对于每个来源，执行以下操作：
• 将其添加到排序列表中。
• 从图中获取其所有子项。
• 将每个孩子的入度减少 1。
• 如果孩子的入度变为“0”，则将其添加到源队列中。
• 重复步骤4，直到源队列为空。

如何识别拓扑排序模式：

• 该问题将处理没有有向循环的图
• 如果要求你按排序顺序更新所有对象
• 如果你有一类遵循特定顺序的对象

具有拓扑排序模式的问题：

• 任务调度（中等）
• 树的最小高度（困难）

下一步是什么？

是不是正在经历 LeetCode 疲劳？学习这 14 种模式，无论问题是什么，你都能更全面地了解如何解决问题。

我知道我们在本文中涵盖了很多数据结构，所以如果你需要复习一下，可以访问这里。如果你想深入了解上述模式或每个模式下的示例问题，请查看《Grokking the Coding Interview: Patterns for Coding Questions》。这是 Grokking 面试系列的最新课程，超过 20,000 名学员通过该课程在顶尖科技公司找到了工作。

我能给予它的最高评价是，我真的希望当我还在准备编码面试时它就存在了。