算法题常见模式总结

发表于 分类于 ， 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 13 分钟

本篇博客旨在介绍算法题中最常见的一些模式。对于每一种模式会介绍其基本原理，应用场景以及经典的例题。

双指针（Two Pointers）

基本原理及应用场景

概述

双指针模式是指使用两个指针来遍历数组或列表等线性结构，直到问题的条件被满足。该模式的优势在于可以在一次迭代中跟踪两个不同的索引值。根据具体问题的不同，指针的遍历可以是单向的，也可以是双向的。

例子

举例来说，数组的反转和有序数组的两数之和都可以使用双指针模式来解决：

模式判断

我们可以基于以下条件判断是否需要使用双指针模式（需要全部满足）：

  • 输入数据能够以线性方式进行遍历，即以数组、链表或字符串的形式展现
  • 问题聚焦于输入数据中的特定范围内的元素（由两个指针的位置确定），即仅需要考虑元素的一小部分而非整个集合

此外，满足该模式的问题通常涉及比较或交换两个索引所指向的元素。

现实世界应用

在现实世界中，以下场景可以考虑使用双指针模式来解决：

  • 传输错误：网络传输场景下可以基于双指针判断请求与响应的数据包传输路线是否相同（是否具有多台分流路由器，最多可以容忍一台），以检测传输错误
  • 商品建议：在线购物场景下可以基于双指针为用户推荐配对商品来减免运费

经典例题

有效回文（Easy）

LeetCode 地址

题目

输入一个字符串 s，判断其是否是回文字符串。

示例

思路

使用双指针，从两个方向依次判断对应的字符是否相等，具体步骤如下：

  • 初始化两个指针，一个指向头部，一个指向尾部，分别向数组中间移动
  • 比较指针对应的字符是否相等，不相等则直接为非回文字符串
  • 如果两个指针都到达数组中间，则该字符串为回文字符串

上述步骤的图解如下：

代码

class ValidPalindrome {

  public static boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
      if (s.charAt(left) != s.charAt(right))
      {
        return false;
      }
      left = left + 1;
      right = right - 1;
    }
    return true;
  }
}

复杂度分析

  • 时间复杂度为 \(O(n)\)，其中 n 是字符串中的字符数量，实际只会运行 \(n/2\) 次
  • 空间复杂度为 \(O(1)\)，只使用了常量空间存储两个索引

快慢指针（Fast and Slow Pointers）

基本原理及应用场景

概述

快慢指针模式是指使用两个移动速度不同的指针来遍历线性数据结构，例如链表或数组。与双指针模式不同，快慢指针模式一般用于确定数据结构的特征，而非关注具体的元素值。该模式常用于检测给定数据结构中的循环，也被称为 Floyd 循环检测算法（如果数据结构中存在环，则两个指针必定会相遇）。

例子

举例来说，查找链表的中间节点、识别快乐数（各位平方和最终可以收敛到 1）都可以使用快慢指针模式来巧妙解决：

模式判断

我们可以基于以下条件判断是否需要使用双指针模式（满足其一即可）：

  • 无论是作为中间步骤，还是最终答案，当前问题需要识别：
    • 链表（或数组，下同）的前 \(x\%\) 元素
    • 链表中特定位置的元素，例如位于中点的元素，倒数第 \(k\) 个元素（指针速度相同，快指针先移动）
  • 当前问题需要检测链表等线性结构中是否存在循环

现实世界应用

在现实世界中，以下场景可以考虑使用快慢指针模式来解决：

  • 符号链接（软链接）验证。操作系统中创建多个软链接时，可能会产生循环，此时可以通过快慢指针来识别出这些循环
  • 编译面向对象的程序。大型程序通常会被分为多个程序文件，可以通过快慢指针来识别多个文件之间的循环依赖

经典例题

快乐数（Easy）

LeetCode 地址

题目

编写一个算法来判断一个数字 \(n\) 是不是快乐数。

快乐数的定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1
  • 如果这个过程结果为 1，那么这个数就是快乐数

示例

思路

使用快慢指针求解，如果出现循环且结果不为 1，则不是快乐数，具体步骤如下：

  • 使用慢指针和快指针分别跟踪两个值，慢指针一次计算一次平方和，快指针一次计算两次
  • 通过比较两个指针对应的值判断是否出现循环，同时判断快指针是否已经收敛到 1（收敛则跳出循环）
  • 最终基于快指针是否为 1 输出结果

上述步骤的图解如下（省去中间步骤）：

代码

class HappyNumber {
  
