20 个必备编码模式助你在下一次编码面试中脱颖而出

要想顺利通过编程面试，不仅需要精通算法和数据结构，还需要策略性的方法和敏锐的模式洞察力。在当今竞争激烈的科技行业面试中，理解和掌握编程模式可以显著提升你的解决问题能力，并提升你的表现。

编码模式，或者我们喜欢这样称呼它，是一些反复使用的技术，它们提供了一种结构化的方法来解决复杂问题。你可以把它们想象成算法的基石，帮助你将问题分解成更易于管理的部分。

在这篇博客中，我们将探讨 20 种对于在编程面试中脱颖而出至关重要的编程模式。我们将深入探讨每种模式的优缺点，为您提供一个平衡的视角，帮助您在面试中做出明智的决定。此外，我们还将为您提供“深入学习编程面试”课程中的真实问题示例。我是这门课程的作者，如果您有任何疑问，请随时联系我。

让我们逐一讨论一下每个模式。

1. 两个指针

描述

双指针技术是算法设计中一种巧妙的策略，尤其是在处理数组或链表时。想象一下，你有两根手指，分别放在数组的不同端点或位置。这些“手指”或指针会遍历数组，帮助你高效地比较、搜索甚至操作数据。

用法

有序数据结构：此模式在应用于有序数组或列表时效果显著，允许基于位置的智能决策，从而显著优化算法。
效率：通过减少嵌套循环的需要，双指针技术有助于实现线性时间复杂度，从而使算法更快、更高效。

优点和缺点

优点：
- 效率：对于可能需要 O(n^2) 时间复杂度的问题，实现 O(n) 时间复杂度。
- 简单：一旦掌握，它就能提供直接而优雅的解决方案。
缺点：
- 适用性：主要对涉及序列或区间的问题有益。
- 初始复杂性：可能需要一些时间来掌握这种模式并了解指针的位置和移动方式。

Grokking the Coding Interview 中的示例问题

与目标总和配对：在数组中找到一对加起来等于特定目标总和的数。
对排序数组进行平方：给定一个排序数组，创建一个新数组，其中包含按排序顺序排列的输入数组中所有数字的平方。
三元组和为零：给定一个未排序的数字数组，找到其中所有和为零的唯一三元组。

2. 岛状（矩阵遍历）模式

描述

岛状模式，也称为矩阵遍历，是一种用于在二维数组或矩阵中导航的技术。其主要目标是识别和处理连续的元素组（通常称为“岛”）。当您需要探索和操作基于网格的数据时，此模式尤其有用。

用法

基于网格的问题：擅长解决需要遍历网格来查找连接组件或区域的问题。
连续元素：适用于需要将具有共同属性的相邻元素组合在一起的情况。

优点和缺点

优点：
- 全面：提供一种彻底的方法来探索网格中的所有元素。
- 多功能：可用于解决与二维数组相关的各种问题。
缺点：
- 复杂性：与线性数据结构遍历相比，实现起来可能更复杂。
- 空间开销：可能需要额外的空间来进行递归或队列/堆栈以进行广度优先/深度优先遍历。

Grokking the Coding Interview 中的示例问题

岛屿数量：计算给定二维矩阵中的岛屿数量。
最大的岛屿：找到面积或细胞数量最大的岛屿。
填充：改变二维数组所表示的图像的颜色。

3. 快速指针和慢速指针

描述

快慢指针技术是指两个指针以不同的速度遍历数据结构。这种巧妙的方法在识别循环、查找中间元素以及解决与链表和数组相关的各种其他问题时特别有用。

用法

循环检测：非常适合识别链接列表或数组中的循环，这是一个常见的面试问题。
查找中间元素：无需事先知道长度，即可有效地找到链表的中间元素。
针对特定问题的解决方案：解决特定问题，例如在链接列表中查找循环的起点。

优点和缺点

优点：
- 空间效率：无需额外空间即可实现解决方案，并遵循 O（1）空间复杂度。
- 多功能性：适用于多种问题，使其成为一种多功能的模式。
缺点：
- 初始复杂性：了解如何移动指针以及以什么速度移动指针一开始可能会很棘手。
- 特殊性：虽然用途广泛，但它主要对与链表和某些数组问题相关的问题有益。

