代码面试

Grokking the Coding Interview

模式一：滑动窗口

滑动窗口用于对给定数组和链表的特定窗口大小执行所需的操作

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

题目练习

1. 大小为K的最大总和子数组（简单）

2. 给定总和的最小子数组（简单）

3. 最长的具有K个不同字符的子字符串（中）

模式二：双指针

“两个指针”是一种模式，其中两个指针串联遍历数据结构，直到一个或两个指针都达到特定条件。两个指针在排序数组或链接列表中搜索对时通常很有用；例如，当您必须将数组的每个元素与其他元素进行比较时。

需要两个指针，因为只有一个指针，您将不得不不断地循环遍历数组以找到答案。用单个迭代器来回进行此操作对于时间和空间复杂度而言效率低下-一种称为渐近分析的概念。尽管使用1个指针的强力或幼稚的解决方案将起作用，但它将产生类似于O（n²）的东西。在许多情况下，两个指针可以帮助您找到具有更好空间或运行时复杂性的解决方案。

确定何时使用“两指针”方法的方法：

• 在处理排序数组（或链接列表）并且需要找到一组满足某些约束的元素时，它将遇到一些问题。
• 数组中的元素集是一对，三元组甚至是子数组

以下是具有两个指针模式的一些问题：

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

模式三：快慢指针

快速和慢速指针方法，也称为 Hare＆Tortoise算法，是一种指针算法，它使用两个指针以不同的速度在数组（或序列/链接列表）中移动。 处理循环链表或数组时，此方法非常有用。

通过以不同的速度移动（例如，在循环链表中），该算法证明两个指针必然会合。一旦两个指针都处于循环循环中，快速指针应捕获慢速指针。

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

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

什么时候应该在上面提到的“两指针”方法上使用它？

• 在某些情况下，您不应该使用“两指针”方法，例如在单链列表中，您不能向后移动。何时使用快速和慢速模式的一个示例是当您试图确定链接列表是否为回文式时。

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

• 链接列表周期（简单）
• 回文链接列表（中）
• 循环循环阵列（硬）

模式四：合并间隔

合并间隔模式是处理重叠间隔的有效技术。在很多涉及间隔的问题中，您需要找到重叠的间隔，或者如果它们重叠，则需要合并间隔。该模式如下所示：

给定两个间隔（“ a”和“ b”），两个间隔可以通过六种不同的方式相互关联：

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

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

• 如果要求您仅以互斥间隔生成列表
• 如果您听到术语“重叠间隔”。
• 合并间隔问题模式：
• 区间相交（中）
• 最大CPU负载（硬）

模式五：循环排序

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

[图片上传失败...(image-b02483-1592497226252)]

如何识别这种模式？

• 它们将是涉及编号在给定范围内的排序数组的问题
• 如果问题要求您在排序/旋转数组中查找缺失/重复/最小的数字

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

• 查找丢失的号码（简单）
• 查找最小的遗漏正数（中）

模式六：就地反转链表

在很多问题中，可能会要求您反向链接列表的一组节点之间的链接。通常，约束是您需要就地执行此操作，即使用现有的节点对象而不使用额外的内存。这是上面提到的模式有用的地方。

此模式一次反转一个节点，其中一个变量（当前）指向链接列表的开头，而一个变量（上一个）将指向您已处理的上一个节点。以锁定步骤的方式，您可以通过将当前节点指向上一个节点来反转该节点，然后再移动到下一个节点。另外，您将更新变量“ previous”以始终指向您已处理的上一个节点。

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

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

链表模式就地反转的问题：

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

模式七：树的宽度优先搜索

此模式基于广度优先搜索（BFS）技术来遍历树，并使用队列来跟踪某个级别的所有节点，然后再跳转到下一个级别。使用这种方法可以有效地解决涉及逐级遍历树的任何问题。

Tree BFS模式的工作原理是将根节点推送到队列，然后不断迭代直到队列为空。对于每次迭代，我们都删除队列开头的节点，然后“访问”该节点。从队列中删除每个节点后，我们还将其所有子节点插入队列。

如何识别Tree BFS模式：

• 如果要求您逐级遍历树（或逐级遍历）

具有Tree BFS模式的问题：

二叉树级顺序遍历（简单）

• 锯齿形遍历（中）

模式八：树的深度优先搜索

树DFS基于深度优先搜索（DFS）技术遍历树。

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

Tree DFS模式通过从树的根部开始工作，如果节点不是叶子，则需要做三件事：

1. 决定是立即处理当前节点（预定），还是在处理两个子节点之间（按顺序），还是在处理两个子节点之后（后处理）。
2. 对当前节点的两个子节点进行两次递归调用以处理它们。

如何识别Tree DFS模式：

• 如果系统要求您按顺序，预顺序或后顺序DFS遍历树
• 如果问题需要在节点更靠近叶子的位置进行搜索

具有Tree DFS模式的问题：

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