常见算法解题范式

发表于 2022/03/06

作者 Optimus-Xs

42 分钟阅读

常见算法解题范式

算法分类总览

基础算法分类表

枚举算法	贪心算法	回溯算法	分治算法	动态规划	数据结构
枚举	贪心	回溯	分治	动态规划	数组
模拟			归并排序	记忆化搜索	链表
			快速选择	状态压缩	双向链表
			递归		栈
					队列
					哈希表
					前缀和
					单调栈
					单调队列
					滚动哈希
					后缀数组
					树
					二叉树
					二叉搜索树
					堆（优先队列）
					字典树
					并查集
					线段树
					树状数组
					图
					最小生成树
					强连通分量
					欧拉回路
					双连通分量
					哈希函数
					有序集合

特定场景算法分类表

搜索与遍历	排序	数学与逻辑	特殊场景类型
深度优先搜索 (DFS)	排序	数学	数据库
广度优先搜索 (BFS)	计数排序	位运算	Shell
二分查找	基数排序	计数	设计
双指针	桶排序	数论	数据流
滑动窗口		几何	交互
拓扑排序		博弈	多线程
最短路		组合数学	迭代器
字符串匹配		概率与统计
字符串		脑筋急转弯
矩阵		扫描线
		随机化
		水塘抽样
		拒绝采样

基础算法分类

枚举算法

枚举算法相关的算法题单: 枚举、 模拟

这是最直接、最容易想到的方法。它的核心思想是穷举所有可能的解，然后从中找到符合条件的那个。

特点: 简单粗暴，实现起来相对容易。
优点: 适用于那些没有明显规律、或者问题规模很小的情况。
缺点: 效率通常很低，时间复杂度很高，大部分情况下会超时。
作用: 在你没有思路时，先用暴力解法作为保底，验证一下逻辑是否正确。这也可以作为优化的起点，让你更清楚地看到问题所在的瓶颈。

具体解题思路如下:

确定枚举的范围和对象: 明确问题有多少个“东西”需要枚举，以及这些“东西”的取值范围是什么。例如，如果要解决一个有 n 个数字的问题，那么枚举的范围就是这些数字的所有组合。
建立搜索策略: 设计一个能覆盖所有可能解的策略，通常使用循环嵌套实现，确保不遗漏任何一个可能的解，同时避免重复。
编写判断条件: 为每一个枚举的候选解设置一个判断条件，检查它是否满足问题的要求，即是否是问题的“有效解”。
进行枚举和筛选: 根据设定的策略，逐一枚举所有可能的候选解。对于每一个候选解，用判断条件进行验证，保留所有符合条件的解。
寻找最优解（如果需要）: 在所有符合条件的解中，根据问题的需求找出最优的解。
优化（可选）: 为了提高效率，可以考虑引入剪枝策略，在枚举过程中排除那些不可能得到最优解的候选解，从而缩小搜索空间

贪心算法

贪心算法相关的算法题单: 贪心

贪心算法的策略是每一步都选择当前看起来最优的解，希望通过一系列局部最优的选择，最终得到一个全局最优的解。

贪心算法的核心在于局部最优。它不从整体上考虑问题，而是将问题分解成多个子问题，在每个子问题上都做出当时看起来最好的决策。它假设通过一系列这样的局部最优决策，最终能够得到一个全局最优解。

并非所有问题都能用贪心算法解决。如果贪心选择性质不成立，那么局部最优解将无法保证全局最优解

贪心选择性质(Greedy Choice Property): 问题的全局最优解可以通过一系列局部最优的选择来达到。这意味着，每一步的局部最优选择都将对最终的全局最优解产生积极影响，并且这个选择一旦做出，就不需要再考虑其对后续步骤的影响。

最优子结构性质(Optimal Substructure): 问题的最优解包含其子问题的最优解。这是动态规划和贪心算法都具备的性质。

如果一个问题同时具备这两个性质，那么贪心算法通常是求解它的最佳选择。

经典案例：找零钱问题

假设你是一个收银员，需要给顾客找零 27 元。你有的零钱是 1 元、5 元、10 元，并且每种零钱的数量是无限的。你的目标是用最少的硬币数量来完成找零。

