递归

  • 定义：是指一个问题可以被分解为更小的、相同或类似的问题，并且这些子问题可以通过递归调用算法本身来解决。
  • 基本情况：递归算法必须具有一个基本情况，这是递归的结束条件。当问题的规模足够小，可以直接解决时，递归算法就会停止递归。
  • 递归调用：递归算法通过递归调用自身来解决问题。每个递归调用都会将问题规模缩小到一个更小的子问题上，直到达到基本情况。
  • 栈空间：递归算法使用栈空间来存储每个递归调用的上下文信息。每次递归调用都会将当前的上下文信息推入栈空间，当递归结束时，栈空间会弹出上一个上下文信息。
  • 递归与迭代：递归算法与迭代算法是算法设计中的两种主要思想。递归算法通过递归调用自身来解决问题，而迭代算法则使用循环来解决问题。
  • 时间复杂度：粗略估算方法就是用递归函数调用次数（递归树的节点数） x 递归函数本身的复杂度。

搜索

深度优先搜索

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，它从起始顶点开始，依次访问其所有相邻顶点，并递归地对每个相邻顶点进行深度优先搜索，直到遍历完整个图。知识点：

  • 栈：DFS可以使用栈来实现。从起始顶点开始，将其压入栈中，然后循环执行以下操作：从栈中取出一个顶点，并访问其所有未访问的相邻顶点，将其压入栈中。直到栈为空，搜索结束。
  • 递归：DFS也可以使用递归实现。从起始顶点开始，依次递归地访问其所有相邻顶点，直到遍历完整个图。递归实现的优点是代码简洁清晰，但也有可能导致栈溢出。
  • 标记数组：为了避免重复访问已经访问过的顶点，DFS通常使用一个布尔类型的标记数组来记录每个顶点是否已经访问过。
  • 拓扑排序：DFS可以用来实现拓扑排序。拓扑排序是对有向无环图的所有顶点进行排序的一种算法。通过DFS，可以将图中的所有顶点按照其依赖关系排序，从而实现拓扑排序。
  • 时间复杂度：DFS的时间复杂度取决于搜索过程中访问每个顶点的次数。对于稠密图，每个顶点都会被访问一次，因此时间复杂度为 $O(V^2)$，其中 $V$ 是顶点数。对于稀疏图，时间复杂度可以达到 $O(V+E)$，其中 $E$ 是边数。
  • 空间复杂度：DFS靠递归的堆栈记录⾛过的路径，要找到最短路径得把⼆叉树中所有树杈都探索完才能对⽐出最短的路径有多⻓，DFS 算法空间复杂度最坏情况下是树⾼度$O(logN)$ 。
  • 应用：DFS通常用于解决一些搜索深度较小的问题，例如拓扑排序、连通性判断等。由于DFS搜索深度较大时容易出现堆栈溢出等问题，因此需要选择合适的算法实现。

力扣指南

深度优先搜索
题目 技巧 难度
✅130. 被围绕的区域 从边界开始处理 🌟🌟
✅200. 岛屿数量 🌟🌟
✅417. 太平洋大西洋水流问题 双边界逆流而上 🌟🌟
✅529. 扫雷游戏 🌟🌟
✅1254. 统计封闭岛屿的数目 去除边界 🌟🌟
✅1020. 飞地的数量 🌟🌟
✅695. 岛屿的最大面积 🌟🌟
✅1905. 统计子岛屿 🌟🌟

深度优先搜索——树专项

二叉树解题的思维模式分两类：

  1. 遍历：通过遍历一遍二叉树得到答案，用一个 traverse 函数配合外部变量来实现
  2. 分解：定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案，写出这个递归函数的定义，并充分利用这个函数的返回值
    思考：如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

算法框架

1
2
3
4
5
def traverse(root: Optional[TreeNode]):
    # root 需要做什么？在这做。
    # 其他的不⽤ root 操⼼，抛给框架
    traverse(root.left)
    traverse(root.right)

力扣指南

树
题目 技巧 难度
✅94. 二叉树的中序遍历 框架递归 🌟
✅105. 从前序与中序遍历序列构造二叉树 前序遍历递归 🌟🌟
✅106. 从中序与后序遍历序列构造二叉树 🌟🌟
✅110. 平衡二叉树 递归 🌟
✅111. 二叉树的最小深度 递归 🌟
✅112. 路径总和 🌟
✅114. 二叉树展开为链表 分解法：通过子问题求解原问题 🌟
✅116. 填充每个节点的下一个右侧节点指针 借助中间节点 🌟🌟
✅117. 填充每个节点的下一个右侧节点指针 II 🌟🌟
✅124. 二叉树中的最大路径和 🌟🌟🌟
✅129. 求根节点到叶节点数字之和 🌟🌟
✅199. 二叉树的右视图 记录深度 跟右左遍历 🌟🌟
✅222. 完全二叉树的节点个数 🌟🌟
✅226. 翻转二叉树 🌟
✅236. 二叉树的最近公共祖先 🌟🌟
✅257. 二叉树的所有路径 🌟
✅297. 二叉树的序列化与反序列化 🌟🌟🌟
✅404. 左叶子之和 🌟
✅543. 二叉树的直径 最大路径为当前节点的左右子树最大高度和 🌟
✅652. 寻找重复的子树 中序遍历无法确定唯一的序列化字符串 🌟🌟
✅654. 最大二叉树 分解法构造 🌟🌟
✅889. 根据前序和后序遍历构造二叉树 🌟🌟

