1.什么是搜索搜索是⼀种枚举通过穷举所有的情况来找到最优解或者统计合法解的个数。因此搜索有时候 也叫作暴搜。搜索⼀般分为深度优先搜索(DFS)与宽度优先搜索(BFS)2.深度优先遍历vs深度优先搜索宽度优先遍历vs宽度优先搜索遍历是形式搜索是⽬的。 不过在⼀般情况下我们不会去纠结概念的差异两者可以等同。3.回溯与剪枝• 回溯当在搜索的过程中遇到⾛不通或者⾛到底的情况时就回头。•剪枝剪掉在搜索过程中剪掉重复出现或者不是最优解的分⽀。1. 深度优先搜索-DFS1.1 递归型枚举与回溯剪枝初识1. 画决策树2. 根据决策树写递归。注意组合和排列在哪些地方可以剪枝。1.1.2 组合型枚举设计递归函数• 重复子问题当前这⼀位应该放哪个数上去。因为这是⼀个「组合」问题不涉及排列所以我们当前位置开始放的数应该是「上次决策的数的下⼀位」。• 实现⽅式参考代码和注释结合「决策树」⼀起看会很清晰。1.1.3 枚举型排列设计递归函数• 重复⼦问题考虑这⼀位要放上什么数。因为是「排列」问题所以我们直接从1开始枚举要放的数。• 剪枝在这⼀条路径中我们「不能选择之前已经选择过的数」。• 实现⽅式参考代码和注释结合「决策树」⼀起看会很清晰。1.2 DFSDFS时走完一条路径时记得回溯。数据量较小的题目可以使用暴力搜索解题。1.2.2 飞机降落枚举所有⻜机的「全排列」判断是否存在⼀种排列使的全部的⻜机都能安全降落。剪枝• 当前路径⾥⾯只能选没有选过的⻜机• 如果这架⻜机不能正常降落剪掉• 如果已经找到⼀种安全降落的⽅式停⽌枚举可以通过「递归的返回值」判断是否搜索成功。1.2.3 八皇后巧用方向向量枚举状态记录枚举策略应该是比较容易想到的这道题的难点在于如何判断「在这⼀列放上这个皇后之后是否冲 突」。当我们一行一行放的时候「⾏是不会产⽣冲突的」。产⽣冲突的只有「列」「主对角线」以及「副对角线」。我们可以⽤三个数组分别标记• col[i] true 表⽰第i ⾏放置了⼀个皇后• dig1[j − i n] true 表⽰y x b这条「主对角线」上放置了⼀个皇后(b为下标)• dig2[j i] true 表⽰y −x b这条「副对⻆线」上放置了⼀个皇后。1.2.4 数独数据量较小——暴力枚举每个3*3的大格看作一个整体做状态表示用于剪枝。1.3 剪枝与优化剪枝形象得看就是剪掉搜索树的分⽀从⽽减⼩搜索树的规模排除掉搜索树中没有必要的分 ⽀优化时间复杂度。在深度优先遍历中有⼏种常⻅的剪枝⽅法1.排除等效冗余如果在搜索过程中通过某⼀个节点往下的若⼲分⽀中存在最终结果等效的分⽀那么就只需要搜 索其中⼀条分⽀。2.可⾏性剪枝如果在搜索过程中发现有⼀条分⽀是⽆论如何都拿不到最终解此时就可以放弃这个分⽀转⽽搜 索其它的分⽀。3.最优性剪枝在最优化的问题中如果在搜索过程中发现某⼀个分⽀已经超过当前已经搜索过的最优解那么这 个分⽀往后的搜索必定不会拿到最优解。此时应该停⽌搜索转⽽搜索其它情况。4.优化搜索顺序在有些搜索问题中搜索顺序是不影响最终结果的此时搜索顺序的不同会影响搜索树的规模。 因此应当先选择⼀个搜索分⽀规模较⼩的搜索顺序快速拿到⼀个最优解之后⽤最优性剪枝剪掉 别的分⽀。5.记忆化搜索记录每⼀个状态的搜索结果当下⼀次搜索到这个状态时直接找到之前记录过的搜索结果。 记忆化搜索有时也叫动态规划。1.3.1 数的划分剪枝策略可行性• 当我们填了cnt个坑时此时总和是sum 如果后续坑位全部都填上最⼩值都会超过n 。说明我们之前填的数太⼤了导致后⾯怎么填都会超过n 直接剪掉。注意剪枝位置的不同⽽导致搜索树的不同(剪枝的位置影响效率)• 如果在进⼊递归之前剪枝我们不会进⼊⾮法的递归函数中• 但是如果在进⼊递归之后剪枝我们就会多进⼊很多不合法的递归函数中。1.3.2 ⼩猫爬⼭搜索策略优化搜索顺序依次处理每⼀只猫对于每⼀只猫我们都有两种处理⽅式• 要么把这只猫放在已经租好的缆⻋上• 要么重新租⼀个缆⻋把这只猫放上去。优先放在已有缆车上。• 最优性剪枝在搜索过程中我们⽤全局变量记录已经搜索出来的最⼩缆⻋数量。如果当前搜索过程中已经⽤的缆⻋数量⼤于全局记录的最⼩缆⻋数量那么这个分⽀⼀定不会得到最优解剪掉。•优化枚举顺序⼀从⼤到⼩安排每⼀只猫◦重量较⼤的猫能够快速把缆⻋填满较快得到⼀个最⼩值◦通过这个最⼩值能够提前把分⽀较⼤的情况提前剪掉。•优化枚举策略⼆先考虑把⼩猫放在已有的缆⻋上然后考虑重新租⼀辆⻋ ◦ 因为如果反着来我们会先把缆⻋较⼤的情况枚举出来这样就起不到剪枝的效果了。1.4 记忆化搜索记忆化搜索也是⼀种剪枝策略。通过⼀个备忘录记录第⼀次搜索到的结果当下⼀次搜索到这个状态时直接在备忘录⾥⾯找 结果。记忆化搜索有时也叫动态规划。通过把「递归展开图」画出来发现在递归过程中会遇到⼤量「⼀模⼀样」的问题时就可以使用记忆化搜索。1.4.2 天下第⼀当有多组数据且每组数据处理方式一样时就可以使用记忆化搜索1.4.3 滑雪因为出现相同⼦问题所以可以⽤ 来解决。⼜因为在搜索的过程中会遇到⼀模⼀样的问题因此 可以把递归改成记忆化搜索的⽅式。2. 宽度优先搜索-BFS宽度优先搜索的过程中每次都会从当前点向外扩展⼀层所以会具有⼀个最短路的特性。因此宽 搜不仅能搜到所有的状态而且还能找出起始状态距离某个状态的最⼩步数。但是前提条件是每次扩展的代价都是1或者都是相同的数。宽搜常常被用于解决边权为 1的最短路问题。宽度优先搜索可用于树、图、矩阵2.1 BFS2.1.1 马的遍历题目要求到达某个点最少要走几步因此可以用bfs解决。因为当权值为1时 每次都是扩展 距离起点等距离的⼀层天然具有最短性。那就从起点开始⼀层⼀层的往外搜用⼀个 dist 数组记录最短距离。2.1.2kotori和迷宫经典的bfs问题。从迷宫的起点位置逐层开始搜索每搜到⼀个点就标记⼀下最短距离。当把整个迷宫全部搜索完毕之后扫描整个标记数组求出出口的数量以及最短的距离。2.1.4 八数码难题因为要求的是最短步数因此可以⽤ bfs解决。• 从起始状态开始每次扩展上下左右交换后的状态• 在搜索的过程中第⼀次遇到最终状态就返回最短步数。 第一次遇到一定是最短的宽搜的性质1. 如何记录⼀个 3*3的棋盘 bfs可以用字符串。从上往下从左往右将棋盘内的数依次存到⼀个字符串⾥来标记棋盘的状态。2. 如何记录最短路 可以用 unordered_map string,int 来标记最短距离3. 如何通过⼀个字符串找到交换之后的字符串2.2多源BFS1.单源最短路问题vs多源最短路问题• 当问题中只存在⼀个起点时这时的最短路问题就是单源最短路问题。• 当问题中存在多个起点而不是单⼀起点时这时的最短路问题就是多源最短路问题。2. 多源BFS多源最短路问题的边权都为1时此时就可以⽤多源BFS来解决。3. 解决⽅式 把这些源点汇聚在⼀起当成⼀个超级源点。然后从这个超级源点开始处理最短路问题。落实 到代码上时1. 初始化的时候把所有的源点都加⼊到队列⾥⾯2. 然后正常执⾏bfs的逻辑即可。 也就是初始化的时候⽐普通的bfs多加⼊⼏个起点。2.2.1 矩阵距离正难则反• 如果针对某⼀个点直接去找最近的1 我们需要对所有的 0都来⼀次bfs 这个时间复杂度是 接受不了的。• 但是我们如果反着来想从 1开始向外扩展每遍历到⼀个 0就更新⼀下最短距离。这样仅需⼀ 次bfs就可以把所有点距离 的最短距离更新出来。正难则反是很重要的思想后续还有很多题可以⽤到这个思想。//多源bfs由于1的数量很多因此可以把所有的1看成⼀个超级源点从这个超级源点开始⼀层⼀层的向外 扩展。实现起来也很简单就是在初始化阶段把所有 的坐标加⼊到队列中然后正常 。2.2.2刺杀⼤使直接找答案显然是不现实的因为能⾛的路径实在是太多了如果全都枚举出来时间上吃不消。但是题⽬要求的是最⼤值最⼩化可以尝试⽤⼆分来优化枚举。设最终结果是 x会发现⼀个性质 二段性• 当规定搜索过程中的最⼤值⼤于等于 x时我们⼀定可以从第⼀⾏⾛到最后⼀⾏• 当规定搜索过程中的最⼤值⼩于 x时我们⼀定不能⾛到最后⼀⾏。 因此我们可以⼆分最终结果通过 bfs 或者 dfs 来判断是否能⾛到最后⼀⾏。2.3 01BFS01 BFS又称双端队列BFS。在最短路问题中边权值可能为1也可能为0。那么在BFS的过程中可以将边权为0扩展出来的点放到队首边权为1扩展出来的点放到队尾。这样就能保证像普通BFS⼀样整个队列队首到队尾权值单调不下降。当经过一条权值为0的路径的时候可以认为起点和终点两个点等价此时把拓展出的点放到队首就保持了整个队列单调不下降01bfs因为有权值为0的路径的存在第二次走到一个位置时可以进行松弛操作。2.3.2ThreeStates正难则反• 直接找出结果点是很⿇烦的需要枚举所有的点然后每个点都要来⼀次 bfs 这样是会超时的。• 可以依次从三个国家出发⽤bfs 计算出来到达所有点的最短距离。求出所有距离之后重新遍 历所有的点分情况求出到三个国家的最短距离。细节问题1. 因为每个国家可能有很多点并且国家的点与点之间不连通因此我们要⽤多源 求某个国家 到所有点的最短距离3. 计算某⼀个点到三个国家的最短距离时应该分情况讨论。设a,b,c 分别表⽰三个国家到该点的最短距离a. 如果该点是⼀个国家最短距离为b. 如果该点是⼀个荒地最短距离为 计算三次所以要减去两次。3. Floodfill 问题Floodfill 算法又称漫水填充像素法本质是在寻找具有相同性质的联通块。利用bfs将连通的块打上标记3.1 LakeCounting遍历整个矩阵当遇到⼀个没有标记过的⽔坑时• 计数• 然后⽤ bfs或者 dfs将整个湖全都标记⼀下。 整个矩阵遍历⼀遍就能得出湖的数量。3.2 填涂颜⾊正难则反直接找出被包围的0是很困难的因为很难确定当前搜索到的这个0是否是被包围的。但是我们如果从边缘的0开始搜索搜索到的0⼀定是没有被包围的。因此我们可以从边缘的 0开始搜索标记所有与边缘相连的联通块。那么没有被标记过的 0就是被包围的。⼩技巧• 我们可以把整个矩阵的外围包上⼀层 0这样只⽤从 [0,0]位置开始搜即可。不⽤遍历第⼀⾏第 ⼀列最后⼀⾏以及最后⼀列 1.什么是搜索搜索是⼀种枚举通过穷举所有的情况来找到最优解或者统计合法解的个数。因此搜索有时候 也叫作暴搜。搜索⼀般分为深度优先搜索(DFS)与宽度优先搜索(BFS)2.深度优先遍历vs深度优先搜索宽度优先遍历vs宽度优先搜索遍历是形式搜索是⽬的。 不过在⼀般情况下我们不会去纠结概念的差异两者可以等同。3.回溯与剪枝• 回溯当在搜索的过程中遇到⾛不通或者⾛到底的情况时就回头。•剪枝剪掉在搜索过程中剪掉重复出现或者不是最优解的分⽀。1. 深度优先搜索-DFS1.1 递归型枚举与回溯剪枝初识1. 画决策树2. 根据决策树写递归。注意组合和排列在哪些地方可以剪枝。1.1.2 组合型枚举设计递归函数• 重复子问题当前这⼀位应该放哪个数上去。因为这是⼀个「组合」问题不涉及排列所以我们当前位置开始放的数应该是「上次决策的数的下⼀位」。• 实现⽅式参考代码和注释结合「决策树」⼀起看会很清晰。1.1.3 枚举型排列设计递归函数• 重复⼦问题考虑这⼀位要放上什么数。因为是「排列」问题所以我们直接从1开始枚举要放的数。• 剪枝在这⼀条路径中我们「不能选择之前已经选择过的数」。• 实现⽅式参考代码和注释结合「决策树」⼀起看会很清晰。1.2 DFSDFS时走完一条路径时记得回溯。数据量较小的题目可以使用暴力搜索解题。1.2.2 飞机降落枚举所有⻜机的「全排列」判断是否存在⼀种排列使的全部的⻜机都能安全降落。剪枝• 当前路径⾥⾯只能选没有选过的⻜机• 如果这架⻜机不能正常降落剪掉• 如果已经找到⼀种安全降落的⽅式停⽌枚举可以通过「递归的返回值」判断是否搜索成功。1.2.3 八皇后巧用方向向量枚举状态记录枚举策略应该是比较容易想到的这道题的难点在于如何判断「在这⼀列放上这个皇后之后是否冲 突」。当我们一行一行放的时候「⾏是不会产⽣冲突的」。产⽣冲突的只有「列」「主对角线」以及「副对角线」。我们可以⽤三个数组分别标记• col[i] true 表⽰第i ⾏放置了⼀个皇后• dig1[j − i n] true 表⽰y x b这条「主对角线」上放置了⼀个皇后(b为下标)• dig2[j i] true 表⽰y −x b这条「副对⻆线」上放置了⼀个皇后。1.2.4 数独数据量较小——暴力枚举每个3*3的大格看作一个整体做状态表示用于剪枝。1.3 剪枝与优化剪枝形象得看就是剪掉搜索树的分⽀从⽽减⼩搜索树的规模排除掉搜索树中没有必要的分 ⽀优化时间复杂度。在深度优先遍历中有⼏种常⻅的剪枝⽅法1.排除等效冗余如果在搜索过程中通过某⼀个节点往下的若⼲分⽀中存在最终结果等效的分⽀那么就只需要搜 索其中⼀条分⽀。2.可⾏性剪枝如果在搜索过程中发现有⼀条分⽀是⽆论如何都拿不到最终解此时就可以放弃这个分⽀转⽽搜 索其它的分⽀。3.最优性剪枝在最优化的问题中如果在搜索过程中发现某⼀个分⽀已经超过当前已经搜索过的最优解那么这 个分⽀往后的搜索必定不会拿到最优解。此时应该停⽌搜索转⽽搜索其它情况。4.优化搜索顺序在有些搜索问题中搜索顺序是不影响最终结果的此时搜索顺序的不同会影响搜索树的规模。 因此应当先选择⼀个搜索分⽀规模较⼩的搜索顺序快速拿到⼀个最优解之后⽤最优性剪枝剪掉 别的分⽀。5.记忆化搜索记录每⼀个状态的搜索结果当下⼀次搜索到这个状态时直接找到之前记录过的搜索结果。 记忆化搜索有时也叫动态规划。1.3.1 数的划分剪枝策略可行性• 当我们填了cnt个坑时此时总和是sum 如果后续坑位全部都填上最⼩值都会超过n 。说明我们之前填的数太⼤了导致后⾯怎么填都会超过n 直接剪掉。注意剪枝位置的不同⽽导致搜索树的不同(剪枝的位置影响效率)• 如果在进⼊递归之前剪枝我们不会进⼊⾮法的递归函数中• 但是如果在进⼊递归之后剪枝我们就会多进⼊很多不合法的递归函数中。1.3.2 ⼩猫爬⼭搜索策略优化搜索顺序依次处理每⼀只猫对于每⼀只猫我们都有两种处理⽅式• 要么把这只猫放在已经租好的缆⻋上• 要么重新租⼀个缆⻋把这只猫放上去。优先放在已有缆车上。• 最优性剪枝在搜索过程中我们⽤全局变量记录已经搜索出来的最⼩缆⻋数量。如果当前搜索过程中已经⽤的缆⻋数量⼤于全局记录的最⼩缆⻋数量那么这个分⽀⼀定不会得到最优解剪掉。•优化枚举顺序⼀从⼤到⼩安排每⼀只猫◦重量较⼤的猫能够快速把缆⻋填满较快得到⼀个最⼩值◦通过这个最⼩值能够提前把分⽀较⼤的情况提前剪掉。•优化枚举策略⼆先考虑把⼩猫放在已有的缆⻋上然后考虑重新租⼀辆⻋ ◦ 因为如果反着来我们会先把缆⻋较⼤的情况枚举出来这样就起不到剪枝的效果了。1.4 记忆化搜索记忆化搜索也是⼀种剪枝策略。通过⼀个备忘录记录第⼀次搜索到的结果当下⼀次搜索到这个状态时直接在备忘录⾥⾯找 结果。记忆化搜索有时也叫动态规划。通过把「递归展开图」画出来发现在递归过程中会遇到⼤量「⼀模⼀样」的问题时就可以使用记忆化搜索。1.4.2 天下第⼀当有多组数据且每组数据处理方式一样时就可以使用记忆化搜索1.4.3 滑雪因为出现相同⼦问题所以可以⽤ 来解决。⼜因为在搜索的过程中会遇到⼀模⼀样的问题因此 可以把递归改成记忆化搜索的⽅式。2. 宽度优先搜索-BFS宽度优先搜索的过程中每次都会从当前点向外扩展⼀层所以会具有⼀个最短路的特性。因此宽 搜不仅能搜到所有的状态而且还能找出起始状态距离某个状态的最⼩步数。但是前提条件是每次扩展的代价都是1或者都是相同的数。宽搜常常被用于解决边权为 1的最短路问题。宽度优先搜索可用于树、图、矩阵2.1 BFS2.1.1 马的遍历题目要求到达某个点最少要走几步因此可以用bfs解决。因为当权值为1时 每次都是扩展 距离起点等距离的⼀层天然具有最短性。那就从起点开始⼀层⼀层的往外搜用⼀个 dist 数组记录最短距离。2.1.2kotori和迷宫经典的bfs问题。从迷宫的起点位置逐层开始搜索每搜到⼀个点就标记⼀下最短距离。当把整个迷宫全部搜索完毕之后扫描整个标记数组求出出口的数量以及最短的距离。2.1.4 八数码难题因为要求的是最短步数因此可以⽤ bfs解决。• 从起始状态开始每次扩展上下左右交换后的状态• 在搜索的过程中第⼀次遇到最终状态就返回最短步数。 第一次遇到一定是最短的宽搜的性质1. 如何记录⼀个 3*3的棋盘 bfs可以用字符串。从上往下从左往右将棋盘内的数依次存到⼀个字符串⾥来标记棋盘的状态。2. 如何记录最短路 可以用 unordered_map string,int 来标记最短距离3. 如何通过⼀个字符串找到交换之后的字符串2.2多源BFS1.单源最短路问题vs多源最短路问题• 当问题中只存在⼀个起点时这时的最短路问题就是单源最短路问题。• 当问题中存在多个起点而不是单⼀起点时这时的最短路问题就是多源最短路问题。2. 多源BFS多源最短路问题的边权都为1时此时就可以⽤多源BFS来解决。3. 解决⽅式 把这些源点汇聚在⼀起当成⼀个超级源点。然后从这个超级源点开始处理最短路问题。落实 到代码上时1. 初始化的时候把所有的源点都加⼊到队列⾥⾯2. 然后正常执⾏bfs的逻辑即可。 也就是初始化的时候⽐普通的bfs多加⼊⼏个起点。2.2.1 矩阵距离正难则反• 如果针对某⼀个点直接去找最近的1 我们需要对所有的 0都来⼀次bfs 这个时间复杂度是 接受不了的。• 但是我们如果反着来想从 1开始向外扩展每遍历到⼀个 0就更新⼀下最短距离。这样仅需⼀ 次bfs就可以把所有点距离 的最短距离更新出来。正难则反是很重要的思想后续还有很多题可以⽤到这个思想。//多源bfs由于1的数量很多因此可以把所有的1看成⼀个超级源点从这个超级源点开始⼀层⼀层的向外 扩展。实现起来也很简单就是在初始化阶段把所有 的坐标加⼊到队列中然后正常 。2.2.2刺杀⼤使直接找答案显然是不现实的因为能⾛的路径实在是太多了如果全都枚举出来时间上吃不消。但是题⽬要求的是最⼤值最⼩化可以尝试⽤⼆分来优化枚举。设最终结果是 x会发现⼀个性质 二段性• 当规定搜索过程中的最⼤值⼤于等于 x时我们⼀定可以从第⼀⾏⾛到最后⼀⾏• 当规定搜索过程中的最⼤值⼩于 x时我们⼀定不能⾛到最后⼀⾏。 因此我们可以⼆分最终结果通过 bfs 或者 dfs 来判断是否能⾛到最后⼀⾏。2.3 01BFS01 BFS又称双端队列BFS。在最短路问题中边权值可能为1也可能为0。那么在BFS的过程中可以将边权为0扩展出来的点放到队首边权为1扩展出来的点放到队尾。这样就能保证像普通BFS⼀样整个队列队首到队尾权值单调不下降。当经过一条权值为0的路径的时候可以认为起点和终点两个点等价此时把拓展出的点放到队首就保持了整个队列单调不下降01bfs因为有权值为0的路径的存在第二次走到一个位置时可以进行松弛操作。2.3.2ThreeStates正难则反• 直接找出结果点是很⿇烦的需要枚举所有的点然后每个点都要来⼀次 bfs 这样是会超时的。• 可以依次从三个国家出发⽤bfs 计算出来到达所有点的最短距离。求出所有距离之后重新遍 历所有的点分情况求出到三个国家的最短距离。细节问题1. 因为每个国家可能有很多点并且国家的点与点之间不连通因此我们要⽤多源 求某个国家 到所有点的最短距离3. 计算某⼀个点到三个国家的最短距离时应该分情况讨论。设a,b,c 分别表⽰三个国家到该点的最短距离a. 如果该点是⼀个国家最短距离为b. 如果该点是⼀个荒地最短距离为 计算三次所以要减去两次。3. Floodfill 问题Floodfill 算法又称漫水填充像素法本质是在寻找具有相同性质的联通块。利用bfs将连通的块打上标记3.1 LakeCounting遍历整个矩阵当遇到⼀个没有标记过的⽔坑时• 计数• 然后⽤ bfs或者 dfs将整个湖全都标记⼀下。 整个矩阵遍历⼀遍就能得出湖的数量。3.2 填涂颜⾊正难则反直接找出被包围的0是很困难的因为很难确定当前搜索到的这个0是否是被包围的。但是我们如果从边缘的0开始搜索搜索到的0⼀定是没有被包围的。因此我们可以从边缘的 0开始搜索标记所有与边缘相连的联通块。那么没有被标记过的 0就是被包围的。⼩技巧• 我们可以把整个矩阵的外围包上⼀层 0这样只⽤从 [0,0]位置开始搜即可。不⽤遍历第⼀⾏第 ⼀列最后⼀⾏以及最后⼀列 
算法精解与面试技巧)