贪心策略：在每一步都选择面额最大的硬币。

找 27 元：你选择面额最大的 10 元硬币。还剩 17 元要找。
找 17 元：你再次选择 10 元硬币。还剩 7 元要找。
找 7 元：你选择 5 元硬币。还剩 2 元要找。
找 2 元：你选择 1 元硬币。还剩 1 元要找。
找 1 元：你选择 1 元硬币。还剩 0 元。

最终，你使用了 2 个 10 元、1 个 5 元和 2 个 1 元，总共 5 枚硬币。这种贪心策略在这里是正确的，因为它能得到最优解。

贪心算法的局限性

并非所有问题都能用贪心算法解决。如果贪心选择性质不成立，那么局部最优解将无法保证全局最优解。

反例：如果你的硬币面额是 1 元、3 元和 4 元，需要找零 6 元。

贪心策略：
- 你选择 4 元硬币。还剩 2 元。
- 你只能用 1 元硬币找，需要 2 个 1 元。
- 最终使用了 3 枚硬币（4 + 1 + 1）。
正确解法：
- 如果你选择 3 元硬币，还剩 3 元。
- 再选择一个 3 元硬币。
- 最终只使用了 2 枚硬币（3 + 3）。

在这个例子中，贪心策略失败了。这是因为在第一步选择了 4 元后，剩余的 2 元无法被 3 元硬币找零，导致后续只能用更小的硬币，从而导致了次优解。

贪心算法是一种简单、快速的算法，但它只适用于那些具备贪心选择性质和最优子结构的问题。在解决问题时，如果直观上能想到一种贪心策略，你应该先尝试证明它的正确性，然后再进行编码。如果证明失败，可能需要考虑使用动态规划或其他算法。

回溯算法

回溯算法相关的算法题单: 回溯

它的核心思想是: 从一个起点出发，一步步地向前探索，如果发现当前的选择无法达到目标，就退回到上一步，重新选择另一条路径，直到找到所有可能的解或第一个解。

通过将问题建模为决策树或图，并利用递归和剪枝策略寻找所有可行解或最优解。核心在于定义问题中的路径（已做选择）、选择列表（当前可选操作）和终止条件（搜索结束或找到目标），并通过不断选择、递归、回溯（撤销选择）来探索所有可能性。

这个过程就像在一个迷宫里寻找出口: 你选择一条路一直走，如果遇到死胡同，就原路返回到上一个岔路口，选择另一条未走过的路继续探索。

具体解题步骤如下:

定义问题和解空间: 将待解决的问题转化为一个抽象的结构，如决策树或图，并确定其包含问题的解（至少是一个）。
确定搜索方式: 通常采用深度优先搜索策略来遍历解空间。
构建递归函数:
- 判断终止条件: 当当前状态满足搜索的终止条件（例如，达到目标，或解空间已探索完毕）时，返回结果。
- 遍历选择列表: 在当前状态下，列出所有可行的选择。
- 做出选择: 选择一个选项，并更新当前状态，将这个选择加入到“路径”中。
- 递归: 对新的状态进行递归调用，继续探索解空间。
- 回溯（撤销选择）: 在从递归调用返回后，撤销刚才的选择，从“路径”中移除它，以便尝试其他选项，这相当于在决策树中从当前节点返回到父节点。
剪枝: 在探索过程中，加入剪枝函数来判断当前路径是否可能导向无效解或非最优解，从而提前终止搜索，避免不必要的计算。

经典案例: 全排列问题

以“给定一个不含重复数字的数组 [1, 2, 3]，返回它的所有排列”为例，我们可以用回溯算法来解决。

问题: 求 [1, 2, 3] 的所有排列。

回溯思路: 我们可以把这个问题看作是，从 3 个数字中，依次选择一个，填入三个位置。

第 1 个位置: 你有 [1, 2, 3] 三个选择。
第 2 个位置: 假设你选择了 1，那么下一个位置你只能从剩下的 [2, 3] 中选。
第 3 个位置: 假设你又选择了 2，那么最后一个位置你只剩下 3 可以选。