深度优先搜索——二叉搜索树专项

算法框架

二叉搜索树的题本质都是中序遍历或者利用其性质任意节点的值要⼤于等于左⼦树所有节点的值且要⼩于等于右边⼦树的所有节点的值。

1
2
3
4
5
6
7
def BST(root: Optional[TreeNode], target):
    if root.val == target:
        # 到⽬标，做点什么
    if root.val < target:
        BST(root.right, target)
    if root.val > target:
        BST(root.left, target)

力扣指南

二叉搜索树
题目 技巧 难度
✅98. 验证二叉搜索树 二叉搜索树中序遍历递增 🌟
✅99. 恢复二叉搜索树 交换节点的值而不是交换地址 🌟🌟
✅108. 将有序数组转换为二叉搜索树 二分转换 🌟
✅109. 有序链表转换二叉搜索树 左闭又开二分 🌟🌟
✅235. 二叉搜索树的最近公共祖先 🌟🌟
✅230. 二叉搜索树中第K小的元素 🌟🌟
✅449. 序列化和反序列化二叉搜索树 🌟🌟
✅450. 删除二叉搜索树中的节点 用右子树的最左节点替换跟节点 🌟🌟
✅530. 二叉搜索树的最小绝对差 🌟
✅538/1038. 把二叉搜索树转换为累加树 🌟🌟
✅700. 二叉搜索树中的搜索 利用递增性质二分 🌟
✅701. 二叉搜索树中的插入操作 找到要插入的位置定义节点 🌟🌟

广度优先搜索BFS

广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，它从起始顶点开始，逐层访问其相邻顶点，并记录每个顶点到起始顶点的距离。知识点：

  • 队列：BFS可以使用队列来实现。从起始顶点开始，将其放入队列中，然后循环执行以下操作：从队列中取出一个顶点，并访问其所有未访问的相邻顶点，将其放入队列中。直到队列为空，搜索结束。
  • 标记数组：为了避免重复访问已经访问过的顶点，BFS通常使用一个布尔类型的标记数组来记录每个顶点是否已经访问过。同时，为了记录每个顶点到起始顶点的距离，可以使用一个整型数组来存储每个顶点的距离。
  • 最短路径：BFS可以用来寻找无权图中起始顶点到其他顶点的最短路径。由于BFS是按层遍历的，因此可以保证从起始顶点到其他顶点的路径是最短的。
  • 连通性：BFS可以用来判断图的连通性。如果从起始顶点开始可以访问到所有其他顶点，则图是连通的；否则，图是不连通的。
  • 时间复杂度：BFS的时间复杂度取决于搜索过程中访问每个顶点的次数。对于稠密图，时间复杂度可以达到 $O(V^2)$，其中 $V$ 是顶点数。对于稀疏图，时间复杂度可以达到 $O(V+E)$，其中 E 是边数。
  • 空间复杂度：BFS 借助队列做到⼀次⼀步⻬头并进，是可以在不遍历完整棵树的条件下找到最短距离。BFS 算法队列中每次都会储存着⼆叉树⼀层的节点，最坏情况下空间复杂度是树的最底层节点的数量$O(N)$ 。
  • 应用：BFS通常用于解决一些搜索深度较大的问题，例如最短路径、最小生成树等。由于BFS按层遍历，因此可以保证从起始顶点到其他顶点的路径是最短的。
  • 变体：双向深度优先搜索（Bidirectional Depth-First Search，简称BDFS）可以在图或树中同时从起点和终点进行深度优先搜索，以期缩短搜索时间。
    • 原理：BDFS是双向搜索的一种变形，它通过同时从起点和终点进行深度优先搜索，以期在中间遇到一条路径，从而找到起点和终点之间的最短路径。在搜索过程中，需要记录起点和终点的已访问状态，直到两个搜索过程汇合，或者找到一条最短路径。
    • 特点：BDFS与DFS的搜索方式类似，只是在搜索过程中从起点和终点同时进行搜索。相比于BFS，BDFS的空间复杂度较低，但是对于图中较长路径，可能会超时或者陷入死循环。
    • 实现：BDFS的实现需要在搜索过程中记录起点和终点的已访问状态，并且需要判断是否有路径在中间汇合，或者找到一条最短路径。通常可以使用哈希表等数据结构来记录已访问状态，以及使用双向队列等数据结构来记录搜索过程中的路径。
    • 应用：BDFS可以用于寻找起点和终点之间的最短路径，例如在网络中找到两个节点之间的最短路径，或者在迷宫中找到从起点到终点的最短路径。另外，BDFS还可以用于图的遍历，例如在社交网络中寻找特定人群之间的联系，或者在语言处理中寻找两个词语之间的关系。

