Archive: 2020/10

对顶栈

$1 场景有一个光标,给出对光标的操作序列,维护操作结果,当操作有以下特性时,对顶栈可以很好地解决。 一次只移动一位 添加、删除均在光标操作 操作位置一定在光标左右 对顶栈实现12vector<int> st_l; // 左栈数据,光标在左栈栈顶vector<int> st_r; // 右栈数据 $2 题目1472. 设计浏览器历史记录问题你有一个只支持单个标签页的

加索引的链表

$0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一种自带索引的数据结构(索引结构)。即将数据项(key)插入进去之后,可以随时根据给定的 key,可以快速查到它所在节点的位置。 作为对比,数组,链表就没有这种根据 key 快速找到其所在节点的特性,数据项(key)插入进去之后,如果想给定 key 找到对应的节点,只能线性扫描去找。(栈,

【设计难题】力扣635-设计日志存储系统

基于 Trie 的日期索引设计 $1 题目题目描述你将获得多条日志,每条日志都有唯一的 id 和 timestamp ,timestamp 是形如 Year:Month:Day:Hour:Minute:Second 的字符串,2017:01:01:23:59:59 ,所有值域都是零填充的十进制数。 实现 LogSystem 类: LogSystem() 初始化 LogSystem 对象voi

【设计难题】力扣631-设计Excel求和公式

基于图论的设计 $1 题目题目链接631. 设计 Excel 求和公式 题目描述你的任务是实现 Excel 的求和功能,具体的操作如下: Excel(int H, char W): 这是一个构造函数,输入表明了 Excel 的高度和宽度。H 是一个正整数,范围从 1 到 26,代表高度。W 是一个字符,范围从 ‘A’ 到 ‘Z’,宽度等于从 ‘A’ 到 W 的字母个数。Excel 表格是一个

【设计难题】力扣1500-设计文件分享系统

$1 题目题目链接1500. 设计文件分享系统 题目描述我们需要使用一套文件分享系统来分享一个非常大的文件,该文件由 m 个从 1 到 m 编号的文件块组成。 当用户加入系统时,系统应为其注册一个独有的 ID。这个独有的 ID 应当被相应的用户使用一次,但是当用户离开系统时,其 ID 应可以被(后续新注册的用户)再次使用。 用户可以请求文件中的某个指定的文件块,系统应当返回拥有这个文件块的所有用户

后缀表达式建表达式树

问题 1628. 设计带解析函数的表达式树 给定一个算术表达式的后缀表示法的标记(token) postfix ,构造并返回该表达式对应的二叉表达式树。 后缀表示法是一种将操作数写在运算符之前的表示法。例如,表达式 4(5-(2+7)) 的后缀表示法表示为数组 postfix = [“4”,”5”,”7”,”2”,”+”,”-“,”“] 。 抽象类 Node 需要用于实现二叉表达式树。我们将通过

实数区间二分

摘要: 实数区间二分的场景与代码模板,经典题目 lc69 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二分 中,我们总结了二分的常见类型,其中主要是区间二分以及值域二分。 本文我们了解一下

三分查找

摘要: 三分的应用场景与代码模板,解决题目 1515、1095、852 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二分 中,我们总结了二分的常见类型,其中主要是区间二分以及值域二分。之后

base64编码的原理与实现

摘要: Base64 编码的原理、实现与应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们学习一下 Base64 编码的原理与实现,给出一个代码模板,并用代码模板解决力扣 535. Tin

双向Trie

Trie基础 trie 01Trie 双向Trie 场景及方案 实现 745. 前缀和后缀搜索 算法1:双向 Trie 算法2:前缀Trie + 后缀Trie $0 双向Trie场景一个 Trie 可以预处理一批单词的所有前缀,或者所有后缀。此后可以快速进行与前缀匹配或者后缀匹配有关的查询。 有时需求会更近一步:即做一些前缀和后缀均需要匹配的查询。例如问前缀为 profix 同时

18岁Cosplay皇上

摘要: 颐和园里的拍照项目 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings

随机队列

摘要: 本文介绍随机队列的原理和代码模板,以及 2 道 leetcode 相关题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 随机队列 增加删 key 的支持 380. 常数时间插入、删除和

优先级队列BFS

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

【多解法】力扣42-接雨水

摘要: 接雨水问题的各种解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个几年前就被网上研究透了的陈题:接雨水。不过从一题多解的角度,本题还是值得看一下的,几个算法都是非常主流的算法

【STL】复数

摘要: 本文介绍在 C++ STL 中,复数的使用方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍在 C++ STL 中,复数的使用方法。《C++标准库》 第2版,作者 Nicolai

【随机算法】洗牌

摘要: 基于抽取、交换、插入的洗牌算法 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前我们学习过很多随机算法,并且解决了很多力扣上的相关题目。但是洗牌这个随机算法中最常见的问题

【随机算法】蓄水池抽样

摘要: 蓄水池抽样入门 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【随机算法】蒙特卡洛 和 【随机算法】拒绝采样 中,我们了解了蒙特卡洛方法的基本思想,实现

【STL】随机数

摘要: 本文介绍在 C++ STL 中,如何使用随机数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍在 C++ STL 中,如何使用随机数,主要参考《C++标准库》 第2版,作者 Nico

【贪心难题】力扣1054-距离相等的条形码

摘要: 堆维护贪心算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个用堆维护贪心算法的例子。 $1 题目 1054. 距离相等的条形码 在一个仓库里,有一排条形码,其中第

【贪心难题】力扣1183-矩阵中1的最大数量

排序贪心 $1 题目题目链接1183. 矩阵中 1 的最大数量 题目描述现在有一个尺寸为 width * height 的矩阵 M,矩阵中的每个单元格的值不是 0 就是 1。 而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中,1 的数量不得超过 maxOnes。 请你设计一个算法,计算矩阵中最多可以有多少个 1。 提示:1231 <

【多解法】力扣1562-查找大小为M的最新分组

算法1: 区间合并 算法2: 并查集 算法3: 逆向思维 + 平衡树 算法4: 逆向思维 + 减治 算法5: 滑动窗口 + 单调队列 $1 题目题目链接1562. 查找大小为 M 的最新分组 题目描述给你一个数组 arr ,该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串,该字符串上的所有位最初都设置为 0 。 在从 1 到 n 的每个步骤 i 中(假设二进制字符串

贪心-限制操作方式的重排问题

1505. 最多 K 次交换相邻数位后得到的最小整数 1536. 排布二进制网格的最少交换次数 1460. 通过翻转子数组使两个数组相等 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串 字典序最小 均分纸牌 升序 贪心问题 操作: 与头元素对换 操作: 与头元素或尾元素对换 动态规划 801. 使序列递增的最小交换次数 1187. 使数组严格递增 1505.

【DP难题】力扣1617-统计子树中城市之间最大距离

摘要: 力扣 1617,比较难的树形 DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们来看一个比较难的图论题,力扣 1617,也就是第 210 周赛 D 题。抽象之后是求树的直径

线段树区间修改

线段树相关基础 力扣1476-子矩形查询,延迟计算 线段树,树状数组 线段树维护区间最值RMQ 离散化,权值线段树,权值树状数组 线段树和树状数组题目汇总 线段树更新非叶节点 带懒标记的线段树模板 同时支持区间加法和区间乘法,区间求和模板 1622. 奇妙序列 P3373 【模板】线段树 2 线段树区间修改 懒标记当线段树有区间修改的需求 range_update_add(i, j,

【随机算法】拒绝采样

摘要: 拒绝采样的算法原理和两道例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在数值分析和计算统计中,拒绝采样是用于从分布生成观测值的基本技术,是一种精确的模拟方法。该方法适

【随机算法】蒙特卡洛

摘要: 蒙特卡洛方法入门 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 蒙特卡洛不是特定的算法,而是一种统计模拟算法思想,它可以理解为一种基于统计的数值计算方法。有很多随机化算法都

【DP难题】力扣1611-使整数变为0的最少操作次数

带有移位操作DP转移方程 格雷码 $1 题目题目链接 1611. 使整数变为 0 的最少操作次数 题目描述给你一个整数 n,你需要重复执行多次下述操作将其转换为 0 : 翻转 n 的二进制表示中最右侧位(第 0 位)。如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0,则翻转 n 的二进制表示中的第 i 位。返回将 n 转换为 0 的最小操作次数。 提示:10 <

格雷码

格雷码 枚举格雷码 搜索构造 镜像构造 计算格雷码 动态规划 异或运算 89. 格雷编码 格雷码转原数 动态规划 异或运算 1611. 使整数变为 0 的最少操作次数 $0 格雷码格雷码是一个二进制数系统,其中两个相邻数的二进制位只有一位不同。 例如 3 位(0~7)的格雷码 12345678G(0) = 000G(1) = 001G(2) = 01

DP方程组

$0 DP 方程组 两个 DP 方程 f[i] 和 g[j] 推导状态的时候是同时推进 i,j f[i] 可能与 f[i - 1] 和 g[j] 都有关 g[j] 可能与 g[j - 1] 和 f[i] 都有关 i 和 j 的具体推进方式和细节需要注意 $1 题目1537. 最大得分12345678910f[i] := 推进到 nums1[i-1] 的最大和g[j] := 推

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

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

单调队列优化DP

1425. 带限制的子序列和 单调队列优化DP单调队列优化 DP 的转移方程的形式 dp[i] = \min\limits_{L(i)其中 f(i, j) 可以分为仅与 x 相关和仅与 y 相关的两部分: f(i, j) = g1(i) + g2(j) 1425. 带限制的子序列和问题给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序

单调队列

摘要: 单调队列的算法原理,代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文详细介绍单调队列的算法原理、代码模板和应用。涉及到的题目汇总如下: 基本模型 239. 滑动窗口最大值

【DP难题】力扣1420-生成数组

第 185 场双周赛 D 题 dp[i][j][k], i 是阶段,j, k 是状态 $1 题目题目链接 1420. 生成数组 题目描述给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。 123456789101112maximum_value = -1;maximum_idx = -1;search_cost = 0n =

同余类分解状态优化DP

摘要: 同余类分解状态优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过两个力扣的题目看一下通过同余类分解状态的方式优化 DP。此外这两个问题都另外有贪心和自动机的解法。 同余类分解状

日期和时间

摘要: 力扣上日期和时间相关题目汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对日期和时间的处理是在编程中经常要处理的问题。本文我们总结力扣上与日期和时间有关的题目。由于不涉及什么算法

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

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

推公式优化DP

摘要: 一些可以通过推公式优化动态规划算法的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 通过分析问题列出的动态规划的转移方程,有时经过一些公式推导后可以简化,这也是一种可以优化动态规划算法的

自动机DP

552. 学生出勤记录 II 935. 骑士拨号器 1220. 统计元音字母序列的数目 1641. 统计字典序元音字符串的数目 1223. 掷骰子模拟 1220. 统计元音字母序列的数目问题给你一个整数 n,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串: 字符串中的每个字符都应当是小写元音字母(’a’, ‘e’, ‘i’, ‘o’, ‘u’) 每个元音 ‘a’

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

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

哈希表优化DP

摘要: 本文介绍了动态规划的一种优化方法:哈希表优化 DP。并拆解了 leetcode 上的 3 道题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 当动态规划的转移方程是以下形式的时候: 计

平衡树优化DP

1235. 规划兼职工作 975. 奇偶跳 1235. 规划兼职工作问题你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。 给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大

【分类讨论】力扣335-路径交叉

摘要: 本文详细拆解 力扣335-路径交叉,核心是分类讨论的思想 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个使用分类讨论思想解决的问题。此前我们解决过另一个分类讨论的问题

分类讨论

摘要: 本文通过两道题来说明分类讨论在算法中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分类讨论是算法中常见的一种思想,这种思想没有固定的套路,需要结合具体的问题进行分析。本文列出 5 道

k叉哈夫曼树

摘要: K叉哈夫曼树的链式实现,字符串编码解码的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 哈夫曼树与哈夫曼编码 中学习了二叉哈夫曼树与哈夫曼编码的原理,并给出基于数组实现的代码模

模拟哈夫曼建树过程的贪心合并问题

摘要: 模拟哈夫曼树建树过程的贪心算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 贪心-哈夫曼编码 和 k叉哈夫曼树 中,我们分别学习了 2 叉哈夫曼树和 K 叉哈夫曼树。 建树的过程

力扣1074-元素和为目标值的子矩阵数量

前缀和题目汇总 前缀和问题分类汇总 二维前缀和 力扣303,304-前缀和与差分 一维版本: 和为目标值的子数组数量 560. 和为K的子数组 $1 题目题目链接1074. 元素和为目标值的子矩阵数量 题目描述给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x

【多维分桶】力扣527-单词缩写

用哈希的方式对多属性分桶 维护桶内元素 排序 Trie $1 题目题目链接527. 单词缩写 题目描述给定一个由n个不重复非空字符串组成的数组,你需要按照以下规则为每个单词生成最小的缩写。 初始缩写由起始字母+省略字母的数量+结尾字母组成。若存在冲突,亦即多于一个单词有同样的缩写,则使用更长的前缀代替首字母,直到从单词到缩写的映射唯一。换而言之,最终的缩写必须只能映射到一个单词。若缩写并不

【分治难题】力扣751-IP到CIDR

摘要: 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个分治法解决的一个比较难的问题。 分治 + 位运算 $1 题目 751. IP 到 CIDR 给定一个起始 IP 地址 ip

高精度运算组件

摘要: 在字符串、数组、链表等数据结构上维护按位的加减乘除,力扣 8 八道题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在计算机中表示整数一般是通过 int、long long 等类型,这些类型

位运算疑难杂症

摘要: 位运算的疑难问题集锦 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 位运算操作 中我们梳理了基础的位运算的运算符、各种集合操作用位运算的实现方式、以及其他比较常见的位运算的问题及其代