现在，我们通过一步步的回溯来找到所有解。

路径: []，可选项: [1, 2, 3],
- 选择 1, 路径: [1]可选项: [2, 3]
- 选择 2, 路径: [1, 2]，可选项: [3]
  - 选择 3, 路径: [1, 2, 3]。已用完所有数字，找到一个解: [1, 2, 3]
    - 回溯，回到上一步。
  - 回溯，回到 [1]。现在还有另一个选择: 3
- 选择 3, 路径: [1, 3]，可选项: [2]
  - 选择 2, 路径: [1, 3, 2]。找到第二个解: [1, 3, 2]。
    - 回溯。
  - 回溯。
- 回溯，直到回到 []
现在回到起点 []，选择 2
- 路径: [2]，可选项: [1, 3]
  - …重复上面的过程，会找到 [2, 1, 3] 和 [2, 3, 1]
再次回到起点 []，选择 3
- 路径: [3]，可选项: [1, 2]
- …重复上面的过程，会找到 [3, 1, 2] 和 [3, 2, 1]

通过这种“选择-探索-回溯”的方式，我们能够不重不漏地找到所有可能的排列组合

回溯算法通常可以抽象为一个递归函数，它的伪代码结构通常如下:

function backtrack(路径, 选择列表):
  // 满足结束条件，找到一个解
  if 满足结束条件:
      result.add(路径)
      return

  // 遍历所有可能的选择
  for choice in 选择列表:
      // 做出选择
      路径.add(choice)
      // 递归，进入下一层决策树
      backtrack(路径, 新的选择列表)
      // 撤销选择 (回溯)，为下一轮选择做准备
      路径.remove(choice)

分治算法

分治算法相关的算法题单: 分治、归并排序、快速选择、递归

分治算法（Divide and Conquer）是一种将复杂问题分解为多个规模更小、相互独立的子问题，独立递归地解决这些子问题，然后将子问题的解合并，得到原问题的解。

例子：归并排序。将一个数组分成两半，分别对左右两半进行排序，这两个子任务是独立的，互不影响。最后将排序好的两半合并。

核心思想: 分解 -> 解决 -> 合并。
经典应用: 归并排序、快速排序、大整数乘法等。

这个过程可以类比为一次大型团队项目:

分解（Divide）：将项目分解成几个独立的、可管理的小任务。
解决（Conquer）：让不同的团队成员分别去完成各自的小任务。他们可以独立工作，互不影响。
合并（Combine）：当所有小任务都完成后，将它们的结果汇总、整合，形成最终的项目成果。

分治算法的魅力在于，它能将一个难以直接解决的大问题，转化为一系列易于解决的小问题。

经典案例：归并排序（Merge Sort）

归并排序是分治算法最经典的例子之一。它的目标是排序一个数组。

假设我们要对数组 [4, 7, 2, 8, 1, 5, 3, 6] 进行排序。

分解 (Divide)
- 将数组一分为二，得到 [4, 7, 2, 8] 和 [1, 5, 3, 6]。
- 接着，再将这两个子数组各自一分为二，直到每个子数组只剩下一个元素。
- 这个过程一直递归地进行下去，直到每个子数组都只包含一个元素。一个单元素的数组被认为是天然有序的。
解决 (Conquer)
- 对每个只有一个元素的子数组进行排序。因为它们只有一个元素，所以本身就是有序的。
- 比如 [4]、[7]、[2]、[8]…
合并 (Combine)
- 现在，我们开始将有序的子数组两两合并，形成更大的有序数组。
- 合并 [4] 和 [7]，得到 [4, 7]。
- 合并 [2] 和 [8]，得到 [2, 8]。
- 合并 [1] 和 [5]，得到 [1, 5]。
- 合并 [3] 和 [6]，得到 [3, 6]。
- 接着，继续合并 [4, 7] 和 [2, 8]，得到 [2, 4, 7, 8]。
- 同时，合并 [1, 5] 和 [3, 6]，得到 [1, 3, 5, 6]。
- 最后，合并 [2, 4, 7, 8] 和 [1, 3, 5, 6]，得到最终排序好的数组 [1, 2, 3, 4, 5, 6, 7, 8]。
- 这个过程的核心在于，每次分解出的两个子数组是完全独立的，对其中一个子数组的排序不会影响到另一个。

