Category: 基础算法

二维差分:用邮票贴满网格图

摘要: 二维差分 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在一维数组上,前缀和与差分是一种常见的处理区间求和问题的算法,参考文章 【模板】前缀和与差分。 如果二维的矩阵上有类似的与求和有关的问

中心扩散法

摘要: 枚举中点,看两边能扩散多长 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过最长回文子串问题,看一下数组上关于子数组的问题的两种不同方向的思考方式,一种是首先确定子数组的两端 l, r

二维转一维

摘要: 基于一维问题的解法,解决二维问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 一维数组上有一些常见的问题,应用了正确的算法后可以很好地解决。这些问题经常在二维矩阵上也有类似的问题。比如一维

分治算法的设计与分析-归并排序

摘要: 以归并排序为例来看分治算法的设计与分析 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分治法的设计思路一些算法在结构上是递归的,为了解决一个给定的问题,算法一次或多次递归地调用自身以解决相关

扫描线算法处理一系列区间上的统计问题

摘要: 扫描线算法、区间列上的统计问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 扫描线算法(Line-Sweep) 中,我们知道在平面上的计算几何问题中,可以通过直线平移扫描的方式,到

在有序数组中查找某个值的出现范围:C++和Python的几个二分查找组件的用法

摘要: STL 和 Numpy 在有序数组中二分查找 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个非常简单的二分查找的问题,重点看一下 STL 和 Numpy 中的相关写法。 题目 34

【Leetbook】区间问题

摘要: 区间问题的 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 区间问题介绍 双指针算法解决区间问题 贪心算法解决区间问题 区间合并 区间覆盖 区间不相

使用双指针实现有序数组原地去重

摘要: 有序数组原地去重 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 尺取法(单串单向双指针) 中,我们总结了 20 多道单串单向双指针的题目,这种算法也称为尺取法,或者不定长

分别计算各元素对答案的贡献的思想

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好。在很多问题中,我们要在一组元素上求解一个全局的指标,通过对具

差分的应用

摘要: 差分的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】前缀和与差分 中,我们介绍了前缀和与差分的算法思想和代码模板。并在文章 前缀和问题分类汇总 中分类罗列了 leetc

递归的机器实现

摘要: 递归的机器实现,递归转非递归 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 递归 中,我们讨论了与递归的相关的问题,并给出了题目列表。基于递归的两个最典型的算法是回溯和分治。 对于回

分形与分治

摘要: 分形问题与分治算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 什么是分形分形,具有以非整数维形式充填空间的形态特征。(关于非整数维的含义和理论,可以看后面介绍的资料)。通常被定义为“一个

下标映射

摘要: 下标映射的处理技巧 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 下标映射的处理技巧本文来看一种数组中常见的操作 — 下标映射。 有两个数组 nums 和 result。其中 nums 是原

按位单独处理

摘要: 按位单独处理的技巧 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文来看一种位运算中的常见操作 — 按位单独处理。 关于位运算的基础知识,可以看这两篇文章: 位运算操作,位运算疑难

快速幂