  public static int sumOfSquaredDigits(int number) {
      int totalSum = 0;
      while (number != 0) {
        int digit = number % 10;
        number = number / 10;
        totalSum += (Math.pow(digit, 2));
      }
      return totalSum;
  }
  public static boolean isHappyNumber(int n) {
      int slowPointer = n; 
      int fastPointer = sumOfSquaredDigits(n); 

      while (fastPointer != 1 && slowPointer != fastPointer) {
          slowPointer = sumOfSquaredDigits(slowPointer);
          fastPointer = sumOfSquaredDigits(sumOfSquaredDigits(fastPointer));
      }
      return fastPointer == 1;
  }
}

复杂度分析

  • 时间复杂度为 \(O(\log n)\)，其中 \(n\) 是输入数字（需要分三位数和三位数以上进行讨论证明）
  • 空间复杂度为 \(O(1)\)

滑动窗口（Sliding Window）

基本原理及应用场景

概述

滑动窗口模式通过维护一个移动的元素子集来处理序列数据，该子集被称为窗口。该模式的主要目的是减少算法中嵌套循环的使用，可以看做是双指针模式的变种。

例子

举例来说，查找 DNA 重复序列和最大子数组和都可以使用滑动窗口模式来解决：

模式判断

我们可以基于以下条件判断是否需要使用滑动窗口模式（满足所有条件）：

  • 问题需要在一组连续的数据元素（例如子数组或子字符串）上进行重复计算，以便窗口在输入数组上从一端移动到另一端
    • 窗口的大小可以是固定或可变（取决于具体问题）
    • 重复计算可以是最终解决方案的一部分，也可以是中间步骤
  • 每次窗口移动所进行的计算时间复杂度较小（ \(O(1)\) 时间或缓慢增长函数）

现实世界应用

在现实世界中，以下场景可以考虑使用滑动窗口模式来解决：

  • 电信：查找每个 k 毫秒时段（窗口）连接到蜂窝网络基站的最大用户数
  • 电商：给定一个按用户查看顺序排列的产品 ID 数据集以及可能彼此相似的产品列表，找出这些产品在数据集中同时出现的次数
  • 视频流：给定代表给定用户会话中缓冲事件数量的数字流，计算每一分钟间隔内缓冲事件的中位数
  • 社交媒体内容挖掘：给定两个用户发布的主题列表，找到一个用户发布的最短帖子序列，其中包含另一用户发布的所有主题

经典例题

重复的 DNA 序列（Medium）

LeetCode 地址

题目

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 k 的序列（子字符串），你可以按 任意顺序 返回答案。

示例

思路

本题可以使用滑动窗口 + 哈希集合的方式进行处理，为了实现更优的时空复杂度，题解中并没有直接将字符串放入哈希集合中进行比较，而是使用了 Rabin-Karp algorithm，基于滚动哈希进行字符串比较。

多项式滚动哈希（polynomial rolling hash）的具体计算方式如下： \[ H=c_1 a^{k-1}+c_2 a^{k-2}+\ldots+c_i a^{k-i}+\ldots+c_{k-1} a^1+c_k a^0 \] 其中 \(a\) 是一个常数，\(c_1...c_k\) 是序列中的字符，\(k\) 是子序列的长度。由于 DNA 只有四种核苷酸（AGCT），所以 \(a\) 可以设置为 4（并非一定，也可以大于 4，该值的目的是避免哈希冲突），我们为这些核苷酸分配如下数值：

A G C T
1 2 3 4

例如，对于序列 ATG，其多项式滚动哈希值为： \[ H(A T G)=\left(1 \times 4^2\right)+\left(4 \times 4^1\right)+\left(3 \times 4^0\right)=35 \] 该哈希值不仅可以体现出子字符串所包含的字符，还可以体现字符的顺序，无需在哈希值相等时进行额外的比较。需要注意，在计算新窗口的哈希值时，由于涉及所有位的左移，需要将当前哈希值先乘上 \(a\) 再加上新的哈希值，例如： \[ \begin{gathered} H(C T)=[(H(A C)-H(A)) \times 4]+H(T) \\ H(C T)=\left[6-\left(1 \times 4^1\right)\right] \times 4+\left(4 \times 4^0\right) \\ =12 \end{gathered} \] 该题的具体步骤如下：

  • 使用滑动窗口迭代所有 k 长度的子串
  • 计算窗口内容的哈希值
  • 将该哈希值添加到集合中进行追踪
  • 移动窗口，使用滚动哈希方法计算新窗口的哈希值
  • 如果一个窗口的哈希值已经出现过，则该窗口对应的子序列重复，将其添加到输出集合中
  • 分析完所有子串后，返回输出集合

代码

class RepeatedDNA {
	