function divideAndConquer(problem):
    // 1. 基本情况 (Base Case)
    // 这是分治的终止条件。当问题规模足够小，可以直接求解时，
    // 无需再进行分解，直接返回结果。
    if problem is simple enough:
        return solve(problem)

    // 2. 分解 (Divide)
    // 将原问题分解成两个或多个相互独立的子问题。
    subproblems = divide(problem)
    
    // 3. 解决 (Conquer)
    // 递归地解决每一个子问题。
    subresults = []
    for subproblem in subproblems:
        subresults.add(divideAndConquer(subproblem))

    // 4. 合并 (Combine)
    // 将所有子问题的解合并成原问题的解。
    result = combine(subresults)

    return result

动态规划

动态规划相关的算法题单: 动态规划、记忆化搜索、状态压缩

动态规划是一种通过拆分问题，定义状态，并利用历史结果来解决复杂问题的方法。它通常用于解决具有重叠子问题和最优子结构特性的问题

重叠子问题: 比如计算斐波那契数列，计算 F(5) 需要 F(4) 和 F(3)，而计算 F(4) 又需要 F(3) 和 F(2)，F(3) 被重复计算了。如果不加处理，每次都重新计算，效率会非常低。

最优子结构: 问题的最优解可以由其子问题的最优解推导而来。这意味着，如果能找到子问题的最优解，你就可以组合它们来构建整个问题的最优解。

基本解题思路:

定义状态: 用一个数组（通常是 dp 数组）来表示问题的解。dp[i] 可能表示前 i 个元素的解。
- 找出状态转移方程: 找出子问题之间的关系, 主要是找到 dp[i] 和之前状态的关系，比如 dp[i] = max(dp[i-1], ...)。
确定初始状态: 找到 dp 数组的初始值。
顺序计算：通常采用自底向上（Bottom-Up）的方式，从最小的子问题开始计算，逐步得到最终解。

经典案例：爬楼梯问题

假设你需要爬 n 级台阶，每次可以爬 1 级或 2 级。请问有多少种不同的方法可以爬到楼顶？
定义状态： dp[i] 表示爬到第 i 级台阶的不同方法数。
状态转移方程：要爬到第 i 级台阶，你只能从第 i-1 级（再爬 1 级）或第 i-2 级（再爬 2 级）上来。因此，dp[i] = dp[i-1] + dp[i-2]。
初始状态：
- dp[1] = 1（爬 1 级台阶只有 1 种方法）
- dp[2] = 2（爬 2 级台阶有 2 种方法：1+1 或 2）
计算：
- dp[3] = dp[2] + dp[1] = 2 + 1 = 3
- dp[4] = dp[3] + dp[2] = 3 + 2 = 5
- …直到 dp[n]。

function dynamicProgramming(n):
    // 1. 定义状态和初始化 (Define State and Initialize)
    // 通常使用一个 dp 数组来存储子问题的解。
    // dp[i] 表示规模为 i 的问题的解。
    dp = new Array(n + 1)
    dp[0] = base_case_value_0
    dp[1] = base_case_value_1

    // 2. 状态转移和计算 (State Transition and Computation)
    // 自底向上地从小规模问题计算到大规模问题。
    // 这个循环是动态规划的核心。
    for i = 2 to n:
        // 状态转移方程：
        // dp[i] 的值依赖于之前子问题的解，例如 dp[i-1]、dp[i-2]...
        dp[i] = calculate_value_from(dp[i-1], dp[i-2], ...)

    // 3. 返回最终结果 (Return Final Result)
    // 最终问题的解通常是 dp 数组的最后一个元素。
    return dp[n]

分治（Divide and Conquer）和动态规划（Dynamic Programming）都是通过将一个大问题分解成子问题来解决的算法思想，但它们在处理子问题的方式上有本质的区别。
分治：解决的子问题是相互独立的，没有重叠。它将问题分解，然后独立地解决每个子问题，最后将子问题的解合并
动态规划：解决的子问题是相互重叠的。这意味着一个子问题可能会被多次计算。动态规划通过存储这些子问题的解，避免了重复计算，从而提高效率。这个过程就像一个有记忆的工人，如果他之前算过一个零件的成本，下次再需要这个零件时，他会直接查记录，而不是重新计算

