Archive: 2020/11

【多维分桶】力扣939,963-最小面积矩形

用坐标值对点做哈希,用哈希值 用中点和长度对点对(线段,圆)做哈希,用哈希值分桶 多层 treemap 对点对做多属性分桶 STL无序关联容器自定义哈希函数 939. 最小面积矩形题目描述给定在 xy 平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形,就返回 0。 提示:12341 <= points.length

极角

摘要: 极角的原理和代码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文首先介绍一下极角的知识点,和代码模板,之后解决力扣的一道相关题目 1610。 向量的极角以原点 O 为极点,从 x 轴正方

摘要: 本文介绍计算几何中与点相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 本文我

力扣1219-黄金矿工

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

力扣1215-步进数

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

凸包的直径,旋转卡尺算法

摘要: 本文介绍计算几何中求凸包的直径的算法:旋转卡尺 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类

扫描线算法(Line-Sweep)

摘要: 扫描线算法:直线平移扫描 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们介绍一个计算几何中非常重要的算法:扫描线算法。除了计算几何之外,扫描线算法还可以解决很多区间的问题,力

多边形

摘要: 本文介绍计算几何中与多边形相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此

直线和线段

摘要: 本文介绍计算几何中与直线和线段相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。

【模板】二维向量的实现

摘要: 本文介绍一个向量的代码模板,解决几何问题是会频繁使用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文介绍一个向量的代码模板,解决几何问题是会频繁使用,在文章 几何题汇总 中,我们

凸包

摘要: 本文介绍计算几何中关于凸包的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基

几何题汇总

摘要: 本文总结了 leetcode 上的计算几何相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 文总结了力扣上 2000 题以内的关于计算几何的 15 道题。将场景相同的放到了一起,场景

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

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

用前缀和的思想快速计算区间上的指标(状态)

摘要: 用前缀和的思想表示前缀的某种状态 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过一个问题看一下如何用前缀和的思想表示前缀的一些其它指标,并且能够快速求出区间中的指标值。 对于数组

Trie单串多模式匹配,模式开头为统一特殊字符

$0 背景给定单串 s,n个模式串 p1, p2, …, pn。 其中 n 个模式串中,任意两个模式串都没有子串的关系,且都以一个特殊字符开头,模式的其它字符不会出现该特殊字符。 在 s 中找到所有匹配到这 n 个模式串的所有起始位置。 Trie用 n 个模式串建立一个 Trie。推进 i 的字符时,如果 s[i] 为特殊字符,则记录 j = i,并初始化 iter = root,之后尝试同时推进

力扣1409-查询带键的排列

第 184 场周赛 B 题 树状数组 $1 题目题目链接1409. 查询带键的排列 题目描述给你一个待查数组 queries ,数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i](从 i=0 到 i=queries.length-1): 一开始,排列 P=[1,2,3,…,m]。对于当前的 i ,请你找出待查项 queries[i] 在排列 P

【搜索难题】力扣1255-得分最高的单词集合

bitset 【STL】bitset 枚举集合 A 的子集 递推枚举: 位运算操作 递归枚举: 枚举 $1 题目题目链接1255. 得分最高的单词集合 题目描述你将会得到一份单词表 words,一个字母表 letters (可能会有重复字母),以及每个字母对应的得分情况表 score。 请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」:能够由 letters 里的字母拼写出的

【搜索难题】力扣1178-猜字谜

摘要: 一个 bitest 的应用题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 位运算操作 中,我们学习了位运算常见的操作。用位运算表示集合操作的时候,有时集合元素非常多,超出了

【频数分桶】力扣1224-最大相等频率

将 key 按频数分桶 维护频数桶的数据结构 链表, 动态数组 Ref1: 全(1)的数据结构 Ref2: LFUCache $1 题目题目链接1224. 最大相等频率 题目描述给出一个正整数数组 nums,请你帮忙从该数组中找出能满足下面要求的 最长 前缀,并返回其长度: 从前缀中 删除一个 元素后,使得所剩下的每个数字的出现次数相同。如果删除这个元素后没有剩余元素存在,仍可认为每个数

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

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

小数转分数

摘要: 小数转分数的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的小数转分数的问题。在编程中,除了整数以外,我们主要用的是小数,比如 float、double

力扣754-到达终点数字

推公式 $1 题目题目链接754. 到达终点数字 题目描述在一根无限长的数轴上,你站在0的位置。终点在target的位置。 每次你可以选择向左或向右移动。第 n 次移动(从 1 开始),可以走 n 步。 返回到达终点需要的最小移动次数。 注意:1target是在[-10^9, 10^9]范围中的非零整数。 样例 示例 1:输入: target = 3输出: 2解释:第一次移动,从 0 到 1

力扣768-最多能完成排序的块2