    public static Set<String> findRepeatedSequences(String s, int k) {
      
        int n = s.length();

        if (n < k) {
            return new HashSet<>();
        }

        Map<Character, Integer> mapping = new HashMap<>();
        mapping.put('A', 1);
        mapping.put('C', 2);
        mapping.put('G', 3);
        mapping.put('T', 4);

        int a = 4;

        List<Integer> numbers = new ArrayList<>(Arrays.asList(new Integer[n]));
        for (int i = 0; i < n; i++) {
            numbers.set(i, mapping.get(s.charAt(i)));
        }

        int hashValue = 0;

        Set<Integer> hashSet = new HashSet<>();
        Set<String> output = new HashSet<>();

        for (int i = 0; i < n - k + 1; i++) {
            if (i == 0) {
                for (int j = 0; j < k; j++) {
                    hashValue += numbers.get(j) * (int) Math.pow(a, k - j - 1);
                }
            } else {
                int previousHashValue = hashValue;
                hashValue = ((previousHashValue - numbers.get(i - 1) * (int) Math.pow(a, k - 1)) * a) + numbers.get(i + k - 1);
            }

            if (hashSet.contains(hashValue)) {
                output.add(s.substring(i, i + k));
            }

            hashSet.add(hashValue);
        }
        return output;
      }
}

复杂度分析

  • 时间复杂度为 \(O(n)\)，\(n\) 为输入字符串的长度
  • 空间复杂度为 \(O(n)\)

合并区间（Merge Intervals）

基本原理及应用场景

概述

合并区间是一种处理重叠区间的有效手段，通常用于日程安排（scheduling）相关的问题。理解这一模式的关键在于理解区间之间的关联关系，总共有以下六种：

例子

举例来说，合并重叠区间和会议室问题都可以使用合并区间模式来解决：

模式判断

我们可以基于以下条件判断是否需要使用滑动窗口模式（满足所有条件）：

  • 输入数据是一个有序区间数组

  • 问题涉及对重叠区间的处理

现实世界应用

在现实世界中，以下场景可以考虑使用重叠区间模式来解决：

  • 显示忙碌日程：向其他用户展示当前用户的忙碌时间段（合并多个区间）
  • 安排新会议：为用户安排会议日程，确保会议的时间不会冲突
  • 操作系统中的任务调度：根据任务优先级和计算机处理调度的空闲槽来调度操作系统中的任务

经典例题

就地反转链表（In-place Reversal of a LinkedList）

基本原理及应用场景

概述

就地反转链表模式允许我们在不使用额外存储空间的情况下反转一个链表。我们需要同时跟踪当前节点、下一个节点以及前一个节点，在一次循环中完成链表的反转，该方法的空间复杂度为 \(O(1)\)，时间复杂度为 \(O(n)\)。反转链表的具体流程如下图所示：

image-20231114202602063

例子

举例来说，顺时针旋转 k 次链表可以使用就地反转链表模式来解决：

模式判断

我们可以基于以下条件判断是否需要使用就地反转链表模式（满足所有条件）：

  • 问题涉及对给定链表的翻转（全部或部分）
  • 对链表的修改必须原地完成，不允许使用额外的存储空间

现实世界应用

在现实世界中，以下场景可以考虑使用就地反转链表模式来解决：

  • 股票：向经纪人分配按照交易到达的顺序分配股票交易（反转股票列表）
  • 电商：给定按照价格和欢迎程度升序排列的商品，需要进行倒序展示（反转商品列表）

经典例题

双堆（Two Heaps）

基本原理及应用场景

经典例题

多路归并（K-way merge）

基本原理及应用场景

经典例题

Top K 元素（Top K Elements）

基本原理及应用场景

经典例题

改造二分查找（Modified Binary Search）

基本原理及应用场景

经典例题

子集（Subsets）

基本原理及应用场景

经典例题

贪婪算法（Greedy Techniques）

基本原理及应用场景

经典例题

回溯法（Backtracking）

基本原理及应用场景

经典例题

动态规划（Dynamic Programming）

基本原理及应用场景

经典例题

循环排序（Cyclic Sort）

基本原理及应用场景

经典例题

拓扑排序（Topological Sort）

基本原理及应用场景

经典例题

矩阵（Matrices）

基本原理及应用场景

经典例题

栈（Stacks）

基本原理及应用场景

经典例题

图（Graphs）

基本原理及应用场景

经典例题

树的深度优先搜索（Tree Depth First Search）

基本原理及应用场景

经典例题

树的广度优先搜索（Tree Breadth First Search）

基本原理及应用场景

经典例题

字典树（Trie）

基本原理及应用场景

经典例题

哈希表（Hash Maps）

基本原理及应用场景

经典例题

定向追踪（Knowing What to Track）

基本原理及应用场景

经典例题

并查集（Union Find）

基本原理及应用场景

经典例题

自定义数据结构（Custom Data Structures）

基本原理及应用场景

经典例题

位运算（Bitwise Manipulation）

基本原理及应用场景

经典例题

本文参考自 educative 的经典课程 Grokking Coding Interview Patterns in Java。