对于许多开发人员来说，编写面试代码的过程是令人焦虑的。要涵盖的内容太多，而且常常感觉很多内容与开发人员的日常工作无关，这只会增加压力。一个结果是，开发人员现在通常会花费数周时间在LeetCode等网站上仔细研究数百个面试问题。我在面试前对患有焦虑症的开发人员所做的最常见观察之一是：我是否解决了足够多的练习题？我可以做更多吗？这就是为什么我试图专注于帮助开发人员掌握每个问题背后的底层模式的原因，这样他们就不必担心遭受Leetcode解决数百个问题的疲劳。如果您知道常见模式，则可以将它们用作模板，以无数小变体形式解决许多其他问题。在这里，我列出了可用于解决任何编码面试问题的前14种模式，以及如何识别每种模式和每种模式的一些示例问题。这只是触及表面——我强烈建议查看GrokkingtheCodingInterview:PatternsofCodingQuestions以获得全面的解释、示例和编码实践。以下模式假定您已经精通数据结构。如果您还没有，请查看这些关于数据结构的进修课程。这是我们今天要看的14种模式。滑动窗口2指针或迭代器快指针或慢指针或迭代器合并区间循环排序就地反向链表树BFS树DFS两个堆子集改进的二分搜索TopK元素K路合并拓扑排序让我们开始吧让我们走吧！1.滑动窗口滑动窗口模式用于对给定数组或链表的特定窗口大小执行所需的操作，例如查找包含全1的最长子数组。滑动窗口从第一个元素开始，一直向右移动一个元素，根据要解决的问题调整窗口的长度。在某些情况下，窗口大小保持不变，而在其他情况下，窗口大小会增大或缩小。以下是一些可以确定给定问题可能需要滑动窗口的方法：滑动窗口模式用于以下常见问题：大小为“K”的最大总和子数组（简单）具有“K”个不同字符的最长子串（中等）字谜（困难）2.两个指针或迭代器“两个指针"是一种模式，其中两个指针串联遍历数据结构，直到一个或两个指针达到特定条件。在排序数组或链表中搜索对时，两个指针通常很有用；例如，当您必须将数组的每个元素与其他所有元素进行比较时。需要两个指针，因为只有指针，您将不得不不断循环遍历数组才能找到答案。使用单个迭代器来回执行此操作在时间和空间复杂性方面效率低下-一个称为渐近分析的概念。虽然使用1个指针的蛮力或天真的解决方案会起作用，但它会产生类似O(n2)行的结果。在许多情况下，两个指针可以帮助您找到具有更好空间或运行时复杂性的解决方案。确定何时使用“双指针”方法的方法：当你处理排序数组（或链表）时它会遇到一些问题，你需要找到一组满足某些约束的元素。数组中的元素集是一对、三元组甚至是子数组以下是两个指针模式的一些问题：对排序数组求平方（简单）三元组求和为零（中）比较包含退格符的字符字符串（中）3.快速且慢指针快慢指针方法，也称为Hare&Tortoise算法，是一种指针算法，它使用两个指针以不同的速度在数组（或序列/链表）中移动。在处理循环链表或数组时，此方法很有用。通过以不同的速度移动（例如，在循环链表中），算法证明两个指针必然相遇。一旦两个指针都在循环中，快指针应该捕获慢指针。您如何确定何时使用快速和慢速模式？当您需要知道某个元素的位置或链表的总长度时，该问题将处理链表或数组中的循环。你应该在什么时候使用它而不是上面提到的“双指针”方法？有一些情况你不应该使用“双指针”方法，例如在你不能向后移动的单向链表中。何时使用快速和慢速模式的一个例子是当您试图确定链表是否为回文时。快慢指针模式的问题：LinkedListPeriodic(easy)PalindromicLinkedList(medium)CircularCircularArray(hard)4.MergeIntervalMergeInterval模式是一种处理重叠区间的高效技术。在很多涉及区间的问题中，你需要找到重叠的区间，或者如果它们重叠则合并区间。模式如下所示：给定两个区间（“a”和“b”），这两个区间可以通过六种不同的方式相互关联：了解和识别这六种情况将帮助您解决将区间插入到Various的问题优化区间合并的问题。您如何确定何时使用“合并间隔”模式？如果您被要求仅以相互排斥的间隔生成列表如果您听到术语“重叠间隔”。合并区间问题模式：区间交集（中）最大CPU负载（困难）5.循环排序该模式描述了一种有趣的方法来解决涉及包含给定范围内数字的数组的问题。循环排序模式一次遍历数组一个数字，如果正在迭代的当前数字不在正确的索引处，则将其与正确索引处的数字交换。您可以尝试将数字放在正确的索引中，但这会导致O(n^2)的次优复杂度，因此会出现循环排序模式。如何识别此类模式？它们将是涉及给定范围内数字的排序数组的问题（简单）找到最小的缺失正数（中等）6.就地反转链表在许多问题中，您可能会被要求反转一组节点之间的链接的链表。通常约束是您需要就地执行此操作，即使用现有的节点对象并且不使用额外的内存。这就是上面提到的模式派上用场的地方。这种模式一次反转一个节点，其中一个变量（current）指向链表的开头，一个变量（previous）将指向你处理过的前一个节点。在锁步方式中，您可以通过在移动到下一个节点之前将其指向前一个节点来反转当前节点。此外，您将更新变量“previous”以始终指向您处理过的前一个节点。如何确定何时使用此模式：如果要求您在不占用额外内存的情况下反转链表链表模式原地反转问题：撤消子列表（中）反转每个K元素子列表（中）7.TreeBFS该模式基于广度优先搜索(BFS)技术遍历树，并使用队列在跳转到下一层之前跟踪某一层的所有节点。使用这种方法可以有效地解决任何涉及逐步遍历树的问题。TreeBFS模式的工作原理是将根节点推入队列，然后迭代直到队列为空。对于每次迭代，我们删除队列头部的节点，然后“访问”该节点。从队列中移除每个节点后，我们还将其所有子节点插入队列。如何识别TreeBFSpattern：如果要求逐层遍历树（或levelbylevel）TreeBFSpattern的问题：二叉树层序遍历（简单）Zigzag遍历（中等）8.TreeDFSTreeDFS是基于深度优先搜索（DFS）技术遍历树。您可以使用递归（或使用堆栈迭代）在遍历时跟踪所有先前的（父）节点。TreeDFS模式从树的根开始工作，如果节点不是叶子，则需要做三件事：决定是否立即处理当前节点（预订），在处理两个子节点之间（按顺序）)，或者处理两个子节点之间的子节点（后处理）。对当前节点的两个子节点进行两次递归调用以处理它们。如何识别树DFS模式：如果要求您按顺序、预先确定或后DFS遍历树如果问题需要在靠近叶子的节点处搜索树DFS模式的问题：路径数之和（中等）)SummedAllpaths(medium)9.两堆在许多问题中，我们得到一组元素，以便将它们分成两部分。为了解决这个问题，我们有兴趣知道一部分中的最小元素和另一部分中的最大元素。这种模式是解决此类问题的有效方法。此模式使用两个堆；最小堆寻找最小元素，最大堆寻找最大元素。该模式的工作原理是将数字的前半部分存储在最大堆中，因为您想在前半部分找到最大的数字。然后你想把后半部分的数字存入最小堆，因为你想在后半部分找到最小的数字。在任何时候，都可以从两个堆的顶部元素计算出当前数字列表的中位数。识别两个堆模式的方法：在“优先级队列”、“调度”等情况下很有用问题对于问题特征FindingtheMedianofaStreamofNumbers(Medium)10很有用。大量编码面试问题的一个子集涉及处理给定元素集的排列和组合。PatternSubsets描述了一种有效的广度优先搜索(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.修改后的二分搜索每当给定一个排序数组、链表或矩阵，并要求您找到某个元素时，您可以使用的最佳算法就是二分搜索。该模式描述了一种处理涉及二分查找的所有问题的有效方法。对于升序设置，模式如下所示：首先，找到起点和终点的中间位置。找到中间值的一个简单方法是：middle=(start+end)/2。但是这样很容易产生整数溢出，所以建议将中间值表示为：middle=start+(end-start)/2如果key等于索引中间的数，则返回中间值如果“键”不等于中间索引：检查键Checkforkey>arr[middle]。如果减少，搜索结束=中间+1这是“修改后的二进制搜索”模式的可视化表示：修改后的二进制搜索模式的问题：顺序无关的二进制搜索（简单）在排序的无限数组中搜索12.前K个元素任何要求我们在给定集合中找到顶部/最小/最频繁的“K”元素的问题属于这种模式。跟踪“K”个元素的最佳数据结构是堆。此模式将利用堆来解决多个问题，一次处理给定元素集中的“K”个元素。该模式如下所示：根据问题将“K”个元素插入到最小堆或最大堆中。遍历剩余的数字，如果找到比堆中数字大的数字，则删除该数字并插入更大的数字。不需要排序算法，因为堆会为您跟踪元素。如何识别最主要的“K”元素模式：如果您被要求在给定集合中找到顶部/最小/频繁的“K”元素如果您被要求对数组进行排序以找到“K”元素的确切出现排行榜TopProblems:Top"K"Numbers(Easy)Top"K"CommonNumbers(Medium)13.K-wayMergeK-wayMerge帮助您解决涉及一组排序数组的问题。只要得到“K”个排序好的数组，就可以利用堆高效地对所有数组的所有元素进行排序遍历。您可以将每个数组中的最小元素推入最小堆以获得整体最小值。获得总最小值后，将同一数组中的下一个元素压入堆中。然后，重复这个过程，对所有元素进行排序遍历。模式如下：将每个数组的第一个元素插入到最小堆中。之后，从堆中取出最小的（顶部）元素并将其添加到合并列表中。从堆中移除最小的元素后，将同一列表的下一个元素插入堆中。重复步骤2和3以按排序顺序填充合并列表。如何识别K-way合并模式：问题会出现在排序数组、列表或矩阵中如果问题要求你合并排序列表，找到排序列表中的最小元素。K-way合并模式的问题：合并K个排序列表（中）K对最大和（硬）14.拓扑排序拓扑排序用于找到相互依赖的元素的线性顺序。例如，如果事件“B”依赖于事件“A”，则“A”按拓扑顺序排在“B”之前。该模式定义了一种简单的方法来理解对一组元素进行拓扑排序的技术。模式如下所示：初始化a)使用HashMap将图存储在邻接列表中b)要查找所有源，使用HashMap保存度数构建图并找到所有顶点的度数a)从输入并填充度HashMap。查找所有源a)所有度数为“0”的顶点都将作为源并存储在队列中。Sorta)对于每个来源，执行以下操作：—i)将其添加到排序列表中。—ii)从图中获取其所有子项。—iii)从每个孩子的程度中减去1。—iv)如果孩子的学位变为“0”，则将其添加到源队列。b)重复(a)直到源队列为空。如何识别拓扑排序模式：此问题将处理没有定向循环的图形如果要求您按排序顺序更新所有对象如果您有一类对象遵循特定顺序拓扑排序模式问题：任务计划（中）最小树高（困难）下一步是什么？体验LeetCode疲劳？学习这14种模式，你将对如何解决问题有更全面的了解。如果您想更深入地研究上述模式或每个模式的示例问题，请查看《 Grokking编码面试：编码问题的模式》。这是Grokking面试系列中的最新课程，超过20,000名学习者使用该课程在顶级科技公司找到工作。我能给的最高认可是，我真希望在我还在准备写编程面试的时候它就已经存在了。