摘要: 双指针+哈希表、单调栈两种解法的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个一题多解的问题:力扣 768。第一种解法是单调栈,不过此前我们解决过的单调栈的问题,栈里保

01背包和完全背包题目汇总

摘要: 转换为 01 背包和完全背包的组合问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 组合数学的问题有时候可以转换为背包问题进而解决,而组合数学研究组合的存在性、计数性、优化性。也就是说背包

背包问题拾遗

摘要: 背包问题的遗留问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 01背包和完全背包 和 01背包和完全背包题目汇总 中我们分别了解了 01 背包和完全背包的算法原理、代码模板,以及

异或空间与异或基

摘要: 本文介绍异或基的算法原理和代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 高斯消元与线性方程组 中,我们学习了高斯消元的原理和代码模板。之后在高斯消元算法的基础上,我们在

线性空间与线性基

摘要: 本文介绍线性基的算法原理和代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 高斯消元与线性方程组 中,我们学习了高斯消元的原理和代码模板。有了高斯消元算法的基础,本文我们看

高斯消元与线性方程组

摘要: 本文介绍高斯消元的算法原理和代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍高斯消元的算法原理和代码模板。首先简要介绍一下线性方程组与高斯消元,以及高斯消元的特殊情况:无

后效性处理

$0 有后效性问题的背景阶段是 DP 的三要素之一,无后效性是 DP 算法有效的三个前提之一。参考 动态规划概念和基础线性DP 在一些问题中,抽象出状态维度,并设计出状态表示和状态转移方程后,可能会发现这样的状态设计不满足无后效性,部分状态之间互相转移,互相影响,构成了环形。 对于环形问题,有一种【可拆解的环形问题】,这样的问题是可以拆环后转化成线性结构上的 DP 问题,参考: 环形DP 。 而对

环形DP

环形结构上的DP 枚举断开位置,求解对应的线性结构上的DP 可拆解的环形DP问题 两次DP 288. 休息时间 213. 打家劫舍 II 1388. 3n 块披萨 复制一倍接在末尾 283. 多边形 变为 2N 长线性数组后用区间DP 289. 环路运输 变为 2N 长线性数组后用单调队列 918. 环形子数组的最大和 算法1: 复制一倍接在末尾 + 前缀和+单调队列 算

二次扫描与换根DP

摘要: 无根树上的树形DP,二次扫描与换根的处理方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 树形DP 中,我们简要介绍了树形 DP 的思想,以及列举了很多可以解决的问题。 在有的问题

树形背包

摘要: 树形背包 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一:树形背包。树形背包问题是 树形DP 和 分组背包 的应用。 树形背包问题 10. 有依赖

分组背包

摘要: 分组背包 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一:分组背包。分组背包是树形背包的基础,同时也是很多树形 DP 中状态转移的基本模型。 分组

单调队列优化多重背包

01背包和完全背包 多重背包 同余类状态 单调队列 单调队列优化DP $0 6. 多重背包问题 III有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。 120<N<=10000<V<=20000 $1 多

取模与分数取整

摘要: 分数取整与取模的关系,约瑟夫环问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的分数取整问题,以及分数取整与取模的关系。我们直接给出结论公式,然后详细拆解

组合数学拾遗2-偏序集,Dilworth定理

摘要: 偏序集、Dilworth定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前我们系统第学习了组合数学,详细内容见下面这些文章: 组合数学1-排列组合 组合数学2-母函数,递推关系 组合

组合数学拾遗1-集合,关系,函数

摘要: 集合、关系、函数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前我们系统第学习了组合数学,详细内容见下面这些文章: 组合数学1-排列组合 组合数学2-母函数,递推关系 组合数学3-特殊

双串线性DP,二维状态表示阶段

子序列匹配 392. 判断子序列 115. 不同的子序列 字符串模糊匹配 72. 编辑距离 712. 两个字符串的最小ASCII删除和 583. 两个字符串的删除操作 44. 通配符匹配 10. 正则表达式匹配 其它 97. 交错字符串 727. 最小窗口子序列 1458. 两个子序列的最大点积 $0 双串线性 DPdp[i][j]: i

最长公共子序列LCS

最长公共子序列 1143. 最长公共子序列 1035. 不相交的线 最长公共子串 718. 最长重复子数组 求具体的最长公共子序列 1092. 最短公共超序列 $1 最长公共子序列线性DP, 是动态规划中最常见的一个类型. 相比其它类型的DP, 它的状态设计变化非常多. 其中最经典的问题是 LIS, LCS, 它们分别代表了单串和双串的线性 DP 中最经典的状态表示和阶

棋盘DP

摘要: 棋盘 DP 的题目总结 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在很多时候,我们要在矩阵或者三角形上解决问题。比如给定一个矩阵,求最大的子矩阵和;又比如给定一个三角形,求从第一行走