摘要: 本文介绍快速幂的算法原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings a^{11} = a^{2^{0}} \times a^{2^{1}} \times a^{2^{

快速乘法

摘要: 本文介绍快速乘法的算法原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings a^{11} = a^{2^{0}} \times a^{2^{1}} \times a^{2^

双指针和滑动窗口题目汇总

摘要: 本文总结一下双指针和滑动窗口题目的分类汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于双指针和滑动窗口的 73 道题,思路接近的题放到了一起。常见

分桶法

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

频数前缀和:用前缀和的思想快速计算区间上各个值的计数信息

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

尺取法(单串单向双指针)

摘要: 本文系统梳理了单串单向双指针的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 双指针 中,我们系统梳理了常见的双指针问题类型,包括单串单向、单串双向、双串单向、单串三指针等。

滑动窗口

摘要: 本文系统梳理定长滑动窗口相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 不定长滑动窗口不定长滑动窗口经常也称为尺取法,可以参考文章: 尺取法。 $1 定长滑动窗口 题

双指针

摘要: 本文系统梳理了双指针的算法要点。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 单串单向维护 [l, r]维护 [l, r] 的题目可以参

实数值域二分

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

实数区间二分

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

单峰性与三分查找

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

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

摘要: 带限制操作方式的重排问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 贪心:不限操作方式的重排问题 中,我们讨论了几种给数组重新排序的场景,需要满足一些给定的要求,或者最大化某个指

日期和时间

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

分类讨论

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

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

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

位运算疑难杂症

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

稀疏表(倍增优化DP):区间最值问题

摘要: 元素不变的区间最值问题,稀疏表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 给定一个数组,其中的元素可以修改,要查询数组中某个区间的和。过程中需要维护元素修改的操作,并且要高效查询区间的和

倍增法

摘要: 倍增法原理、代码模板、例题与应用场景 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 倍增法算法思想在递推状态的时候,只递推状态空间中 2 的幂次,当需要求其它位置的时候,利用以下性质,

自定义排序题目清单:定义 Cmp 结构体并重载 () 运算符

摘要: 题目汇总,自定义元素的比较方法,定义 Cmp 结构体病重载 (),比较逻辑中可能含复杂的判断逻辑,Cmp 的实例可能持有额外状态。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 C++

贪心-双指标规划问题

摘要: 一些用贪心解决的双指标规划问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在业务场景中,我们经常遇到这样一类优化问题。有一个对象池,我们要从中选出 K 个对象。这些对象中,有 x 和 y

贪心-分拆问题

摘要: 一些用贪心解决的分拆类问题, 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分拆类问题汇总 中我们总结了分拆类问题。这类问题没有固定的算法,要根据具体的问题看,本文我们看一下适用贪心

贪心:不限操作方式的重排问题

摘要: 几个用贪心解决的重排问题场景 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于一个数组来说,对其元素重新排序是最重要的操作。如果排序的依据就是从小到大,那么就是常规的排序算法。还有很多重排

贪心:构造性问题

摘要: 基于贪心的构造问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 构造是算法中广泛使用的一类技巧。其中贪心地构造是比较考验灵感的问题,没有定式化的方法论。本文整理了一些这类问题,共 11 题

贪心-删数,拼数,选数,改数

摘要: 贪心算法解决数字构造问题:删数、拼数、选数、改数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文罗列一下力扣上的一大类问题,也就是贪心算法解决的数字构造问题,包括删数、拼数、选数、改数等

奇数位置元素排在偶数位置元素之前

摘要: 线性结构上的一种常见操作 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个在线性结构上非常常见的操作,就是将奇数位置的元素排在偶数位置的元素之前。 首先我们考

逆向思维

摘要: 本文梳理了 leetcode 上用逆向思维的思想解决的问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文梳理力扣上 9 道用逆向思维的思想解决的问题,总览如下: 1558. 得到目

离散化

摘要: 离散化的原理和代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 离散化属于排序算法的应用,目的是把无穷大集合中的若干元素映射为有限集合,以便于统计。 很多时候,问题的范围是定义在整数集

单调性与二分

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

差分维护区间加法

摘要: 本文通过详细拆解 leetcode 370 来理解差分的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【模板】前缀和与差分 中,我们串讲了前缀和的算法原理和代码模板,并

惰性更新

摘要: 惰性更新的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 惰性更新是一种常见的思想,简单理解就是将更新操作存下来,但是不实际执行更新,而当查询的内容需要更新后的结果的时候,才执行更新

三色排序

摘要: 计数排序的特例:三色排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过一个模板题看一下三色排序问题。有计数排序和双指针两种方法。之后我们解决力扣 324 摆动排序2,其

非比较排序

摘要: 计数排序、桶排序、基数排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 计数排序当数据范围较小,例如十万级,可以通过一个计数数组统计各个数字出现的次数,然后在按照出现的数字和次数从小

位运算操作

摘要: 常见的位运算操作 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在编程中,经常会使用一些位运算操作,比如用位运算来实现集合的操作。本文我们总结一下常见的位运算操作,首先介绍基础的位运算的运算

异或的性质,数字出现次数问题

摘要: 利用异或的性质,解决数组中数字出现次数的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 异或的性质 交换律: $p \oplus q = q \oplus p$ 结合律: $p \opl

topK问题:第K个最大元素

摘要: TopK 问题的几种主流解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个大家都研究的很透的问题,数组中的第 K 个最大元素。这种 TopK 问题有 3 种主流解法: 用堆

众数,摩尔投票

摘要: 求众数的算法,摩尔投票 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文以 169. 多数元素 和 229. 求众数 II 来看一下求众数的算法。其中我们重点看一下摩尔投票算法。 求众数问