14种常见算法模型

1. 滑动窗口

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

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

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

长度为 K 的子数组的最大和（简单）

可能会要求子数组不包含重复数字，可以用 hashmap 的方式来计数，如果 size == k 说明满足长度，反之存在重复数据

带有 K 个不同字符的最长子字符串（中等）
寻找字符相同但排序不一样的字符串（困难）

2. 二指针或迭代器

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

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

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

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

3. 快速和慢速指针

3.1 如何判别使用快速和慢速模式的时机？

处理链表或数组中的循环的问题
当你需要知道特定元素的位置或链表的总长度时

3.2 何时应该优先选择这种方法，而不是上面提到的二指针方法？

有些情况不适合使用二指针方法，比如在不能反向移动的单链接链表中。使用快速和慢速模式的一个案例是当你想要确定一个链表是否为回文（palindrome）时。

3.3 下面是一些满足快速和慢速指针模式的问题：

链表循环（简单）
回文链表（中等）
环形数组中的循环（困难）

4. 合并区间

4.1 那么如何确定何时该使用合并区间模式呢？

如果你被要求得到一个仅含互斥区间的列表
如果你听到了术语「重叠区间（overlapping intervals）」

4.2 合并区间模式的问题：

区间交叉（中等）
最大 CPU 负载（困难）

5. 循环排序

5.1 如何识别这种模式？

涉及数值在给定范围内的排序数组的问题
如果问题要求你在一个排序/旋转的数组中找到缺失值/重复值/最小值

5.2 循环排序模式的问题：

找到缺失值（简单）
找到最小的缺失的正数值（中等）

6. 原地反转链表

6.1 如何识别使用该模式的时机：

如果你被要求在不使用额外内存的前提下反转一个链表

6.2 原地反转链表模式的问题：

反转一个子列表（中等）
反转每个 K 个元素的子列表（中等）

7. 树的宽度优先搜索（Tree BFS）

该模式基于宽度优先搜索（BFS）技术，可遍历一个树并使用一个队列来跟踪一个层级的所有节点，之后再跳转到下一个层级。

7.1 如何识别 Tree BFS 模式：

如果你被要求以逐层级方式遍历（或按层级顺序遍历）一个树

7.2 Tree BFS 模式的问题：

二叉树层级顺序遍历（简单）
之字型遍历（Zigzag Traversal）（中等）

8. 树的深度优先搜索（Tree DFS）

你可以使用递归（或该迭代方法的技术栈）来在遍历期间保持对所有之前的（父）节点的跟踪。

8.1 Tree DFS 模式的工作方式是从树的根部开始，如果这个节点不是一个叶节点，则需要做两件事：

1．决定现在是处理当前的节点（pre-order），或是在处理两个子节点之间（in-order），还是在处理两个子节点之后（post-order）
2．为当前节点的两个子节点执行两次递归调用以处理它们

8.2 如何识别 Tree DFS 模式：

如果你被要求用 in-order、pre-order 或 post-order DFS 来遍历一个树
如果问题需要搜索其中节点更接近叶节点的东西

8.3 Tree DFS 模式的问题：

路径数量之和（中等）
一个和的所有路径（中等)

9. Two Heaps

先将前一半的数值存储到 Max Heap，这是由于你要寻找前一半中的最大数值。然后再将另一半存储到 Min Heap，因为你要寻找第二半的最小数值。在任何时候，当前数值列表的中间值都可以根据这两个 heap 的顶部元素计算得到。

9.1 识别 Two Heaps 模式的方法：

在优先级队列、调度等场景中有用
如果问题说你需要找到一个集合的最小/最大/中间元素
有时候可用于具有二叉树数据结构的问题

9.2 Two Heaps 模式的问题：

查找一个数值流的中间值（中等）

10. 子集

很多编程面试问题都涉及到处理给定元素集合的排列和组合。

子集（Subsets）模式描述了一种用于有效处理所有这些问题的宽度优先搜索（BFS）方法。

10.1 如何识别子集模式：

你需要找到给定集合的组合或排列的问题

10.2 子集模式的问题：

带有重复项的子集（简单）
通过改变大小写的字符串排列（中等）

11. 经过修改的二叉搜索

只要给定了排序数组、链表或矩阵，并要求寻找一个特定元素，你可以使用的最佳算法就是二叉搜索。

这一模式描述了一种用于处理所有涉及二叉搜索的问题的有效方法。

11.1 经过修改的二叉搜索模式的问题：

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

12. 前 K 个元素

任何要求我们找到一个给定集合中前面的/最小的/最常出现的 K 的元素的问题都在这一模式的范围内。

跟踪 K 个元素的最佳的数据结构是 Heap。

这一模式会使用 Heap 来求解多个一次性处理一个给定元素集中 K 个元素的问题。

12.1 该模式是这样工作的：

根据问题的不同，将 K 个元素插入到 min-heap 或 max-heap 中
2．迭代处理剩余的数，如果你找到一个比 heap 中数更大的数，那么就移除那个数并插入这个更大的数

12.2 如何识别前 K 个元素模式：

如果你被要求寻找一个给定集合中前面的/最小的/最常出现的 K 的元素
如果你被要求对一个数值进行排序以找到一个确定元素

12.3 前 K 个元素模式的问题：

前面的 K 个数（简单）
最常出现的 K 个数（中等

13. K 路合并

13.1 如何识别 K 路合并模式：

具有排序数组、列表或矩阵的问题
如果问题要求你合并排序的列表，找到一个排序列表中的最小元素