数据结构

很多算法题的解法都离不开对合适数据结构的运用。选择正确的数据结构能极大地简化问题，提高效率

线性数据结构

线性数据结构相关的算法题单: 数组、链表、双向链表、栈、队列、哈希表、前缀和、单调栈、单调队列、滚动哈希、后缀数组

线性数据结构（如数组、链表、栈、队列）是算法题中最常见的基础。针对这些数据结构的题目，存在一些非常普遍且高效的解题方法或模式

双指针 (Two Pointers)
这是处理数组或链表问题时最常用的技巧之一。通过使用两个指针，从不同方向或以不同速度遍历数据，可以高效地解决许多问题。
- 对撞指针（Two Pointers from Opposite Ends）：一个指针从数组开头向后移动，另一个从结尾向前移动。常用于在有序数组中查找特定值对，比如“两数之和”。
- 快慢指针（Fast and Slow Pointers）：两个指针从同一点出发，一个移动得快，一个移动得慢。常用于检测链表中的环、找到链表的中间节点等。
- 同向指针（Sliding Window）：两个指针都从开头出发，一个指针负责扩张窗口，另一个负责收缩窗口。常用于解决子数组或子串问题，比如找到满足条件的最小子数组。
哈希表 (Hash Table)
哈希表因其 O(1) 的平均查找、插入和删除时间复杂度，成为解决许多线性数据结构问题的利器。它的核心思想是用空间换时间。
- 频率统计：用哈希表记录元素出现的次数，轻松解决“众数”、“出现一次的数字”等问题。
- 快速查找：将元素存入哈希表，之后可以在 O(1) 时间内判断某个元素是否存在。例如，“两数之和”问题，可以把每个元素及其索引存入哈希表，之后遍历时查找目标元素是否已存在。
- 去重和唯一性判断：利用哈希表自动去重的特性，或者用来检查元素是否唯一。
栈和队列 (Stack and Queue)
虽然它们本身就是数据结构，但作为解题工具，它们经常用于处理特定模式的问题。
- 栈（Stack）：后进先出（LIFO）。常用于：
  - 括号匹配：遍历字符串，遇到左括号入栈，遇到右括号时弹出栈顶元素进行匹配。
  - 语法解析：逆波兰表达式求值等。
  - 单调栈：用于找到数组中每个元素左边或右边第一个比它大或小的元素，比如“柱状图中最大的矩形”。
- 队列（Queue）：先进先出（FIFO）。常用于：
  - 广度优先搜索 (BFS)：遍历图或树时按层级进行。
  - 任务调度：按照顺序处理任务。
  - 单调队列：用于解决“滑动窗口最大值”等问题，保证队列的单调性。
排序 (Sorting)
许多看似复杂的线性数据结构问题，在对数据进行排序后，往往会变得简单。
- 预处理：在解决问题前，先对数组进行排序。例如，在有序数组中找“三数之和”，排序后可以使用双指针快速查找。
- 特定算法的预备：一些算法（如二分查找）本身就要求数据是有序的。
前缀和与差分 (Prefix Sum & Difference Array)
这是一类基于数组的预处理技巧，能将区间和、区间修改等操作从 O(n) 降到 O(1)。
- 前缀和 (Prefix Sum)：预先计算数组中每个位置之前的元素总和。之后，求任意区间的和就可以通过两个前缀和相减得到。
- 差分数组 (Difference Array)：通过记录相邻元素之间的差值，将对区间的统一修改（例如，区间内的每个元素都加 1）转化为对两个端点的单点修改。
递归与分治 (Recursion & Divide and Conquer)
- 递归：许多链表问题天然适合递归解决，例如反转链表、合并两个有序链表。
- 分治：将问题分解为独立的子问题。最典型的例子是归并排序，它在数组上实现了高效排序。