Grokking the Coding Interview 中的示例问题

LinkedList Cycle：确定链表是否有循环。
LinkedList 的中间：查找链表的中间节点。
回文链表：检查链表是否为回文。

4.滑动窗口

描述

滑动窗口模式是指在部分数据上创建一个“窗口”，并将其滑动过去，从而高效地解决问题。这种技术对于基于数组或列表的问题尤其有用，因为您需要在所有给定大小的连续子数组或子列表中查找或计算某些内容。

用法

连续子数组：非常适合需要处理连续子数组或子列表的问题。
可变大小窗口：可以适用于窗口大小不固定、需要根据特定条件进行调整的问题。

优点和缺点

优点：
- 效率：针对特定问题，提供一种方法将时间复杂度从 O(n^2) 降低到 O(n)。
- 多功能性：可用于各种问题，包括最大和子数组、给定和的最小子数组以及具有 K 个不同字符的最长子字符串。
缺点：
- 初始复杂性：了解如何调整窗口大小以及何时滑动窗口最初可能具有挑战性。
- 特殊性：主要对涉及连续子数组或子列表的问题有益。

Grokking the Coding Interview 中的示例问题

大小为 K 的最大和子数组：给定一个正数数组和一个正数“k”，找出大小为“k”的任何连续子数组的最大和。
将水果放入篮子：给定一个字符数组，其中每个字符代表一棵果树，给你两个篮子，你的目标是在每个篮子中放入最大数量的水果。
具有 K 个不同字符的最长子字符串：给定一个字符串，找出其中不超过 K 个不同字符的最长子字符串的长度。

5. 合并间隔

描述

合并区间模式是一种处理重叠区间或范围的强大技术。它涉及根据特定条件对区间进行排序和合并。此模式对于基于时间的问题、调度和范围操作非常有用。

用法

重叠间隔：非常适合需要合并重叠间隔或查找间隔是否与任何其他间隔重叠的问题。
区间调度：对于涉及基于时间间隔的调度问题很有用。

优点和缺点

优点：
- 清晰度：提供清晰、系统的方法来处理重叠间隔。
- 效率：有助于降低问题复杂性并获得最佳解决方案。
缺点：
- 排序开销：需要预先对间隔进行排序，这可能会增加时间复杂度。
- 特异性：主要对涉及区间和范围的问题有益。

Grokking the Coding Interview 中的示例问题

合并间隔：给定一个间隔列表，合并所有重叠间隔以生成仅具有互斥间隔的列表。
插入间隔：给定一个按开始时间排序的不重叠间隔列表，在正确的位置插入给定间隔并合并所有必要的间隔以生成仅具有互斥间隔的列表。
区间交集：给定两个区间列表，求这两个列表的交集。每个列表由按开始时间排序的不相交区间组成。

6.循环排序

描述

循环排序是一种独特且直观的排序算法，尤其适用于给定一定范围的数字并要求对其进行排序的问题。这种模式的妙处在于它能够利用数字连续或具有特定范围这一特性，对数字进行就地排序。

用法

连续数字：非常适合您拥有特定范围内的数字数组，并且需要对它们进行排序或查找缺失/重复的数字的情况。
就地排序：提供一种无需使用任何额外空间即可对数字进行排序的方法。

优点和缺点

优点：
- 空间效率：无需额外空间即可实现排序，空间复杂度为 O(1)。
- 时间效率：为特定的基于范围的排序问题提供线性时间复杂度解决方案。
缺点：
- 适用性有限：最适合涉及特定范围内的数字的问题，可能不适用于其他类型的排序问题。
- 初始学习曲线：理解循环排序模式并知道何时应用它可能需要一些时间。

Grokking the Coding Interview 中的示例问题

查找缺失的数字：给定一个包含 n 个不同数字的数组，这些数字取自 0、1、2、...、n，请找出数组中缺失的数字。
查找所有重复项：查找所有重复的数字（不使用额外空间且运行时间为 O（n））。
数组中的重复项：给定一个整数数组，1 ≤ a[i] ≤ n（n = 数组大小），一些元素出现两次，其他元素出现一次。

