Tag: 搜索

2022力扣秋季赛第3题

摘要: 2022 力扣秋季赛第 3 题,比较复杂的多源 BFS 题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来研究一下力扣秋季赛第 3 题,也就是 LCP63,本题是在多源

力扣1162-多源BFS与多源最短路径

摘要: 力扣 1162,最基础的多源 BFS 题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 上个周日照例参加了力扣秋季赛的个人赛,在文章 2022力扣秋季赛个人赛战报 中记录的战报,并

人工智能一本书

摘要: 一本不错的《人工智能》书 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 搜索、知识、推理、规划、不确定性、学习、感知、行动 本文介绍人工智能的一本书,一般是计算机系大三的专业课。 作为计

博弈DP

摘要: 本文介绍概率 DP 的原理和例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 博弈是应用数学的一个分支,表示在多决策主体之间行为具有相互作用时,各主体根据所掌握信息以及对自身能力的认知,做

树的遍历题目汇总

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

【搜索难题】力扣489-扫地机器人

算法要点 回溯 参考: 隐式图搜索 DFS $1 题目题目链接489. 扫地机器人 题目描述房间(用格栅表示)中有一个扫地机器人。格栅中的每一个格子有空和障碍物两种可能。 扫地机器人提供4个API,可以向前进,向左转或者向右转。每次转弯90度。 当扫地机器人试图进入障碍物格子时,它的碰撞传感器会探测出障碍物,使它停留在原地。 请利用提供的4个API编写让机器人清理整个房间的算法。 12

力扣LCP34-二叉树染色

摘要: LCP34,树形DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们来看一个树形DP的何题,力扣 LCP34,本题是2021力扣杯春季赛团队赛第2题。算法要点如下: 树形DP 二叉

【搜索难题】力扣1258-近义词句子

大杂烩:DFS + 哈希表 + 并查集 + 排序 $1 题目题目链接1258. 近义词句子 题目描述给你一个近义词表 synonyms 和一个句子 text , synonyms 表中是一些近义词对 ,你可以将句子 text 中每个单词用它的近义词来替换。 请你找出所有用近义词替换后的句子,按 字典序排序 后返回。 提示:123450 <= synonyms.length &

模拟退火

摘要: 介绍模拟退火的原理并解决力扣 1515 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 梯度下降 和 爬山法 中我们学习了解决在目标函数上找最优解的两类算法,

爬山法

摘要: 介绍爬山法的原理并解决力扣 1515 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 梯度下降 中我们学习了梯度下降并解决了力扣 1515,本文介绍另一个在目

力扣1219-黄金矿工

摘要: 枚举所有起点的搜索题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个搜索题,也是常见的在二维迷宫上按要求进行游走的问题。本题与其他常见问题不同的是迷宫中每个点作为起点都可能是

力扣1215-步进数

$1 题目题目链接1219. 黄金矿工 题目描述如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 1,那么这个数就是一个「步进数」。 例如,321 是一个步进数,而 421 不是。 给你两个整数,low 和 high,请你找出在 [low, high] 范围内的所有步进数,并返回 排序后 的结果。 提示:10 <= low <= high <=

【搜索难题】力扣1197-进击的骑士

BFS Astar DFS + 记忆化 $1 题目题目链接1197. 进击的骑士 题目描述一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上,你的 骑士 驻扎在坐标为 [0, 0] 的方格里。 骑士的走法和中国象棋中的马相似,走 “日” 字:即先向左(或右)走 1 格,再向上(或下)走 2 格;或先向左(或右)走 2 格,再向上(或下)走 1 格。 每次移动

【搜索难题】力扣465-最优账单平衡

DFS 回溯 剪枝 $1 题目题目链接465. 最优账单平衡 题目描述一群朋友在度假期间会相互借钱。比如说,小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易,表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学(0, 1, 2 为人的标号),上述交易可以

优先级队列BFS

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

【搜索难题】力扣1439-有序矩阵中的第k个最小数组和

摘要: 一个比较难得搜索题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个搜索题,这是力扣第 187 场周赛 D 题。首先本题可以抽象成 TopK 问题,于是基于堆的算法可以

【搜索难题】力扣1240-铺瓷砖

基础搜索 最优性剪枝 搜索顺序 $1 题目题目链接1240. 铺瓷砖 题目描述你是一位施工队的工长,根据设计师的要求准备为一套设计风格独特的房子进行室内装修。 房子的客厅大小为 n x m,为保持极简的风格,需要使用尽可能少的 正方形 瓷砖来铺盖地面。 假设正方形瓷砖的规格不限,边长都是整数。 请你帮设计师计算一下,最少需要用到多少块方形瓷砖? 提示:121 <= n <

【搜索难题】力扣411-最短特异单词缩写

