14种常见的算法模式

微信公众号
https://mp.weixin.qq.com/s/FbMCAiRN_rO9a_GV4pCGoA

代码仓库
https://github.com/TangBean/grokking-the-coding-interview/

1．滑动窗口

1.1 给定问题可能需要滑动窗口的方法

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

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

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

/**
     * Given an array of positive numbers and a positive number ‘k’,
     * find the maximum sum of any contiguous subarray of size ‘k’.
     * <p>
     * Example 1:
     * <p>
     * Input: [2, 1, 5, 1, 3, 2], k=3
     * Output: 9
     * Explanation: Subarray with maximum sum is [5, 1, 3].
     * <p>
     * Example 2:
     * <p>
     * Input: [2, 3, 4, 1, 5], k=2
     * Output: 7
     * Explanation: Subarray with maximum sum is [3, 4].
     */
    public static int findMaxSumSubArray(int k, int[] arr) {
        // 过滤不符合条件的输入变量
        if (k == 0 || arr == null || arr.length == 0 || arr.length < k) {
            return -1;
        }

        int res = Integer.MIN_VALUE;
        int sum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            // 累加
            sum += arr[i];
            // 当窗口超过k
            if (i >= k) {
                sum -= arr[i - k];
            }
            // 比较当前窗口和上一个窗口的大小
            // 如果当前窗口大，则就选择当前窗口
            if (sum > res) {
                res = sum;
            }
        }
        return res;
    }

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

2．二指针或迭代器

两个指针以一前一后的模式在数据结构中迭代，直到一个或两个指针达到某种特定条件。
二指针通常在排序数组或链表中搜索配对时很有用：比如当你必须将一个数组的每个元素与其它元素做比较时。

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

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

2.2 满足二指针模式的问题

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

3．快速和慢速指针或迭代器

快速和慢速指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。通过以不同的速度进行移动（比如在一个循环链表中），该算法证明这两个指针注定会相遇。只要这两个指针在同一个循环中，快速指针就会追赶上慢速指针。

3.1 、使用快速和慢速模式的时机

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

3.2 、满足快速和慢速指针模式的问题

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

4．合并区间

合并区间模式是一种处理重叠区间的有效技术。

在很多涉及区间的问题中，你既需要找到重叠的区间，也需要在这些区间重叠时合并它们。该模式的工作方式为：给定两个区间（a 和 b），这两个区间有 6 种不同的互相关联的方式：

4.1 使用合并区间的时机

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

4.2 使用合并区间方法解决的问题

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

5．循环排序

循环排序模式一次会在数组上迭代一个数值，如果所迭代的当前数值不在正确的索引处，就将其与其正确索引处的数值交换。

5.1 使用循环排序的时机

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

5.2 使用循环排序解决的问题

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

6．原地反转链表

在很多问题中，你可能会被要求反转一个链表中一组节点之间的链接。

通常而言，你需要原地完成这一任务，即使用已有的节点对象且不占用额外的内存。这就是这个模式的用武之地。

该模式会从一个指向链表头的变量（current）开始一次反转一个节点，然后一个变量（previous）将指向已经处理过的前一个节点。

6.1、使用反转链表的时机

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

6.2、使用反转链表的问题

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

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

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

任何涉及到以逐层级方式遍历树的问题都可以使用这种方法有效解决。

Tree BFS 模式的工作方式是：将根节点推至队列，然后连续迭代知道队列为空。在每次迭代中，我们移除队列头部的节点并「访问」该节点。
在移除了队列中的每个节点之后，我们还将其所有子节点插入到队列中。

7.1 、使用时机

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

7.2、解决的问题

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

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

Tree DFS 是基于深度优先搜索（DFS）技术来遍历树。你可以使用递归（或该迭代方法的技术栈）来在遍历期间保持对所有之前的（父）节点的跟踪。

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

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

8.1、使用时机

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

8.2、解决问题

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

9．Two Heaps

在很多问题中，我们要将给定的一组元素分为两部分。

为了求解这个问题，我们感兴趣的是了解一部分的最小元素以及另一部分的最大元素。这一模式是求解这类问题的一种有效方法。

该模式要使用两个堆（heap）：一个用于寻找最小元素的 Min Heap 和一个用于寻找最大元素的 Max Heap。

9.1、使用时机

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

9.2、解决问题

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

10．子集

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

10.1、使用时机

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

10.2、解决问题

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

11．经过修改的二叉搜索

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

对于一个升序的集合，该模式看起来是这样的：

    1．首先，找到起点和终点的中间位置。
    寻找中间位置的一种简单方法是：middle = (start + end) / 2。
    但这很有可能造成整数溢出，所以推荐你这样表示中间位置：middle = start + (end—start) / 2。
    2．如果键值（key）等于中间索引处的值，那么返回这个中间位置。
    3．如果键值不等于中间索引处的值：
    4．检查 key < arr[middle] 是否成立。如果成立，将搜索约简到 end = middle—1【换行】5．检查 key > arr[middle] 是否成立。如果成立，将搜索约简到 end = middle + 1

解决问题

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

12．前 K 个元素

1
2
3

任何要求我们找到一个给定集合中前面的/最小的/最常出现的 K 的元素的问题都在这一模式的范围内。
跟踪 K 个元素的最佳的数据结构是 Heap。
这一模式会使用 Heap 来求解多个一次性处理一个给定元素集中 K 个元素的问题。

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

12.1、使用时机

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

12.2、解决问题

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

13．K 路合并

K 路合并能帮助你求解涉及一组经过排序的数组的问题。当你被给出了 K 个经过排序的数组时，你可以使用 Heap 来有效地执行所有数组的所有元素的排序遍历。你可以将每个数组的最小元素推送至 Min Heap 以获得整体最小值。在获得了整体最小值后，将来自同一个数组的下一个元素推送至 heap。然后，重复这一过程以得到所有元素的排序遍历结果。

1．将每个数组的第一个元素插入 Min Heap
2．之后，从该 Heap 取出最小（顶部的）元素，将其加入到合并的列表。
3．在从 Heap 移除了最小的元素之后，将同一列表的下一个元素插入该 Heap
4．重复步骤 2 和 3，以排序的顺序填充合并的列表

13.1、使用时机

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

13.2、解决问题

合并 K 个排序的列表（中等）
找到和最大的 K 个配对（困难）

14．拓扑排序

拓扑排序可用于寻找互相依赖的元素的线性顺序。比如，如果事件 B 依赖于事件 A，那么 A 在拓扑排序时位于 B 之前。这个模式定义了一种简单方法来理解执行一组元素的拓扑排序的技术。该模式看起来是这样的：

1．初始化。
    a）使用 HashMap 将图（graph）存储到邻接的列表中；
    b）为了查找所有源，使用 HashMap 记录 in-degree 的数量

2．构建图并找到所有顶点的 in-degree。
    a）根据输入构建图并填充 in-degree HashMap

3．寻找所有的源。
    a）所有 in-degree 为 0 的顶点都是源，并会被存入一个队列

4．排序。
    a）对于每个源，执行以下操作：
        i）将其加入到排序的列表；
        ii）根据图获取其所有子节点；
        iii）将每个子节点的 in-degree 减少 1；
        iv）如果一个子节点的 in-degree 变为 0，将其加入到源队列。

    b）重复 (a)，直到源队列为空。

使用时机

处理无向有环图的问题
如果你被要求以排序顺序更新所有对象
如果你有一类遵循特定顺序的对象