7. 链表的就地反转

描述

链表就地反转模式是一种无需使用额外内存即可反转链表元素的技术。这是通过操作链表中节点的指针来反转其方向来实现的。

用法

内存效率：由于不使用额外的数据结构，因此这种模式内存效率高。
反转子列表：可以扩展为反转链接列表内的子列表，为解决更复杂的问题提供多功能性。

优点和缺点

优点：
- 空间效率：实现就地逆转，确保O（1）空间复杂度。
- 多功能性：可用于解决与链表相关的各种问题，包括反转子列表和查找回文。
缺点：
- 指针操作：需要小心操作指针，这很容易出错。
- 初始学习曲线：理解如何在不丢失其余链接列表的情况下反转指针最初可能具有挑战性。

Grokking the Coding Interview 中的示例问题

反转 LinkedList：给定单链表的头，反转 LinkedList。
反转子列表：给定 LinkedList 的头和两个位置“p”和“q”，将 LinkedList 从位置“p”反转到“q”。
反转每个 K 元素子列表：给定 LinkedList 的头和数字“k”，从头开始反转每个“k”大小的子列表。

8.树广度优先搜索

描述

树形广度优先搜索 (BFS) 模式涉及逐层遍历树，确保在访问下一深度节点之前，先访问当前深度的所有节点。这通常使用队列来实现。

用法

层次遍历：非常适合需要按层次遍历树或需要对相同深度的节点执行操作的问题。
最小深度：用于查找树的最小深度，因为一旦找到第一个叶节点就可以停止遍历。

优点和缺点

优点：
- 完全遍历：确保树中的每个节点都被访问。
- 级别顺序信息：提供有关每个节点的深度或级别的信息。
缺点：
- 空间开销：需要为队列提供额外的空间，该空间可以与最大级别的节点数一样大。
- 对于深度相关查询效率不高：对于依赖深度信息的问题，深度优先搜索可能更有效。

Grokking the Coding Interview 中的示例问题

二叉树级别顺序遍历：按级别顺序遍历树并返回每级节点的值。
逆序遍历：以逆序遍历树。
之字形遍历：以之字形顺序遍历树。

9. 树深度优先搜索

描述

树深度优先搜索 (DFS) 模式涉及以深度优先的方式遍历树，这意味着在回溯并探索其他分支之前，先尽可能深入地搜索一个分支。这通常使用递归或堆栈来实现。

用法

路径查找：非常适合需要查找路径或检查具有某些属性的路径是否存在的问题。
复杂树遍历：对于更复杂的树遍历问题很有用，您需要在遍历时维持状态或执行操作。

优点和缺点

优点：
- 空间效率：对于平衡树，DFS 比 BFS 使用的空间更少。
- 简单性：递归实现可以更加直接和简洁。
缺点：
- 对于宽树来说效率较低：对于非常宽的树，DFS 会比 BFS 使用更多的空间。
- 可能找不到最短路径：如果您正在寻找无权树中的最短路径，BFS 通常是更好的选择。

Grokking the Coding Interview 中的示例问题

二叉树路径和：给定一棵二叉树和一个数字“S”，查找该树是否有一条从根到叶的路径，使得该路径的所有节点值的总和等于“S”。
所有路径的总和：查找二叉树中所有总和等于给定数字的根到叶路径。
计算路径总数：找出树中总和为给定值的路径数。

10. 两堆

描述

双堆模式涉及使用两个优先级队列（堆）来维护一组数字的运行平衡或中值。其中一个堆跟踪较小的一半数字，另一个堆跟踪较大的一半数字。

用法

运行中位数：非常适合在添加新数字时需要找到一组数字的中位数的问题。
平衡分区：对于需要维护数字平衡分区的问题很有用。

优点和缺点

优点：
- 效率：提供一种在 O(log N) 时间内高效地找到中位数或维持平衡的方法。
- 动态：可以处理随时间推移而添加数字的动态数据集。
缺点：
- 复杂性：由于需要平衡两个堆，实现可能更加复杂。
- 空间开销：需要额外的空间来存储堆中的数字。

