Category: 搜索

2021
算法搜索

树的遍历题目汇总

本文总结了力扣上 2000 题以内的关于树的遍历与搜索的 73 道题。将场景相同的放到了一起。 场景上主要涉及前序遍历、中序遍历、后续遍历、层序遍历、两次遍历、树上搜索、最近公共祖先。 算法上主要涉及DFS、BFS。这两个算法都是主流算法，非常重要，而且它们各自都有非常多的场景和题目，这两块后面会单独总结。 刷完这份题目列表，力扣上的树的遍历的问题可以说刷爆了。 之前也对树的 DFS 遍历、树的

2020
算法搜索

优先级队列BFS

摘要: 基于优先级队列的 BFS 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 带权图最短路径 中我们全面学习了带权图最短路径的算法，其中 BFS 是一类非常重要的算法。但是常规的 BFS

算法搜索

滑动谜题和八数码

数字华容道可行性: 108. 奇数码问题 数字华容道1: 773. 滑动谜题 数字华容道2: 179. 八数码 置换群理论判定数字华容道可行性 组合数学5-群论 DFS BFS Astar IDAstar 用康拓编码给排列的哈希做空间压缩 排列算法 $0 置换群理论判定可行性原理算法基于置换群的理论，Ref : 组合数学5-群论 涉及到奇置换，偶置换，循环，对换的概念 奇置换：一

算法搜索

双向搜索

双向搜索的思想 双向BFS 双向迭代加深 $1 双向搜索的思想在一些问题中，初态和终态都是确定的，并且从初态想终态搜索，并且两个方向的搜索是等效的，和从终态向初态搜索都可以覆盖整个搜索空间，相当于搜索路径可逆。此时可以采用双向搜索。 在搜索过程中对状态染色，一共有三种： 未访问过 属于初态搜索树 属于终态搜索树 当属于初态的搜索树和属于终态的搜索树在某个状态相遇了，则搜索到了答案，此时根

算法搜索

IDAstar

IDAstar 算法 迭代加深 Astar 估价函数 IDAstar算法 代码 题目 1091. 二进制矩阵中的最短路径 854. 相似度为 K 的字符串 773. 滑动谜题 / 179. 八数码 180. 排书 $1 IDAstar 算法Astar 回顾Ref: Astar Astar 是一个带有估价函数的优先级队列 BFS 算法。因此 Astar 有一个缺点就是要维护优先级队列

算法搜索

剪枝

影响搜索的时间效率的因素 搜索树的规模，影响时间复杂度 每个状态上记录，检索，更新的时间，影响常数 剪枝做的事情是减小搜索树的规模 常见手法： 优化搜索顺序 等效性剪枝 可行性剪枝 最优性剪枝 记忆化 $1 优化搜索顺序搜索树的各个层次，各个分支之间的顺序是不固定的，不同的搜索顺序会产生不同的搜索树形态。 搜索顺序$2 等效性剪枝如果能判定从搜索树的当前节点上沿着某几条不同分支到达的子树

算法搜索

迭代加深

迭代加深 DFS 回顾 迭代加深的思想 迭代加深的代码 迭代加深的适用性 题目 $1 迭代加深的思想和算法DFS 回顾DFS 的逻辑是每次选定一个分治，不断深入，直到达到递归边界才回溯。这种方法退域很多搜索问题非常有效，尤其是配合剪枝，记忆化等手段后很有威力。 但是 DFS 也有弱点：当每个节点的分支非常多，且问题的答案在比较浅的节点上的时候，DFS 一旦选错了分支，就可能在不包含答案的

算法搜索

双端队列BFS

摘要: 基于双端队列的 BFS 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 带权图最短路径 中我们全面学习了带权图最短路径的算法，其中 BFS 是一类非常重要的算法。但是常规的 BFS 只

算法搜索

Astar

dijkstra 回顾 Astar 思想 估价函数 例子 1091. 二进制矩阵中的最短路径 675. 为高尔夫比赛砍树 854. 相似度为 K 的字符串 773. 滑动谜题 / 179. 八数码 178. 第K短路 $1 Astar回顾优先级队列 BFS(dijkstra)维护一个优先级队列，不断从队列中去除当前代价最小的状态进行扩展，每个状态第一次从队列中取出的时候，就得到了从初始状态

算法搜索

搜索顺序

搜索问题中，搜索树的各个层次，各个分支之间的顺序是不定的。不同的搜索顺序会产生不同的搜索树形态。 改变搜索顺序使得尽早剪枝是搜索中的重要优化手段。例如在数独问题中，优先搜索能填的合法数字最少的位置就属于这种策略。 473. 火柴拼正方形在 DFS 之前先排序 sort(nums.begin(), nums.end(), greater<int>()); 使得较长的火柴先搜索。 1234

算法搜索

DFS

解决的问题 组合搜索和隐式图搜索 组合搜索,隐式图搜索 树搜索 树的DFS遍历 图搜索 无向图的连通分量 有向图的连通分量 无向图的环 有向图的环 二分图判定 无向图的桥 无向图的割点 无向图的双连通分量 tarjan算法 欧拉路径 DFS拓扑排序 还有很多… 图搜索的 DFS 模板(以遍历为例) 经常配合使的用方法 连通性(DFS基本模型) 1391. 检查网格中是否存在有

算法搜索

BFS

BFS 可解决的问题 组合搜索和隐式图搜索 组合搜索,隐式图搜索 树搜索 树的BFS遍历 图搜索 无权图最短路径 带权图最短路径 无向图的环 有向图的环 无向图的连通分量 二分图判定 拓扑排序 还有很多… 图搜索的 BFS 模板(无权图最短路径为例) 经常配合使用的方法 无权图最短路径(BFS基本模型) 1311. 获取你好友已观看的视频 909. 蛇梯棋 复杂状态表示和

算法搜索

组合搜索,隐式图搜索

组合搜索：在有限的搜索空间(也叫隐式图)内穷举搜索出可行答案或最优答案，本质上还是穷举。 组合经常用于各种隐式图搜索，一般既可以 DFS 也可以 BFS，哪种好没有定式，需要结合具体问题。 难点主要有两个： 第一个是搜索空间中的状态表示(隐式图的节点意义)和状态转移(隐式图的边意义)可以很复杂。陷入具体问题或业务问题中有时很难发现其中的状态和转移，进而找到合适的图表示来建模。 第二个是优化，组

算法搜索

树的BFS遍历

基础层序遍历: 102. 二叉树的层序遍历 队列 递归(不用队列方法1) 双指针(不用队列方法2) 429. N叉树的层序遍历 变种层序遍历 自底向上层序 107. 二叉树的层次遍历 II 锯齿形层序 103. 二叉树的锯齿形层次遍历 层平均值 637. 二叉树的层平均值 堂兄弟节点 993. 二叉树的堂兄弟节点 垂序遍历 314. 二叉树的垂直遍历

算法搜索

树的DFS遍历

前序遍历: 递归、迭代、Morris遍历 144. 二叉树的前序遍历 建树问题 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 889. 根据前序和后序遍历构造二叉树 1028. 从先序遍历还原二叉树 1008. 先序遍历构造二叉树 编码和序列化问题: 数据压缩 结构判断问题 100. 相同的树 572. 另一个树的子树 1367.

算法搜索

带压缩的额外状态的 BFS

摘要: 带压缩的额外状态的 BFS 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个比较难的 BFS 的问题。说的是我们在二维矩阵上走迷宫，其中除了常规的道路和墙，还有