算法框架

原地修改的问题可以不使用visited标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List, Set, Tuple

class Node:
    def adj(self) -> List[Node]:
        pass

def BFS(start: Node, target: Node) -> int:
    q: List[Node] = []  # 核心数据结构
    visited: Set[Node] = set()  # 避免走回头路

    q.append(start)  # 将起点加入队列
    # visited.add(start)
    step: int = 0  # 记录扩散的步数

    while q:
        sz: int = len(q)
        # 将当前队列中的所有节点向四周扩散
        for i in range(sz):
            cur: Node = q.pop(0)
            # 划重点：这里判断是否到达终点
            if cur is target:
                return step
            # 将 cur 的相邻节点加入队列
            for x in cur.adj():
                if x not in visited:
                    q.append(x)
                    visited.add(x)
        # 划重点：更新步数在这里
        step += 1

力扣指南

广度优先搜索
题目 技巧 难度
✅111. 二叉树的最小深度 🌟
✅112. 路径总和 🌟
✅116. 填充每个节点的下一个右侧节点指针 🌟🌟
✅117. 填充每个节点的下一个右侧节点指针 II 🌟🌟
✅130. 被围绕的区域 从边界开始处理 🌟🌟
✅199. 二叉树的右视图 🌟🌟
✅200. 岛屿数量 🌟🌟
✅404. 左叶子之和 理解题意 🌟
✅417. 太平洋大西洋水流问题 双边界逆流而上 🌟🌟
✅529. 扫雷游戏 🌟🌟
✅752. 打开转盘锁 🌟🌟
✅773. 滑动谜题 🌟🌟🌟

回溯

回溯算法（Backtracking）是一种基于深度优先搜索的算法，它常用于在一组可能的解中搜索最优解。知识点：

  • 原理：回溯算法是通过试错的方式进行搜索，即从一个可能的解开始搜索，如果发现当前解不可行，则回溯到上一步进行尝试。在搜索过程中需要记录当前已尝试的路径，并在每一步进行判断，如果当前路径已经不能满足要求，则需要进行回溯。
  • 实现：回溯算法通常采用递归实现，每次搜索的参数包括当前路径、已访问状态等。在搜索过程中需要进行剪枝，即在当前路径已经不能满足要求时，提前结束搜索。在实现过程中需要注意，回溯算法通常可以通过状态重置来进行回溯，也可以通过栈等数据结构来记录搜索过程。
  • 应用：回溯算法常用于求解组合、排列、子集等问题，例如在数独游戏中求解解，在密码破解中找到密码、图的遍历、求解最优化问题等。
  • 优化：回溯算法的时间复杂度往往较高，常用的优化方法包括剪枝、记忆化搜索等。剪枝可以在搜索过程中排除不必要的搜索路径，从而减少搜索时间。记忆化搜索可以将已经搜索过的结果记录下来，避免重复搜索。另外，在实际应用中可以根据问题的特点进行算法的优化，例如在图的遍历中，可以使用启发式搜索等算法加速搜索过程。
  • 时间复杂度：$O(n!)$，不像动态规划存在重叠⼦问题可以优化，回溯算法是纯暴⼒穷举。
  • 技巧：回溯的撤销选择取决于是否对原始选择列表修改，如果修改则需要撤销操作。

算法框架

回溯问题实际上是⼀个决策树的遍历过程。需要思考 3 个问题：

  1. 路径：已经做出的选择
  2. 选择列表：当前可以做的选择
  3. 结束条件：到达决策树底层，⽆法再做选择的条件

排列题用used标记，组合题用start标记

1
2
3
4
5
6
7
8
9
result = []
def backtrack(path, choice_list):
    if target:
        result.add(path)
        return
    for choice in choice_list:
        # 做选择
        backtrack(path, choice_list)
        # 撤销选择

力扣指南

回溯
题目 技巧 难度
✅37. 解数独 有数字的剪枝；有可行解返回避免撤销 🌟🌟🌟
✅39. 组合总和 （元素无重可复选）每次复用start，使用整体剪纸避免无限递归 🌟🌟
✅40. 组合总和 II 剪枝掉超过target的 🌟🌟
✅46. 全排列 时间复杂度为O(n×n!) 🌟🌟
✅47. 全排列 II 🌟🌟
✅51. N 皇后 python字符串为不可变类型，修改只能对字符串重新赋值 🌟🌟🌟
✅52. N 皇后 II 🌟🌟🌟
✅77. 组合 同78 🌟🌟
✅78. 子集 （元素无重不可复选）用start标记起始点避免产生重复 🌟🌟
✅90. 子集 II 剪枝走过的路径 🌟🌟
✅216. 组合总和 III 秒了 🌟🌟
✅22. 括号生成 🌟🌟