Grokking the Coding Interview 中的示例问题

查找数字流的中位数：设计一个类来计算数字流的中位数。
滑动窗口中位数：查找数组中所有大小为“K”的子数组的中位数。
最大化资本：给定一组投资项目及其各自的利润，我们需要找到利润最高的项目。我们获得一笔初始资本，并且只能投资固定数量的项目。我们的目标是选择那些能带来最大利润的项目。

11.子集

描述

子集模式用于处理需要生成集合所有可能组合或子集的问题。当需要探索元素组合的所有不同方式时，此模式尤其有用，而这在许多编码问题中都是常见的情况。

用法

组合问题：非常适合需要生成元素的所有可能组合的问题。
详尽搜索：当您需要对集合的所有可能子集执行详尽搜索时很有用。

优点和缺点

优点：
- 全面：确保您考虑到所有可能的元素组合。
- 多功能：可用于解决各种问题，包括生成幂集、组合和排列。
缺点：
- 时间复杂度：由于集合的子集数量为 2^N，因此可能导致指数时间复杂度。
- 空间复杂度：需要额外的空间来存储所有子集。

Grokking the Coding Interview 中的示例问题

子集：给定一个具有不同元素的集合，找到其所有不同的子集。
具有重复项的子集：给定一组可能包含重复项的数字，找到其所有不同的子集。
排列：给定一组不同的数字，找出它的所有排列。

12. 改进的二分查找

描述

修改后的二分查找模式涉及采用经典二分查找算法来解决各种问题，通常与在排序数组中搜索或查找条件的边界有关。

用法

排序数组：非常适合解决涉及搜索或基于排序数组做出决策的问题。
查找边界：用于在排序数组中查找条件的开始或结束。

优点和缺点

优点：
- 高效性：为搜索问题提供了对数时间复杂度的解决方案，使其效率极高。
- 多功能性：可以解决简单搜索以外的各种问题。
缺点：
- 适用性：主要对涉及排序数组或具有明确边界的条件的问题有益。
- 实施细微差别：需要仔细实施以处理边缘情况并避免无限循环。

Grokking the Coding Interview 中的示例问题

顺序无关二分查找：给定一个已排序的数字数组，找到给定数字的索引。该数组可以按升序或降序排序。
求一个数的上限：给定一个按升序排列的数组，求出给定数的上限。一个数的上限是给定数组中大于或等于该数的最小数。
下一个字母：给定一个按升序排序的小写字母数组，找到给定数组中大于给定“键”的最小字母。

13. 按位异或

描述

按位异或 (XOR) 模式涉及使用 XOR 按位运算符解决问题，通常涉及查找数组中缺失的数字或重复的数字。XOR 是一个二进制运算符，当两位不同时返回 1，当两位相同时返回 0。

用法

查找缺失或重复的数字：非常适合需要在数组中查找缺失数字或重复数字的问题。
位操作：对于需要操作位才能获得所需结果的问题很有用。

优点和缺点

优点：
- 高效性：为某些问题提供恒定的空间解决方案，使其效率极高。
- 简单性：一旦理解，XOR 运算符可用于创建优雅而简单的解决方案。
缺点：
- 特异性：主要对涉及查找缺失或重复数字的问题有益。
- 学习曲线：了解 XOR 运算符的工作原理以及何时使用它可能需要一些时间。

Grokking the Coding Interview 中的示例问题

单个数字：在一个非空的整数数组中，除一个数字外，每个数字都出现了两次，找出那个单个数字。
两个单数：在一个非空数组中，除了两个只出现一次的数字外，其他每个数字都恰好出现了两次。找出这两个只出现一次的数字。
十进制数的补数：对于给定的十进制正数 N，返回其二进制表示的补数作为十进制整数。

14. 前“K”个元素

描述

前“K”个元素模式涉及在数组或数据流中查找“K”个最大或最小元素。当处理大型数据集并且需要根据特定条件维护数据子集时，此模式特别有用。

用法

优先级队列：利用最小堆或最大堆来有效地跟踪“K”个最大或最小元素。
流数据：非常适合数据流入的场景，您需要在任何给定时间维护“K”个最大或最小元素。

优点和缺点

