力扣刷题笔记 #10 搜索&剪枝
本文最后更新于:2023年3月18日 晚上
本文包含「搜索&剪枝」类型题中的:搜索回溯、优化剪枝、A* 搜索、启发式搜索等。持续更新中。
题目描述:
方法1:
方法2:
方法3:
坑点:
搜索回溯
暴力搜索 + 回溯,常见于「返回所有可能组合、方案、排列」题目,由于要得到所有可能,就必须暴力搜索,最多加上一定的优化剪枝。
回溯算法建立在 DFS 基础之上的,但不同的是在搜索过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置。
1 |
|
17. 电话号码的字母组合 (M)
题目描述:给定一个仅包含数字 2-9
的字符串,返回所有它能表示的九键字母组合。答案可以按任意顺序返回。
方法1:DFS 回溯,递归时用参数 $now$ 表示遍历到第几个数字;当 $now=n$ 时递归结束,加入答案数组。时间复杂度 $O(3^n)$,空间复杂度为递归栈的深度 $O(n)$。
方法2:BFS + 队列,每遍历到一个数字,就把队列中所有元素依次弹出,尾部加上不同字母后再压回队列。最后整个队列存放的就是答案。
22. 括号生成 (M)
题目描述:数字 n
代表目标字符串中合法括号的对数,生成所有可能的并且合法的括号组合字符串。
方法1:DFS 回溯,定义用一个 $cur$ 全局字符串,每次 DFS 时如果 $左括号数<n$,则在末尾添加一个 (
继续 DFS;如果 $右括号数<左括号数$,则在末尾添加一个 )
继续 DFS,当 $cur.size()=2n$ 时结束。
时刻保持 $右括号数 \leqslant 左括号数 \leqslant n$,则能够保证左括号先放置,则序列一定合法。
方法2:递归调用自身,递归 f(n-1)
得到对数 $n-1$ 的答案,并在每一个位置插入 ()
,去重后得到答案。
最终答案包含元素个数可以证明是第 $n$ 个卡特兰数 $\frac{1}{n+1}C^{n}_{2n}$,渐进于 $\frac{4^n}{n\sqrt{n}}$。而在回溯过程中,每个字符串需要 $O(n)$ 的时间插入新的括号,并 $O(1)$ 移动到新数组,所以总时间复杂度为 $O($$
\frac{4^n}{\sqrt{n}})$。而总共的递归层数为 $n$,每层都需要一个与答案数组同样数量级的临时数组,所以总空间复杂度也为 $O($$
\frac{4^n}{\sqrt{n}})$。
方法3:记忆化 DFS,答案序列的第一个字符一定是 (
,与之对应的 )
可能出现在右侧任何一个位置,构成 (A)B
。枚举 )
的位置 $2i+1$,则 A
就是 f(i)
,B
就是 f(n-i-1)
,记忆化存储每个结果,遍历拼接。
39. 组合总和 (M)
题目描述:给定一个无重复整数数组,和一个目标整数,找出数组中所有和为目标数的元素组合,同一个数字可以无限次重复选中,如果至少一个数字的被选数量不同,则两种组合是不同的。
方法1:DFS 回溯,用一个临时序列记录。递归时记录当前距离目标的差值和当前可选的数字起点,每次递归可以选择跳过当前数并将起点向前移动,也可以选择当前数且不移动起点,递归回溯后要将当前数移出临时序列。当起点遍历完时递归结束,当差值为零时得到组合。
方法2:DFS + 剪枝,先将数组从小到大排序,则当一个数字选完可能会溢出时,其后面的数字也不会再选,提前结束。
46. 全排列 (M)
题目描述:给定一个无重复整数数组,返回其所有可能的全排列,可以按任意顺序返回。
方法1:使用「31. 下一个排列」中的方法,每次都「贪心」找出下降点,时间复杂度 $O(n\times n!)$。
方法2:DFS 回溯,用一个临时序列记录,由于不按顺序,每次可从剩余数中放入一个数继续递归,递归回溯后要将当前数移出临时序列。时间复杂度 $O(n\times n!)$。
记录剩余数的方法有很多:
- 枚举下一个数,同时比对其是否出现在临时序列(无重复的好处);
- 用一个 $vis$ 数组记录临时序列中的数,作为参数传递,进一步地,可以用状态压缩;
- 使用一个分割点,左侧的数作为已确定的,右侧的数是将要访问的,每次从右侧 swap 一个数到分割点的位置,继续递归,递归回溯后将其 swap 回原位。
47. 全排列 II (M)
题目描述:给定一个有重复整数数组,返回其所有不重复的全排列,可以按任意顺序返回。
方法1:DFS 回溯,用一个临时序列记录,每次从剩余数中放入一个数继续递归,但是还需要判断相同数不能多次放置在当前位置。先排序将相同数放到一起,再用以下条件判断:
1 |
|
坑点:本题不能用上一题记录剩余数的方法 1,因为有重复;不能用方法 3,因为 swap 会打乱右侧数的顺序,使相同数不再放到一起。
78. 子集 (M)
题目描述:给定一个整数数组,数组中的元素互不相同 。返回该数组所有可能的子集(幂集)。
方法1:枚举,每个数有两种选择,总共有 $2^n$ 个子集,用二进制表示每个子集,则范围是 $[0, 2^n-1]$。枚举每个数字并生成对应的子集,时间复杂度 $O(n \cdot 2^n)$。
方法2:DFS 回溯,用一个临时序列记录,每次将 $now$ 指向的数「放入或不放入」后继续递归,递归回溯后要将放入的数移出临时序列。时间复杂度 $O(n \cdot 2^n)$。
方法3:线性 DP,$dp[i]$ 表示前 $i$ 个数的子集,初始 $dp[0]$ 为空集,每遍历到一个数就将前面的所有子集拼接上这个数,然后放入 $ans$。时间复杂度 $O(n \cdot 2^n)$。
优化剪枝
有的搜索问题涉及排列组合、卡特兰数等内容,暴力复杂度达到 $O(n!)$ 或 $O(k^n)$,必须使用优化、剪枝技巧。二者有一定的相似性。
所谓优化,就是降低单轮判断的复杂度,常用的优化技巧有:
- 记忆化,通过记录出现过的子状态,来快速判断当前状态的有效性;
- 辅助数组,以空间换时间,通常记录影响当前局面的历史信息;
- 编排分支顺序,先解决相对简单的子问题,使其他尚未解决的问题得到简化;
- 状态压缩,在小范围数据中使用,加快多维数组的访问效率、或减少辅助数组的空间占用。
所谓剪枝,就是提早退出某些搜索分支,常用的剪枝技巧有:
- 记忆化,对于出现过的子状态,标记 $vis$,防止多次访问;
- 可行性判断,根据题意提前退出不可能的分支(无法转向目标状态),避免无用的搜索;
- 最优性判断,每次搜索前判断当前解是否可能超过当前最优解,避免无用的搜索。
51. N 皇后 (H)
题目描述:国际象中,皇后可以攻击与之处在同一行、同一列、同一斜线上的棋子。将 $N$ 个皇后放在 $N\times N$ 的棋盘上,使其彼此之间不能相互攻击,返回所有解决方案。
方法1:暴力,按行搜索,第一行有 $N$ 种选择,第二行有 $N-1$ 种选择,以此类推。对于每个选择,逐个判断和之前放置过的皇后是否冲突,如果不冲突则搜索下一行。时间复杂度 $O(N\times N!)$。
方法2:暴力 + 辅助数组,使用额外的三个数组或哈希集合标记该列、主对角线、副对角线有无皇后,每次可以 $O(1)$ 判断冲突,时间复杂度 $O(N!)$,空间复杂度 $O(N)$。
对角线可以通过存行下标与列下标之差、行下标与列下标之和来表示,注意数组下标不能是负数,需要偏移 $N$,但是哈希集合不需要。
方法3:暴力 + 辅助数组 + 状态压缩,用三个整数的二进制位实现标志,每次先三个数进行或运算,得到 0 的位置就是可以放置的位置,时间复杂度 $O(N!)$,空间复杂度 $O(1)$(不考虑递归的空间占用)。
二进制位的标志 0 表示的是「该位可以放置」,而不是方法 2 中的「列、主对角线、副对角线」,因此在搜索时,下一行的应为
dfs(n, row+1, col|pos, (ld|pos)<<1, (rd|pos)>>1);
,最后两个参数表示两条对角线带来的影响会左移、右移一位。求 pos 需要用到位运算技巧
n & (-n)
和n & (n-1)
。
301. 删除无效的括号 (H)
题目描述:给定一个由括号和字母组成的字符串,删除最小数量的无效括号,使得字符串有效。返回所有可能的结果。
方法1:DFS 回溯,合法的方案左右括号数量相等,记左括号为 $+1$,右括号为 $-1$,最终得分必然为 $0$。DFS 正向遍历字符串,考虑每个元素是否放入子串,当遍历结束时,判断最终得分是否为 $0$,如果合法,则考虑将其加入集合去重。由于要求删除最小数量,剩余的字符串应该越长越好,因此维护一个 $maxlen$,仅当子串长度大于等于 $maxlen$ 时将其放入,并且只保留长度等于 $maxlen$ 的结果。时间复杂度 $O(n\cdot 2^n)$。
方法2:分数剪枝,在 DFS 传入参数 $score$,则根据 $score$ 的取值范围可以进行剪枝,提前排除不可能的子串。
在搜索过程中,两种情况可以提前剪枝:
- 得分为负数,即在子串前缀中右括号数量大于左括号,此时不可能是合法方案。
- 得分超过上限,这里的上限指的是
min(左括号的数量, 右括号的数量)
,上限只有在「合法左括号先全部出现在左边,右边全是右括号」时才出现。因此当子串前缀中出现大量左括号时,不可能是合法方案。于是,我们可以得到分数的限制范围 $[0, limit]$,$limit$ 可以预处理。
方法3:预处理 $maxlen$ 剪枝,最终目标串的长度可以提前确定为 $n-l-r$,$l$ 为失配左括号数,$r$ 为失配右括号数。正向遍历到左括号时 $l++$,遍历到右括号时 $l—$,如果 $l$ 为零,则 $r++$ 表示右括号失配。