算法入门很简单：算法题的破解之道下篇

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

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

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

如何识别Tree BFS模式：

1. 如果要求您逐级遍历树（或逐级遍历）具有Tree BFS模式的问题：
   二叉树级顺序遍历（简单）
2. 锯齿形遍历（中）

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

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

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

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

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

如何识别Tree DFS模式：

1. 如果系统要求您按顺序，预顺序或后顺序DFS遍历树
2. 如果问题需要在节点更靠近叶子的位置进行搜索具有Tree DFS模式的问题：
3. 路径数总和（中）
4. 求和的所有路径（中）

模式九：两个堆​

在许多问题中，我们被赋予一组元素，以便可以将它们分为两部分。为了解决该问题，我们有兴趣知道一个部分中的最小元素，而另一部分中的最大元素。这种模式是解决此类问题的有效方法。

该模式使用两个堆；最小堆可查找最小元素，最大堆可查找最大元素。该模式通过将数字的前半部分存储在Max Heap中而起作用，这是因为您要在前半部分中找到最大的数字。然后，您要在最小堆中存储数字的后半部分，因为您要在后半部分中找到最小的数字。在任何时候，都可以从两个堆的顶部元素计算当前数字列表的中位数。

识别两个堆模式的方法：

1. 在诸如“优先级队列”，“计划”之类的情况下很有用
2. 如果问题表明您需要找到集合中最小/最大/中值的元素
3. 有时，对于解决具有二叉树数据结构的问题很有用问题特点
4. 查找数字流的中位数（中）

模式十：子集​

大量的编码面试问题涉及处理给定元素集的置换和组合。模式子集描述了一种有效的广度优先搜索（BFS）方法来处理所有这些问题。

该模式如下所示：

给定一组[1、5、3]

1. 从一个空集开始：[[]]
2. 将第一个数字（1）添加到所有现有子集以创建新的子集：[[]，[1]];
3. 将第二个数字（5）添加到所有现有子集：[[]，[1]，[5]，[1,5]]；
4. 将第三个数字（3）添加到所有现有子集：[[]，[1]，[5]，[1,5]，[3]，[1,3]，[5,3]，[1， 5,3]]。

这是子集模式的直观表示：

模式十一：改变的二分查找​

每当给您排序数组，链接列表或矩阵，并且要求您查找某个元素时，您可以使用的最佳算法是二进制搜索。此模式描述了一种有效的方法来处理涉及二进制搜索的所有问题。

对于升序设置，模式如下所示：

1. 首先，找到开始和结束的中间位置。查找中间值的简单方法是：middle =（start + end）/2。但这很有可能产生整数溢出，因此建议将中间值表示为：Middle = start +（end-start） / 2
2. 如果键等于索引中间的数字，则返回中间
3. 如果“键”不等于中间索引：
4. 检查键<arr [middle]。如果减少，则搜索结束=中间— 1
5. 检查key> arr [middle]。如果减少，则搜索结束=中间+1

这是“修改后的二进制搜索”模式的直观表示：

具有修改后的二进制搜索模式的问题：

与顺序无关的二进制搜索（简单）在排序的无限数组中搜索（中等）

模式十二：按位异或​

模式十三：Top k问题​

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

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

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

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

如何识别顶部的“ K”元素模式：

1. 如果要求您查找给定集合的顶部/最小/频率最高的“ K”元素
2. 如果系统要求您对数组进行排序以查找确切的元素具有“前K个”元素模式的问题：
3. 前“ K”号（简单）
4. 前“ K”个常见数字（中）

模式十四：K路合并​

K-way Merge可帮助您解决涉及一组排序数组的问题。

只要获得“ K”个排序数组，就可以使用堆有效地对所有数组的所有元素进行排序遍历。您可以将每个数组中的最小元素推入最小堆中，以获取整体最小值。获得总最小值后，将下一个元素从同一数组推到堆中。然后，重复此过程以对所有元素进行排序遍历。

该模式如下所示：

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

如何识别K-way合并模式：

1. 该问题将出现排序的数组，列表或矩阵
2. 如果问题要求您合并排序列表，请在排序列表中找到最小的元素。K-way合并模式的问题：
3. 合并K个排序列表（中）
4. K对最大和（硬）

模式十五：0/1背包（动态规划）​

模式十六：拓扑排序（图）​

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

该模式定义了一种简单的方法，可以理解用于对一组元素进行拓扑排序的技术。​

该模式如下所示：​

1. 初始化 a）使用HashMap将图存储在邻接列表中 b）要查找所有源，请使用HashMap保持度数构建图并查找所有顶点的度数​
2. 从输入中构建图形并填充度数HashMap。​
3. 查找所有源 a）所有度数为“ 0”的顶点将作为源，并存储在队列中。​
4. 排序 a）对于每个来源，请执行以下操作： —i）将其添加到排序列表中。 — ii）从图中获取其所有子级。 — iii）将每个孩子的度数减1。— iv）如果孩子的度数变为'0'，则将其添加到源队列中。 b）重复（a），直到源队列为空。​

如何识别拓扑排序模式：​

1. 该问题将处理没有定向周期的图
2. 如果要求您按排序顺序更新所有对象
3. 如果您有一类遵循特定顺序的对象具有拓扑排序模式的问题：​
4. 任务计划（中）
5. 最小树高（硬）