优点：
- 效率：提供一种在 O(N log K) 时间内找到“K”个最大或最小元素的方法。
- 空间效率：只需要 O(K) 空间，无论数据集的大小。
缺点：
- 仅限于“K”个元素：仅维护有关前“K”个元素的信息，而不是整个数据集。
- 堆维护：需要仔细维护堆以确保效率。

Grokking the Coding Interview 中的示例问题

前“K”个数字：给定一个未排序的数字数组，找出其中最大的“K”个数字。
第 K 个最小数：给定一个未排序的数字数组，找出其中第 K 个最小的数字。
距离原点最近的“K”个点：给定二维平面中的点数组，找到距离原点最近的“K”个点。

15. K路合并

描述

K 路合并模式涉及将多个已排序的数组或列表合并为一个已排序的列表。当您有多个已排序的数据集需要合并并保持排序顺序时，此模式非常有用。

用法

多个排序数组：适合合并多个排序数组或列表。
外部排序：在外部排序中很有用，其中要排序的数据不适合内存并存储在已排序的块中。

优点和缺点

优点：
- 效率：提供一种在 O(N log K) 时间内合并多个排序数组的方法，其中“N”是所有数组的元素总数，“K”是数组的数量。
- 空间效率：优先级队列只需要 O(K) 空间。
缺点：
- 依赖于排序：此模式的效率取决于被排序的数组。
- 优先级队列开销：需要维护优先级队列，这增加了复杂性。

Grokking the Coding Interview 中的示例问题

合并 K 个排序列表：给定一个“K”个排序的 LinkedLists 数组，将它们合并为一个排序列表。
M 个排序列表中的第 K 个最小数：给定“M”个排序数组，在所有数组中找到第 K 个最小数。
从 K 个列表中找到覆盖元素的最小范围：给定“M”个排序数组，找到包含每个“M”列表中至少一个数字的最小范围。

16.拓扑排序

描述

拓扑排序是一种用于对有向图的顶点进行线性排序的模式，对于每个有向边 (U, V)，顶点 U 位于 V 之前。这种模式在您有一组任务且某些任务依赖于其他任务的情况下特别有用。

用法

任务调度：非常适合需要按照特定顺序安排任务并尊重其依赖关系的问题。
课程安排：在某些课程有先决条件的课程安排等场景中很有用。

优点和缺点

优点：
- 清晰度：提供一种清晰、系统的方式来排序任务或顶点。
- 检测循环：有助于检测有向图中的循环，这对于理解是否可以进行有效排序非常重要。
缺点：
- 适用性：主要对涉及有向图和顶点排序的问题有益。
- 复杂性：实施可能很复杂，尤其是对于初学者而言。

Grokking the Coding Interview 中的示例问题

拓扑排序：给定一个有向图，找到其顶点的拓扑排序。
任务安排：检查是否可以安排所有任务。
任务调度顺序：找到我们应该选择的任务顺序来完成所有任务。

17. 字典树

描述

字典树（Trie），又称前缀树，是一种用于存储动态字符串集合的树状数据结构，其键通常为字符串。字典树尤其适用于在字符串数据集中检索键，这使得它能够高效地解决基于单词的问题。

用法

自动完成：非常适合在搜索引擎或文本编辑器中实现自动完成功能。
拼写检查器：用于在文字处理器中构建拼写检查器。
IP路由：用于IP路由存储和搜索路由。

优点和缺点

优点：
- 效率：提供快速的字符串检索，并且在涉及字符串键时比哈希表或集合更有效。
- 前缀搜索：非常适合需要前缀搜索或匹配的问题。
缺点：
- 空间开销：当数据集稀疏时，与其他数据结构相比可以使用更多空间。
- 复杂性：实现可能很复杂，尤其是在处理从 Trie 中删除单词时。

Grokking the Coding Interview 中的示例问题

插入和搜索 Trie：在 Trie 中实现插入和搜索。
最长公共前缀：查找一组字符串的最长公共前缀。
单词搜索：给定一个二维棋盘和一个单词，查找该单词是否存在于网格中。

18.回溯

描述