总而言之，处理线性数据结构的算法题时，你应首先思考：
能不能用双指针来提高效率？
能不能用哈希表来换取查找速度？
栈或队列能否简化问题？
排序后问题是否会变得更简单

树形数据结构

树形数据结构相关的算法题单: 树、二叉树、二叉搜索树、堆（优先队列）、字典树、并查集、线段树、树状数组

处理树形数据结构的算法题，通常有两种最核心、最通用的方法：递归和迭代。这两种方法又可以引申出几种经典的遍历模式

递归（Recursion）

模式一：自顶向下（Top-Down）
这种模式从根节点开始，通过递归函数向下传递信息。在处理当前节点时，我们假设它的子节点已经通过递归调用处理完毕
模式二：自底向上（Bottom-Up）
这种模式从叶子节点开始，通过递归调用向上返回信息。在处理当前节点时，我们先递归地处理它的子树，然后根据子树返回的信息来处理当前节点。

迭代（Iteration）

虽然递归很直观，但它可能会导致栈溢出，特别是在处理深度很大的树时。这时候，迭代就成为了一个更稳健的选择。迭代通常使用栈（Stack）或队列（Queue）来模拟递归过程。

模式一：深度优先遍历（DFS）
DFS 优先探索树的深度，通常使用栈来实现。它的访问顺序与递归类似。
模式二：广度优先遍历（BFS）
BFS 逐层探索树的节点，通常使用队列来实现。它能确保你总是先访问离根节点最近的节点。

递归是处理树最优雅的方式，自顶向下和自底向上是它的两种基本模式。
迭代通常使用栈（DFS）或队列（BFS）来避免递归的深度限制，并解决特定类型的问题。
对于任何树形问题，你都应该首先考虑这两种通用方法，然后根据问题的具体要求，选择最合适的遍历模式。

图数据结构

图数据结构相关的算法题单: 图、最小生成树、强连通分量、欧拉回路、双连通分量

处理图结构最核心、最通用的方法是图遍历（Graph Traversal），这通常有两种基本方式和处理树一样：深度优先搜索（DFS）和广度优先搜索（BFS）

图和树的BFS和DFS的区别：

树（Tree）：树是一种特殊的图，它不包含环。
图（Graph）：图可以包含环。

在树上进行 DFS 或 BFS 遍历时，由于没有环，你永远不会重复访问同一个节点。但在图上，从一个节点出发，可能会经过一系列边，最终又回到这个节点。如果没有处理好，DFS 或 BFS 可能会陷入死循环

为了避免死循环，在图的遍历中，必须使用一个访问标记数组（visited array）或哈希集合（hash set）来记录已经访问过的节点。

当你面对一个图问题时，通常可以问自己：
这个问题是关于路径还是连通性？如果是，DFS 或 BFS 可能是你的起点。
问题是否要求最短路径？如果是，BFS（无权图）或 Dijkstra/Floyd-Warshall（带权图）可能是答案。
问题是否与最小代价或最小连接有关？如果是，Prim 或 Kruskal 可能是正确方向。

处理图结构的问题，最基础的思路是遍历。DFS 和 BFS 是两种最通用的遍历方式，各自有不同的应用场景。在此基础上，结合贪心、动态规划等思想，可以解决更复杂的图论问题

其他数据结构

其他数据结构相关的算法题单: 哈希函数、有序集合

特定场景算法分类

搜索与遍历

搜索与遍历相关的算法题单: 深度优先搜索、广度优先搜索、二分查找、双指针、滑动窗口、拓扑排序、最短路、字符串匹配、字符串、矩阵

排序

排序相关的算法题单: 排序、计数排序、基数排序、桶排序

排序算法的种类, 实现可参考: 排序算法全面解析

数学与逻辑

数学与逻辑相关的算法题单: 数学、位运算、计数、数论、几何、博弈、组合数学、概率与统计、脑筋急转弯、扫描线、随机化、水塘抽样、拒绝采样

特殊场景

特殊场景相关的算法题单: 数据库、Shell、设计、数据流、交互、多线程、迭代器

参考

Bottom Layer Knowledge

Algorithm

本文由作者按照 CC BY 4.0 进行授权