LeetCode 搜索算法指南DFS、BFS、双向搜索与状态空间实战解析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文是 leetcode 题解仓库中《搜索篇上》的完整技术指南聚焦算法面试中占比极高的搜索类问题。你将系统掌握把题目映射为状态空间图、用 DFS 或 BFS 遍历状态图、通过 visited/距离表记录并维护状态的完整解题框架并深入理解迭代加深、双向搜索、双端队列等进阶技巧最终通过两道 LeetCode 真题1755. 最接近目标值的子序列和、126. 单词接龙 II把理论落地为可运行的 Python 代码。一、搜索的本质在有限状态空间中穷举搜索一般指在有限的状态空间中枚举通过穷尽所有可能来找到符合条件的解或解的个数。根据搜索方式的不同搜索算法可以分为 DFS、BFS、A* 算法等本文即仓库 thinkings/search.en.md 与中文版 thinkings/search.md只介绍 DFS 和 BFS以及发生在 DFS 上的一种技巧——回溯回溯专题。搜索问题覆盖面非常广泛在算法题中占据很高的比例。搜索专题中的子专题还有很多大家熟知的 BFS、DFS 只是其中特别基础的内容除此之外还有状态记录与维护、剪枝、连通分量、拓扑排序等。另外即使只考虑 DFS 和 BFS 两种基本算法也有双向搜索、DFS 的前中后序、迭代加深等花样。需要强调的是搜索其实在二叉树部分已经做了介绍这里的搜索是进一步的泛化。数据结构不再局限于数组、链表或树而是扩展到了二维数组、多叉树、图等。核心仍然一样只不过数据结构发生了变化。1.1 搜索的核心是什么搜索题目的本质是将题目中的状态映射为图中的点将状态间的联系映射为图中的边。根据题目信息构建状态空间然后对状态空间进行遍历遍历过程需要记录和维护状态并通过剪枝和数据结构等提高搜索效率。状态空间的数据结构不同会导致算法不同比如对数组搜索和对树、图搜索就不太一样。再次强调这里讲的数组、树和图是状态空间的逻辑结构而不是题目给的数据结构。例如题目给了一个数组让你求数组的子集虽然题目给的是线性的数组数据结构实际上我们是在对树这种非线性数据结构进行搜索——因为这道题对应的状态空间是非线性的。对于搜索问题核心关注的信息树的深度、图的 DFS 序、图中两点间的距离等指标都是完成高级算法必不可少的而这些指标可以通过一些经典算法来实现这也是为什么要先学好基础的数据结构与算法。另外由于其他数据结构都可以看作图的特例研究透图的基本思想就很容易扩展到树等其他数据结构上。1.2 状态空间解题的出发点结论先行状态空间其实就是一个图结构图中的节点表示状态图中的边表示状态之间的联系这种联系就是题目给出的各种关系。以求一个数组的子集为例状态空间实际上就是数组的各种组合一种可行的划分方式为长度为 1 的子集长度为 2 的子集……长度为 n 的子集其中 n 为数组长度如何确定上面所有的子集一种可行方案是采取类似分治的方式逐一确定先确定某一种子集的第一个数是什么再确定第二个数是什么……如何确定暴力枚举所有可能就可以了——这就是搜索问题的核心其他都是辅助。以长度为 3 的数组为例第一个数可能是数组中任意一项枚举 3 种情况第二个数可以是除了已被选择的数之外的任意一个数枚举 2 种情况。据此可以画出决策树——一些搜索算法就是基于这个朴素思想本质就是模拟这个决策树。记住两点即可状态空间就是图构建状态空间就是构建图如何构建当然是根据题目描述搜索算法只是对状态空间进行遍历的方式如何构建状态图才是关键。二、DFS深度优先遍历DFS 的概念来自图论但搜索中的 DFS 与图论中的 DFS 有些区别搜索中的 DFS 一般指通过递归函数实现暴力枚举不使用递归也可以用栈实现本质类似。首先将题目的状态空间映射到一张图——状态就是图中的节点状态间的联系就是图中的边——那么 DFS 就是在这张图上进行深度优先的遍历。本质上对图进行遍历会生成一棵搜索树。为了避免重复访问需要记录已经访问过的节点这是所有搜索算法共有的后续不再赘述。如果你是在树上遍历树是简单无环图不会有环自然不需要为了避免环的产生而记录已访问节点。仓库 thinkings/DFS.md 对该算法流程与模板有更详尽的展开可对照阅读。2.1 算法流程首先将根节点放入stack中从 stack 中取出第一个节点并检验它是否为目标。如果找到目标则结束搜寻并回传结果否则将它某一个尚未检验过的直接子节点加入 stack 中重复步骤 2如果不存在未检测过的直接子节点将上一级节点加入 stack 中重复步骤 2重复步骤 4若 stack 为空表示整张图都检查过了——亦即图中没有欲搜寻的目标结束搜寻并回传找不到目标。这里的 stack 可以理解为自实现的栈也可以理解为调用栈递归时由系统维护。2.2 算法模板const visited {} function dfs(i) { if (满足特定条件) { // 返回结果 or 退出搜索空间 } visited[i] true // 将当前状态标为已搜索 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } }2.3 常用技巧一前序遍历与后序遍历DFS 常见的形式有前序和后序二者的使用场景截然不同。如果搜索过程中当前点的结果需要依赖其他节点大多数情况都会有依赖那么遍历顺序就变得重要当前节点需要依赖其子节点的计算信息 → 使用后序遍历自底向上递推当前节点需要依赖其父节点的信息 → 使用先序遍历自顶向下递归。例如计算树的深度递推公式为 $f(x) f(y) 1$f(x) 表示节点 x 的深度x 是 y 的子节点base case 是根节点深度为 1通过 base case 可递推求出任意节点深度——显然用先序遍历自顶向下统计更简单直接。再如计算树的子节点个数递推公式为 $f(x) \sum_{i0}^{n}{f(a_i)}$$a_i$ 为 x 的子节点base case 是叶子节点 $f(x) 1$——可以利用后序遍历自底向上完成统计。2.4 常用技巧二迭代加深迭代加深本质上是一种可行性剪枝关于剪枝回溯专题有更多介绍。所谓迭代加深指的是在递归树比较深的时候通过设定递归深度阈值超过阈值就退出主动减少递归深度的优化手段。这种算法成立的前提是题目中告诉我们答案不超过 xxx这样可以将 xxx 作为递归深度阈值不仅不会错过正确解还能在极端情况下有效减少不必要的运算。具体地可以使用自顶向下的方式记录递归树的层次和计算树深度的方法一样然后在主逻辑前增加当前层次是否超过阈值的判断MAX_LEVEL 20 def dfs(root, level): if level MAX_LEVEL: return # 主逻辑 dfs(root, 0)这种技巧在实际使用中并不常见不过在某些时候能发挥意想不到的作用。2.5 常用技巧三双向搜索DFS 版有时候问题规模很大直接搜索会超时。此时可以考虑从起点搜索到问题规模的一半将此过程中产生的状态存起来接下来目标转化为在存储的中间状态中寻找满足条件的状态进而达到降低时间复杂度的效果。该算法本质上是将位于指数位的常数项挪动到了系数位——这是一种常见的双向搜索可称为 DFS 的双向搜索目的是与后文 BFS 的双向搜索区分。2.5.1 例题1755. 最接近目标值的子序列和题目地址https://leetcode-cn.com/problems/closest-subsequence-sum/题目描述给你一个整数数组 nums 和一个目标值 goal 。 你需要从 nums 中选出一个子序列使子序列元素总和最接近 goal 。也就是说如果子序列元素和为 sum 你需要 最小化绝对差 abs(sum - goal) 。 返回 abs(sum - goal) 可能的 最小值 。 注意数组的子序列是通过移除原始数组中的某些元素可能全部或无而形成的数组。 示例 1 输入nums [5,-7,3,5], goal 6 输出0 解释选择整个数组作为选出的子序列元素和为 6 。 子序列和与目标值相等所以绝对差为 0 。 示例 2 输入nums [7,-9,15,-2], goal -5 输出1 解释选出子序列 [7,-9,-2] 元素和为 -4 。 绝对差为 abs(-4 - (-5)) abs(1) 1 是可能的最小值。 示例 3 输入nums [1,2,3], goal -7 输出7 提示 1 nums.length 40 -10^7 nums[i] 10^7 -10^9 goal 10^9思路从数据范围可以看出这道题大概率是 $O(2^m)$ 时间复杂度的解法其中 m 是 nums.length 的一半。一般如果题目数组长度限制为小于等于 20那么大概率是 $O(2^n)$ 的解法——而这里nums.length 40且 40 折半恰好是 2040 这个数字本身就是折半搜索meet in the middle的强信号。回到题目可以用一个二进制位表示原数组 nums 的一个子集这样一个长度为 $2^n$ 的数组就可以描述 nums 的所有子集这就是状态压缩一般题目数据范围 20 都应该想到。接下来使用动态规划求出所有子集和令 dp[i] 表示选择情况如 i 所示的和。nums 的子集有 $2^n$ 个即每个数都有选择和不选择两种情况用一个二进制数表示这种选择情况0 表示选择、1 表示不选择一个位数足够的数可以表示一种可能的选择情况枚举数组的每一项对于每一项都考虑将其加入选择转移方程为dp[(1 i) j] dp[j] A[i]其中 j 为 i 的子集i 和 j 的二进制表示的是 nums 的选择情况。动态规划求子集和def combine_sum(A): n len(A) dp [0] * (1 n) for i in range(n): for j in range(1 i): dp[(1 i) j] dp[j] A[i] # 将 i 加入选择 return dp接下来将 nums 平分为两部分分别计算子集和n len(nums) c1 combine_sum(nums[: n // 2]) c2 combine_sum(nums[n // 2 :])其中 c1 是前半部分数组的子集和c2 是后半部分的子集和。问题转化为在两个数组 c1 和 c2 中找两个数其和最接近 goal——这是一个非常经典的双指针问题逻辑类似两数之和只不过两数之和是一个数组挑两个数这里是两个数组分别挑一个数。只需一个指针指向一个数组的头另一个指针指向另一个数组的尾def combine_closest(c1, c2): # 先排序以便使用双指针 c1.sort() c2.sort() ans float(inf) i, j 0, len(c2) - 1 while i len(c1) and j 0: _sum c1[i] c2[j] ans min(ans, abs(_sum - goal)) if _sum goal: j - 1 elif _sum goal: i 1 else: return 0 return ans代码Python3class Solution: def minAbsDifference(self, nums: List[int], goal: int) - int: def combine_sum(A): n len(A) dp [0] * (1 n) for i in range(n): for j in range(1 i): dp[(1 i) j] dp[j] A[i] return dp def combine_closest(c1, c2): c1.sort() c2.sort() ans float(inf) i, j 0, len(c2) - 1 while i len(c1) and j 0: _sum c1[i] c2[j] ans min(ans, abs(_sum - goal)) if _sum goal: j - 1 elif _sum goal: i 1 else: return 0 return ans n len(nums) return combine_closest(combine_sum(nums[: n // 2]), combine_sum(nums[n // 2 :]))复杂度分析令 n 为数组长度m 为 $\frac{n}{2}$时间复杂度$O(m \times 2^m)$空间复杂度$O(2^m)$相关题目推荐最接近的三数之和最后一块石头的重量 II最接近目标价格的甜点成本这道题与双向搜索的关系如果直接暴力搜索枚举所有子集和再找与 goal 最接近的思路简单直接但会超时于是搜索到一半将状态存起来对应本题存到 dp 数组再转化为两个 dp 数组的运算。这一思路在仓库另一道题 problems/805.split-array-with-same-average.md 中有类似应用——该题同样通过双向搜索把 $O(2^n)$ 降到 $O(2^{n/2})$ 从而通过全部测试用例。三、BFS广度优先遍历BFS 也是图论中的一种算法。不同于 DFSBFS 采用横向搜索的方式从初始状态一层层展开直到目标状态在数据结构上通常采用队列。具体地不断从队头取出状态然后将此状态对应的决策产生的所有新状态推入队尾重复以上过程直至队列为空。这里有两个关键点此状态对应的决策这句话指的就是状态空间中的图的边。不管是 DFS 还是 BFS边都是确定的——也就是说决策是一样的不同的是进行决策的方向所有新状态推入队尾由于直接将状态空间中当前点的所有邻边放到队尾由队列先进先出的特性当前点的邻边访问完成之前不会继续向外扩展——这一点可以和 DFS 对比理解。最简单的 BFS 每次扩展新状态就增加一步通过一步步逼近答案等价于在一个权值为 1 的图上进行 BFS。由于队列的单调性和二值性第一次取出目标状态时就是最少的步数。基于这个特性BFS 适合求解一些最少操作的题目。前面 DFS 部分提到不管是什么搜索都需要记录和维护状态其中一个就是节点访问状态以防止环的产生。在 BFS 中我们常常用它求最短距离。值得注意的是有时候会使用一个哈希表 dist 来记录从源点到图中其他点的距离这个 dist 也可以充当防止环产生的功能——因为第一次到达一个点后再次到达此点的距离一定比第一次到达大利用这一点就可以知道是否是第一次访问。3.1 算法流程首先将根节点放入队列中从队列中取出第一个节点并检验它是否为目标如果找到目标则结束搜索并回传结果否则将它所有尚未检验过的直接子节点加入队列中若队列为空表示整张图都检查过了——亦即图中没有欲搜索的目标结束搜索并回传找不到目标重复步骤 2。3.2 算法模板const visited {} function bfs() { let q new Queue() q.push(初始状态) while(q.length) { let i q.pop() if (visited[i]) continue for (i的可抵达状态j) { if (j 合法) { q.push(j) } } } // 找到所有合法解 }3.3 常用技巧一双向搜索BFS 版当终点可以逆向搜索的时候可以尝试双向 BFS。更本质一点如果你构建的状态空间的边是双向的那么就可以使用双向 BFS。和 DFS 的双向搜索思想类似只需使用两个队列分别存储从起点和终点扩展的节点起点集与终点集。当起点和终点在某一时刻交汇说明找到了一个从起点到终点的路径其路径长度就是两个队列扩展的路径长度和。3.3.1 例题126. 单词接龙 II题目地址https://leetcode-cn.com/problems/word-ladder-ii/题目描述按字典 wordList 完成从单词 beginWord 到单词 endWord 转化一个表示此过程的转换序列是形式上像 beginWord - s1 - s2 - ... - sk 这样的单词序列并满足 - 每对相邻的单词之间仅有单个字母不同。 - 转换过程中的每个单词 si1 i k必须是字典 wordList 中的单词。注意beginWord 不必是字典 wordList 中的单词。 - sk endWord 给你两个单词 beginWord 和 endWord 以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 如果不存在这样的转换序列返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。 示例 1 输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog] 输出[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]] 解释存在 2 种最短的转换序列 hit - hot - dot - dog - cog hit - hot - lot - log - cog 示例 2 输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log] 输出[] 解释endWord cog 不在字典 wordList 中所以不存在符合要求的转换序列。 提示 1 beginWord.length 7 endWord.length beginWord.length 1 wordList.length 5000 wordList[i].length beginWord.length beginWord、endWord 和 wordList[i] 由小写英文字母组成 beginWord ! endWord wordList 中的所有单词互不相同思路这道题就是我们日常玩的成语接龙游戏从 beginWord 开始接龙到 endWord找到最短的接龙方式如果有多个则全部返回。与成语接龙字首接字尾不同这种接龙要求下一个单词和上一个单词仅有一个字母不同。对问题进行抽象构建一个大小为 n 的图图中每一个点表示一个单词目标是找到一条从节点 beginWord 到节点 endWord 的最短路径——这是一个不折不扣的图上 BFS 题目。套用 BFS 模板可以轻松解决唯一需要注意的是如何构建图更进一步说就是如何构建边。由转换规则每对相邻的单词之间仅有单个字母不同可知如果两个单词仅有一个字母不同说明两者之间有一条边。据此可以构建邻接表使用通配符*进行预处理空间换时间neighbors collections.defaultdict(list) for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word)构建好图之后BFS 剩下的就是明确起点和终点起点是 beginWord终点是 endWord。将 beginWord 入队不断在图上做 BFS直到第一次遇到 endWord。以下代码使用 cost 而非 visited 记录目的是展示多种写法下面的优化解法会使用 visited 记录class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: cost collections.defaultdict(lambda: float(inf)) cost[beginWord] 0 neighbors collections.defaultdict(list) ans [] for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word) q collections.deque([[beginWord]]) while q: path q.popleft() cur path[-1] if cur endWord: ans.append(path.copy()) else: for i in range(len(cur)): for neighbor in neighbors[cur[:i] * cur[i 1 :]]: if cost[cur] 1 cost[neighbor]: q.append(path [neighbor]) cost[neighbor] cost[cur] 1 return ans当终点可以逆向搜索的时候可以尝试双向 BFS。使用两个队列分别存储从起点和终点扩展的节点。为了判断两者是否交汇可以使用两个 hashSet 分别存储起点集和终点集当一个节点既出现在起点集又出现在终点集就说明出现了交汇。关于双向搜索快慢的四个问题原文观点整理为什么双向搜索更快刚开始时边比较少、队列中的数据也比较少而随着搜索进行搜索树越来越大、队列中的节点随之增多很多情况下这种增长是指数级别的双向搜索可以将指数的常系数移动到多项式系数从而显著缩小搜索树什么情况下更快相比于单向搜索双向搜索通常更快但也有例外——假如从起点到终点只有一条路径那么无论单向还是双向搜索结果都一样为什么不都用双向搜索做题中建议尽量使用单向搜索因为写起来更简单并且大多数情况可以通过所有测试用例除非预估到可能超时或提交后发现超时再尝试使用双向搜索有哪些使用条件正如前面所说终点可以逆向搜索的时候可以尝试双向 BFS更本质一点是——如果构建的状态空间的边是双向的就可以使用双向 BFS。为了节省代码量以及空间消耗下面的代码没有使用队列而是直接使用哈希表代替队列。这种做法可行的关键仍然是前面提到的队列的二值性和单调性由于新一轮出队列前队列中的权值都是相同的因此从左到右、从右到左甚至任意顺序遍历都无所谓很多题都无所谓所以使用哈希表代替队列是可行的。这道题的具体算法定义两个队列 q1 和 q2分别从起点和终点进行搜索构建邻接表每次都尝试从 q1 和 q2 中较小的一端进行扩展这样可以达到剪枝的效果如果 q1 和 q2 交汇了则将两者的路径拼接起来即可。代码Python3双向 BFS 优化版class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: list) - list: # 剪枝 1 if endWord not in wordList: return [] ans [] visited set() q1, q2 {beginWord: [[beginWord]]}, {endWord: [[endWord]]} steps 0 # 预处理空间换时间 neighbors collections.defaultdict(list) for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word) while q1: # 剪枝 2从较少状态的一端扩展 if len(q1) len(q2): q1, q2 q2, q1 nxt collections.defaultdict(list) for _ in range(len(q1)): word, paths q1.popitem() visited.add(word) for i in range(len(word)): for neighbor in neighbors[word[:i] * word[i 1 :]]: if neighbor in q2: # 从 beginWord 扩展过来的 if paths[0][0] beginWord: ans [path1 path2[::-1] for path1 in paths for path2 in q2[neighbor]] # 从 endWord 扩展过来的 else: ans [path2 path1[::-1] for path1 in paths for path2 in q2[neighbor]] if neighbor in wordList and neighbor not in visited: nxt[neighbor] [path [neighbor] for path in paths] steps 1 # 剪枝 3 if ans and steps 2 len(ans[0]): break q1 nxt return ans本题传递的四个知识点队列不一定非得是常规的队列也可以是哈希表等不过某些情况必须是双端队列见下文双向 BFS 只适合双向图也就是说从终点也能往前推双向 BFS 从较少状态的一端进行扩展可以起到剪枝的效果visited 和 dist/cost 都可以起到记录节点访问情况、防止环产生的作用不过 dist 的作用更多相应空间占用也更大。3.4 常用技巧二双端队列上面提到 BFS 本质可以看作在一个边权值为 1 的图上遍历。可以做一个简单扩展如果图中边权值不全是 1而是 0 和 1 呢这时就用到双端队列。双端队列可以在头部和尾部同时进行插入和删除而普通队列仅允许在头部删除、在尾部插入。使用双端队列时每次取出一个状态如果能够无代价地进行转移就将其直接放在队头否则放在队尾。由前面讲的队列的单调性和二值性不难得出算法的正确性。这也是很多语言提供的内置数据结构是双端队列而不是队列的原因之一。思考如果图对应的权值不是 0 和 1而是任意正整数呢前面提到是不是不需要队列就用哈希表、哈希集合存就行了——这里揭晓不可以因为哈希表无法处理权值为 0 的情况无代价转移需要插入队头以保持层序二值性。四、DFS 和 BFS 的对比简单来说不管是 DFS 还是 BFS都是对题目对应的状态空间进行搜索。二者区别在于DFS在分叉点会任选一条深入进入遇到终点则返回再次返回到分叉口后尝试下一个选择。基于此可以在路径上记录一些数据由此衍生出很多有趣的东西如前序/后序、回溯等BFS在分叉点会选择搜索的路径各尝试一次。使用队列存储待处理元素时队列中最多只会有两层的元素且满足单调性即相同层的元素在一起——基于这个特点有很多有趣的优化如最短距离、双向 BFS、双端队列等。五、总结搜索篇的解题思路搜索篇上的解题思路可归纳为三步根据题目信息构建状态空间图——节点表示状态边表示状态间的联系即题目给出的各种关系对图进行遍历——用 BFS 或 DFS记录和维护状态——比如用 visited 维护访问情况用队列和栈维护状态的决策方向等。需要大家注意的核心点DFS 通常都是有递推关系的而递归关系就是图的边根据递归关系可以选择使用前序遍历自顶向下如计算树深度或者后序遍历自底向上如计算子树大小BFS 由于其单调性适合求解最短距离问题双向搜索的本质是将复杂度的常数项从一个影响较大的位置比如指数位移到了影响较小的位置比如系数位。本文篇幅所限回溯与剪枝以及常用指标与统计方法树的深度与子树大小、图的 DFS 序、图的拓扑序、图的连通分量将在后续章节展开可先结合仓库 thinkings/backtrack.md、thinkings/DFS.md 与 thinkings/graph.md 提前研读。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考