单串线性DP-多维状态,在阶段的基础上附加维度

801. 使序列递增的最小交换次数 1187. 使数组严格递增 873. 最长的斐波那契子序列的长度 1027. 最长等差数列 813. 最大平均值和的分组 887. 鸡蛋掉落 256. 粉刷房子 265. 粉刷房子 II 975. 奇偶跳 403. 青蛙过河 1478. 安排邮筒 1230. 抛掷硬币 410. 分割数组的最大值 1473. 给房子涂色 III 446. 等差数列划分 II -

单串线性DP-一维状态表示阶段

32. 最长有效括号 413. 等差数列划分 91. 解码方法 338. 比特位计数 871. 最低加油次数 978. 最长湍流子数组 656. 金币路径 1024. 视频拼接 639. 解码方法 2 1578. 避免重复字母的最小删除成本 1218. 最长定差子序列 1235. 规划兼职工作 1043. 分隔数组以得到最大和 1416. 恢复数组 1055. 形成字符串的最短路径 368

最长上升子序列LIS

最长上升子序列 300. 最长上升子序列 DP (单串线性DP基本设计思路) (权值)树状数组优化DP 二分 (LIS 的最优解) 最长上升子序列的基础变形 最长上升子序列个数 673. 最长递增子序列的个数 最长上升子串 (最优解是滑动窗口) 674. 最长连续递增序列 俄罗斯套娃信封 (通过合适的排序转换为 LIS) 二维 354. 俄罗斯套娃信封问题

有向图上的DP(HMM前向后向计算)

$0 有向图上的 DP (HMM前向后向计算)一些表现形式为有向图 D 上的动态规划的问题,其阶段的推导是在 G 上进行的,如果本阶段在节点 u,u, v 之间没有有向边,则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段,而是作为阶段持有的状态。而阶段另有一个维度表示,并且具有例如长度,时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

无向图上的DP(CRF前向后向计算)

$0 无向图上的 DP (CRF前向后向计算)一些表现形式为无向图 G 上的动态规划的问题,其阶段的推导是在 G 上进行的,如果本阶段在节点 u,u, v 之间没有无向边,则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段,而是作为阶段持有的状态。而阶段另有一个维度表示,并且具有例如长度,时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

DAG判定

$0 场景给定有向图 D,判定 D 是否为 DAG 分析等价于判定有向图 D 中有没有环,因此判定 DAG 的算法与有向图判定环的算法相同。以下为复习。 有向图判定环的方法:有向图的环 BFS (拓扑排序) 如果拓扑排序后的排序列表长度小于 n,则无法拓扑排序,即 D 不是 DAG。 代码模板1234567891011121314151617181920212223242526class

并查集维护平面点的横纵坐标

并查集 带权并查集 并查集维护坐标点的办法 维护点编号 维护横纵坐标 求连通分量个数的一种方法:枚举点,将代表元插入哈希表,由哈希表执行去重 947. 移除最多的同行或同列石头 1267. 统计参与通信的服务器 $0 场景二维平面有 N 个点,每个点有一个坐标 (x, y),每两个点,如果横坐标相同或纵坐标相同,则视为在同一个连通分量中。问给定的 N 个点构成多少个连通分量。 (1) 并

并查集时光倒流

并查集 带权并查集 并查集时光倒流 803. 打砖块 $0 并查集时光倒流对于维护加边连通性的过程,并查集是非常有力的。 但是由于并查集合并后一般是不支持回滚的,仅仅可以通过开栈的方式实现撤销合并,即回滚一步。 因此如果要维护一个删边连通性的过程,并查集就无法完成了。但是有些问题可以逆向思维,即正向思维是 初态图 -> 删边 -> 终态图,逆向思维就变成了 终态图 -> 加边

【模板】双向链表+哈希映射,有序字典,LRU,LFU

背景 链表维护数据插入顺序 对链表节点的高效查询, 加索引的链表 【模板】无重哈希映射 【模板】双向链表 模板应用: 实现带更新顺序的字典 Python OrderedDict 模板 : 双向链表+哈希映射实现带更新顺序的字典 应用: 340. 至多包含 K 个不同字符的最长子串 模板应用: 实现带访问顺序的字典 146. LRU缓存机制 模板 : 双向链表+哈希映射实现带访问顺序的字典

【模板】双向链表的懒释放

惰性更新与懒释放 带懒释放的双向循环链表 懒释放 模板 测试: 1388. 3n 块披萨 $1 惰性更新与懒释放惰性更新是一种面对频繁操作时,先把操作记下来,等查询时再把记下的操作一次性都做掉,这在很多时候可以提高性能,因为有时候操作可以合并。参考 惰性更新 在基于数组的数据结构中对指定节点删除经常是一种比较重的操作,需要根据实际情况判断是否要用惰性更新的方式,即懒删除,具体的操作是