判定 t 是否为 s 的缩写: 320. 列举单词的全部缩写 双指针 枚举所有缩写: 408. 有效单词缩写 DFS 状态压缩维护子集型枚举 最优性剪枝 $1 题目题目链接411. 最短特异单词缩写 题目描述字符串 “word” 包含以下这些缩写形式: [“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1

【搜索难题】力扣956-最高的广告牌

可行性剪枝 + 最优性剪枝 记忆化搜索 $1 题目题目链接题目描述你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。 你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。 返回广告牌的最大可能安装高度。如果没法安装广告牌,请返回 0。 提示:1230 <&

最小生成树2

摘要: 最小生成树的一些衍生问题,比较难。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最小生成树方案数 题目: P4208 最小生成树计数算法: Kruskal题解参考: 力扣1489-找

k短路

K 短路 178. 第K短路 问题给定一张N个点(编号1,2…N),M条边的有向图,求从起点S到终点T的第K短路的长度,路径允许重复经过点或边。 注意: 每条最短路中至少要包含一条边。 数据格式 第一行包含两个整数N和M。接下来M行,每行包含三个整数A,B和L,表示点A与点B之间存在有向边,且边长为L。最后一行包含三个整数S,T和K,分别表示起点S,终点T和第K短路。 12341 <&

滑动谜题和八数码

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

基于 Floyd 搜索有向图的所有最小环

搜索有向图最小环长度并返回一个最小环 无向图的环 有向图的环 Floyd 搜索有向图所有的最小环 应用:854. 相似度为 K 的字符串 注: 最小环的问题也可以用 dijkstra 求解 $1 求有向图最小环长度并返回一个最小环有向图的环的基本概念参考:有向图的环 无向图 Floyd 求最小环的过程参考 无向图的环,有向图的情况类似。 考虑 Floyd 的过程: 在最外层 k 在迭代过

【搜索难题】力扣854-相似度为K的字符串

有向图的环 建图 Ref: 官解 一个有重边和自环的图,按照规则改变内部的边,使得所有的边都是自环 规则:当某个位置的字符不相等时,需要一步交换,这步交换涉及到图中两条边的改动 长为 l 的环可以用 l - 1 次按照规则对边的修改得到 l 个自环(Ref: 置换群中的一个 l 循环 $(1,2,…,l)$ 可以用 l - 1 次对换变为 $(1),(2),(3),…,(l)$) 将图分解为多个

双向搜索

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

单词矩阵

【搜索难题】力扣425-单词方块 数据结构维护状态转移时所需的查询需求 剪枝手段: 剪枝 $1 题目题目链接面试题 17.25. 单词矩阵 题目描述给定一份单词的清单,设计一个算法,创建由字母组成的面积最大的矩形,其中每一行组成一个单词(自左向右),每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现,但要求所有行等长,所有列等高。 如果有多个面积最大的矩形,输出任意一个均可。一

【搜索难题】力扣679-24点游戏

摘要: 最经典的 24 点判定问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,1024 快到了,各公司的程序员的活动也都出来了,力扣也不例外,出了一个参与感还挺强的活动。不过活动说明可

【搜索难题】力扣425-单词方块

DFS 数据结构维护状态转移 $1 题目题目链接425. 单词方块 题目描述给定一个单词集合 (没有重复),找出其中所有的 单词方块 。 一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k < max(行数, 列数)) 来看都是相同的字符串。 例如,单词序列 [“ball”,”area”,”lead”,”lady”] 形成了一个单词方块,因为每个单词从水

【搜索难题】力扣282-给表达式添加运算符

复杂的状态和转移 用类似单调栈的逻辑维护表达式符号和值 $1 题目题目链接282. 给表达式添加运算符 题目描述给定一个仅包含数字 0-9 的字符串和一个目标值,在数字之间添加二元运算符(不是一元)+、- 或 * ,返回所有能够得到目标值的表达式。 样例 示例 1:输入: num = “123”, target = 6输出: [“1+2+3”, “123”] 示例 2:输入: num = “

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 一旦选错了分支,就可能在不包含答案的

力扣1091-Astar,IDAstar

本题我们看一个 常规BFS, 无权图最短路模型, Ref BFS Astar, Ref Astar IDAstar, Ref IDAstar c++ 二维动态数组的创建和初始化 $1 题目 1091. 二进制矩阵中的最短路径 给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。 二进制矩阵中的 畅通路径 是一条从 左上角 单

【搜索难题】力扣1263-推箱子

摘要: 搜索难题,推箱子问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个很有挑战性的搜索问题,算法的框架是以 BFS 为核心的最短路径。但是有两个难点: 在推 BFS 的过程中,

双端队列BFS

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

Astar

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

【搜索难题】力扣675-BFS常数优化,Astar,Hadlock算法

BFS 中的常数优化办法 基本BFS12中文版 TLE英文版 1712ms 勉强过 优化1:将 forest[i][j] 值加进 Point 字段,而不在 cmp 中持有 forest 矩阵121944ms英文版 1628 ms 优化2:将 Point 的 x, y 变成 pos (x * m + y)121760ms英文版 1392ms 优化3:将 visited 的索引从 x, y 变成 p

minimax