回溯是一种通用的算法技术，它考虑搜索搜索空间的所有可能配置，以解决计算问题。它对于优化问题以及需要对解空间进行完整搜索的情况特别有用。其主要思想是探索每一种可能性，直到找到解或穷尽所有可能性。

用法

组合问题：非常适合解决需要生成所有可能配置（如排列、组合和子集）的问题。
解谜：有助于解决数独、填字游戏和 N-Queens 问题等谜题。

优点和缺点

优点：
- 完整性：确保探索整个解决方案空间，保证找到存在的最佳解决方案。
- 空间效率：由于只需要存储当前状态和决策堆栈，因此使用更少的内存。
缺点：
- 时间复杂度：由于它探索了所有可能的配置，因此可以导致指数时间复杂度。
- 需要优化：可能需要额外的优化，例如修剪，才能适用于更大的实例。

Grokking the Coding Interview 中的示例问题

子集：给定一组数字，找出它的所有子集。
排列：给定一组不同的数字，找出它的所有排列。
N 个皇后：在 N×N 棋盘上放置 N 个皇后，使得任何两个皇后都不会互相威胁。

19. 单调栈

描述

单调栈是一种特殊的数据结构，它维护元素的排序顺序，同时支持栈操作。对于需要在数组中查找下一个更大或更小的元素，或者需要高效地维护连续的最大值或最小值的问题，它特别有用。

用法

下一个更大元素：非常适合为数组中的每个元素找到下一个更大元素。
最大面积直方图：对于查找直方图下最大矩形面积等问题很有用。

优点和缺点

优点：
- 效率：提供一种在线性时间内解决某些问题的方法，使其效率极高。
- 简单性：一旦理解，单调堆栈就可以带来简洁而优雅的解决方案。
缺点：
- 特异性：主要对涉及寻找下一个更大或更小元素的问题以及相关问题有益。
- 学习曲线：了解如何以及何时使用单调堆栈可能需要一些时间。

示例问题

下一个更大元素：给定一个数组，找到数组中每个元素的下一个更大元素。
最大面积直方图：给定一个直方图，找到直方图下最大的矩形面积。
直方图中的最大矩形：给定 n 个非负整数，表示直方图的条形高度，其中每个条形的宽度为 1，求直方图中最大矩形的面积。

20. 0/1 背包（动态规划）

描述

0/1背包问题是一个经典的优化问题，属于动态规划的范畴。在这个问题中，给定一组物品，每件物品都有重量和价值，以及一个背包，背包的最大容量是有限的。目标是确定在不超过背包容量的情况下，背包可以容纳的最大价值。“0/1”这个名称反映了你不能破坏物品，你只能拿走它，或者把它留下。

用法

资源分配：非常适合需要最佳分配有限资源以最大化利润或最小化成本的问题。
预算：适用于需要选择部分项目或投资以最大化回报的预算场景。

优点和缺点

优点：
- 最优性：确保找到最优解决方案，前提是问题满足最优性原则。
- 通用性：可以适用于解决各种各样的优化问题。
缺点：
- 时间和空间复杂度：简单实现的时间和空间复杂度为 O(nW)，其中 n 是物品数量，W 是背包容量。对于大量输入来说，这可能会令人望而却步。
- 需要整数权重和值：经典的 0/1 背包问题要求权重和值为整数。

Grokking the Coding Interview 中的示例问题

0/1 背包：给定“N”件物品的重量和利润，将这些物品放入容量为“C”的背包中。目标是从背包中的物品中获得最大利润。
相等子集和分割：给定一组正数，查明是否可以将其分成两个子集，使得两个子集中元素的总和相等。
子集和：给定一组正数，确定集合中是否存在一个子集，其和等于给定数字“S”。

结论

掌握这些模式绝对不是死记硬背解决方案，而是理解其背后的原理，并学习如何将其应用于各种问题。这些模式的多功能性确保你能够应对各种挑战，让你在任何编程面试中都成为令人敬畏的候选人。

记住，练习是关键。使用这些模式解决的问题越多，你识别问题类型和运用适当模式的能力就越强。所以，坚持练习，持之以恒，你会发现自己在编程面试中表现出色，随时准备应对任何遇到的问题。