Archive: 2020/10

对顶栈

摘要: 对顶栈的使用场景 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 场景有一个光标,给出对光标的操作序列,维护操作结果,当操作有以下特性时,对顶栈可以很好地解决。 一次只移动一位 添加、

加索引的链表

摘要: 加索引的链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一

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

摘要: 基于 Trie 的日期索引设计 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 题目635. 设计日志存储系统 你将获得多条日志,每条日志都有唯一的 id 和 timestamp ,ti

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

摘要: 基于图算法的设计 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 题目 631. 设计 Excel 求和公式 你的任务是实现 Excel 的求和功能,具体的操作如下: Excel(in

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

摘要: 最小可用 ID 的维护 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个设计题,数据结构的设计比较复杂,同时还需要处理最小可用 ID 的维护。 $1 题目 1500. 设计文件分享系

实数区间二分

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

三分查找

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

base64编码的原理与实现

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

双向Trie

摘要: 在一个 Trie 节点同事维护前缀和后缀 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 双向Trie场景一个 Trie 可以预处理一批单词的所有前缀,或者所有后缀。此后可以快速进行与前

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的最大数量

摘要: 一个排序贪心的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,今天我们来看一个排序贪心的问题。比较难想,但是想通了之后就非常简单。 $1 题目 1183. 矩阵中 1 的最大数量

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

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

线段树大模板:区间修改(加法、乘法)、区间和查询

摘要: 线段树区间修改(加法、乘法)、区间和查询 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 线段树和树状数组:单点修改、区间和查询 中我们学习了线段树的单点更新、区间查询,并解决了区间求

【随机算法】拒绝采样

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

【随机算法】蒙特卡洛

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

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

摘要: 力扣 1611, 稀疏状态,带位运算的状态转移方程 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文是一个动态规划问题,状态转移方程中有位运算操作,状态取值非常稀疏。处理这种稀疏状

格雷码

摘要: 格雷码的枚举和计算,异或与动态规划 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在通信中,由于信息码元序列是一种随机序列,接收端无法预知码元的取值,也无法识别其中有无错码。所以在发送端需要

方程组DP

摘要: 同一套阶段划分下的两套状态表示以及转移方程 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较少见的动态规划问题。场景是两个串,按照两个串比较常见的思路,参考 LCS 问题

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

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

单调队列优化DP

摘要: 单调队列优化 DP 的思路以及一些例子 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 使用数据结构优化动态规划的状态转移过程是很常见的思路,例如 平衡树优化DP、哈希表优化DP。单调队列也是

单调队列

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

同余类分解状态优化DP

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

日期和时间

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

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

摘要: 应用了最优性剪枝和搜索顺序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个搜索题,主要的难点在于需要应用最优性剪枝,以及改变搜索顺序的优化方法。 $1 题目1240. 铺瓷砖 你

推公式优化DP

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

【搜索难题】力扣898-子数组按位或操作

摘要: 等效性剪枝 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个搜索问题,涉及到了记忆化,以及等效性剪枝。 $1 题目 898. 子数组按位或操作 我们有一个非负整数数组 A

哈希表优化DP

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

【分类讨论】力扣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-元素和为目标值的子矩阵数量

摘要: 基于一维问题的解法,解决二维问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 题目1074. 元素和为目标值的子矩阵数量 给出矩阵 matrix 和目标值 target,返回元素总和

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

摘要: 桶外分类、桶内排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个分桶的问题。首先根据需求对字符串设计一种哈希值,该值包含了词的长度信息,首字符和尾字符信息。然后依据

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

摘要: 减治法,模拟难题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个困哪的模拟题,直接按照要求实现功能即可,难点在于对问题的拆解带有一些减治的思想、以及位运算的一些细节。 $1 题

高精度运算组件

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

位运算疑难杂症

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

限制运算符的数字运算

摘要: 限制运算符的数字运算问题,四道题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 有时我们会遇到实现某种运算的问题,但是限制某些运算符的使用。这类问题主要考察的是对各个运算符的特性的理解,以及

分数转小数, 数字运算的 Corner Case

摘要: 力扣166:分数转小数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过力扣 166 来看一下在数学算法中常见的分数转小数的问题。算法比较简单,类似于竖式除法的过程,称为长除法,但

负进制数与模负数

摘要: 负进制数与10进制的转换,模负数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 进制转换 中,我们系统整理了 k 进制(k > 0)与十进制的互相转化,包括整数部分、小数部分。

进制转换

摘要: 进制转换的算法、代码模板、例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在进制转换当中,我们比较熟悉的是二进制和十进制之间的互相转换。有时候我们会遇到 k 进制与 10 进制互相转换的

后缀数组:排名为i的后缀的起始下标

摘要: 后缀数组原理与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 背景一个长度为 n 的字符串 s,共有 n 种后缀。现在想对这 n 个后缀排序,将排序结果保存在一个数组 sa 中。sa[i

跳表

摘要: 跳表的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 跳表背景与哈希表、平衡树、Trie类似,跳表也可以看成是一种自带索引的数据结构(索引结构)。即根据给定的 key,可以快