极小化极大问题描述和定义 极小化极大问题分类 极小化极大解法 minimax算法 minimax 算法优化: $\alpha-\beta$ 剪枝 题目 minimax 843. 猜猜这个单词 minimax + 数学推导 292. Nim 游戏 博弈DP: minimax + DP/记忆化搜索 294. 翻转游戏 II minimax + 记忆化搜索 SG定理 464.

【搜索难题】力扣913-猫和老鼠

摘要: 本文详细拆解 leetcode 913-猫和老鼠,主要涉及对抗搜索与minimax、记忆化搜索、染色 BFS 等算法。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天分享一个对抗搜索的问

【搜索难题】力扣126-两次搜索,搜索路径

搜索过程记录路径的方法 两次搜索 双向 BFS 优化: 枚举点找边改成枚举边找点 $1 题目题目链接126.单词接龙 II 题目描述给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 1234

【搜索难题】力扣127-双向BFS

双向 BFS: 稠密图收益极大 BFS 的时间复杂度和优化 $1 题目题目链接127 单词接龙 题目描述给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:12345如果不存在这样的转换序列,返回 0。所有单词

【搜索难题】力扣1036-逃离大迷宫

摘要: 本文详细拆解 leetcode 1036-逃离大迷宫,有带步数上限的 BFS 和二维离散化两种方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们看一个迷宫上的问题,迷宫是非常大的一

【搜索难题】力扣778-优先级队列BFS

摘要: 一个搜索题,可以用优先级队列 BFS 或者值域二分解决 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个搜索题。有两个解法,一个是值域二分+DFS、另一个是优先级队列 BFS,都

DFS序,欧拉序,dfn序

DFS序,欧拉序,dfn序的定义和性质 经典问题 $1 DFS序,欧拉序,dfn序的定义和性质(1) DFS 序定义DFS 过程中对于某节点进入这个节点的子树和离开子树的顺序 性质 满足每个节点都会在dfs序上出现恰好两次 任意子树的 dfs 序都是连续的 记节点 x 在 dfs 序中的两次出现的位置为 L[x], R[x],则区间 [L[x], R[x]] 就是以 x 为根的子树的 d

力扣272-BST前去后继,dfn序列的滑动窗口

二叉查找树的中序遍历和前驱后继 DFS序,欧拉序,dfn序 deque 实现 dfn 序上的滑动窗口 BST 上的查找 + BST 前驱后继 $1 题目题目链接272. 最接近的二叉搜索树值 II 题目描述给定一个不为空的二叉搜索树和一个目标值 target,请在该二叉搜索树中找到最接近目标值 target 的 k 个值。 注意: 给定的目标值 target 是一个浮点数 你可以默认 k 值

有向图的环

有向图判定环 207. 课程表 DFS BFS(拓扑排序) 维护环的长度 最小环 经过特定点的最小环 有向图判定环207. 课程表 dfs在无向图判定环时,找到一个点,它不是 prev 点而又在此前遍历过,则形成环 有向图:以前遍历过并不代表形成环,办法是标记当前搜索路径,当回溯后,相应点要从标记中去掉。 123visited[i] = 0 未考查过visited[i] &

无向图的环

无向图判定环 DFS 染色 BFS 染色 并查集 拓扑排序 返回一条在环上的边/判定具体的边是否在环上 684. 冗余连接 维护环的长度 d[u] := u 到源点 start 的距离 / d[i][j] := i 到 j 的距离 1559. 二维网格图中探测环 无向带权图最小环问题:344. 观光之旅 其它 环的计数 返回所有简单环 对环做缩点 $1 无向图判定环(模板)

无向图的双连通分量

无向双连通图的定义 点双连通图 边双连通图 双连通分量 DCC 点双连通分量 v-DCC 边双连通分量 e-DCC 双向连通图的判定定理(充要条件) 双向连通图算法(Tarjan) e-DCC 求法 e-DCC 缩点 v-DCC 求法 v-DCC 缩点 $1 无向双连通图的定义对于无向连通图: 若不存在割点,则称其为点双连通图 若不存在桥,则称其为边双连通图 $2 双连通分量

tarjan算法

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。 Tarjan 算法基于无向图的 DFS,可以在 $O(N + E)$ 求出无向图的割点和桥,进一步可以求出无向图的双连通分量。 Tarjan 算法涉及时间戳,搜索树,以及追溯值的概念。 节点 node 的时间戳是指在 DFS 中,按照每个节点第一次被访问的顺序给 N 个节点做标记,记为 ord[node] 或者 dfn

无向图的连通分量

连通分量的图论阐释:图论1-基本概念 无向图的连通分量算法 DFS BFS 并查集(可以处理动态加边以及多次查询) 最大连通分量 695. 岛屿的最大面积 BFS 处理无向图连通分量 连通分量个数 200. 岛屿数量 并查集处理无向图连通分量 枚举连通分量 1202. 交换字符串中的元素 DFS 处理无向图连通分量 $1 无向图的连通分量算法DFSRef: DFS BFSRe