↓推荐关注↓

貌似2022届校招提前批已经快开始了，现在不管是校招还是社招算法题肯定会被考察到，要么让你手写代码，要么在线做题。这篇文章关于常见的算法解题套路，总结了 14 种算法模式，讲的挺好的。

让我们开始吧！

解题套路

咱们在面试程序员岗位时往往需要经历一个编程面试过程，雇主会借此考验面试者的技术实力。

然而，这些技术问题有时候却和我们的实际工作并无太大关系，也由此可能给我们的编程面试准备阶段带来很大的压力。

曾在 Facebook 和微软工作过的 Educative.io 创始人 Fahim ul Haq 近日发文总结了编程面试所遇到的问题的 14 种最常见的模式，也许能帮你看清各种编程面试问题「背后的真相」。

对很多开发者来说，编程工作的面试准备很容易让人焦虑。面试要涉及的东西实在太多，其中很多还往往与开发者的日常工作无关，只会额外增添压力。

这种现状导致了一个后果：现在的开发者往往需要花费数周时间在 LeetCode 等网站上了解综合数百个问题。

与我谈过的开发者在面试前的一个常见焦虑问题是：我是否已经解决过足够多的实际问题？我本可以做到更多吗？

这就是我想要帮助开发者了解每个问题背后的底层模式的原因——这样他们就不必担忧解决数百个问题以及被 LeetCode 整得疲惫不堪了。

如果你理解面试的通用模式，你就可以将其用作模板，从而解决各种层级的稍有不同的问题。

这里我将列出最常见的 14 种模式，它们可被用于解决任何编程面试问题。

另外我还会说明如何识别每种模式，并会为每种模式提供一些问题示例。

这些内容都只是蜻蜓点水——我强烈建议你看看课程《Grokking the Coding Interview: Patterns for Coding Questions》，里面提供了全面的解释、示例和编程实践。

下面的模式说明假设你已经知悉了数据结构。如果你还不了解，那需要补充一下知识点哦。

我们今天将说明以下 14 种模式：

• 1．滑动窗口
• 2．二指针或迭代器
• 3．快速和慢速指针或迭代器
• 4．合并区间
• 5．循环排序
• 6．原地反转链表
• 7．树的宽度优先搜索（Tree BFS）
• 8．树的深度优先搜索（Tree DFS）
• 9．Two Heaps
• 10．子集
• 11．经过修改的二叉搜索
• 12．前 K 个元素
• 13．K 路合并
• 14．拓扑排序

我们开始吧！

1．滑动窗口

滑动窗口模式是用于在给定数组或链表的特定窗口大小上执行所需的操作，比如寻找包含所有 1 的最长子数组。

从第一个元素开始滑动窗口并逐个元素地向右滑，并根据你所求解的问题调整窗口的长度。

在某些情况下窗口大小会保持恒定，在其它情况下窗口大小会增大或减小。

下面是一些你可以用来确定给定问题可能需要滑动窗口的方法：

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

你可以使用滑动窗口模式处理的常见问题：

• 大小为 K 的子数组的最大和（简单）
• 带有 K 个不同字符的最长子字符串（中等）
• 寻找字符相同但排序不一样的字符串（困难）

2．二指针或迭代器

二指针（Two Pointers）是这样一种模式：

两个指针以一前一后的模式在数据结构中迭代，直到一个或两个指针达到某种特定条件。

二指针通常在排序数组或链表中搜索配对时很有用：比如当你必须将一个数组的每个元素与其它元素做比较时。

二指针是很有用的，因为如果只有一个指针，你必须继续在数组中循环回来才能找到答案。

这种使用单个迭代器进行来回在时间和空间复杂度上都很低效——这个概念被称为「渐进分析（asymptotic analysis）」。

尽管使用 1 个指针进行暴力搜索或简单普通的解决方案也有效果，但这会沿 O(n²) 线得到一些东西。在很多情况中，二指针有助于你寻找有更好空间或运行时间复杂度的解决方案。

用于识别使用二指针的时机的方法：

• 可用于你要处理排序数组（或链接列表）并需要查找满足某些约束的一组元素的问题
• 数组中的元素集是配对、三元组甚至子数组

下面是一些满足二指针模式的问题：

• 求一个排序数组的平方（简单）
• 求总和为零的三元组（中等）
• 比较包含回退（backspace）的字符串（中等）

3．快速和慢速指针

快速和慢速指针方法也被称为 Hare