Category: 基础算法

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

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

【Leetbook】区间问题

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

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

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

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

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

差分的应用

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

递归的机器实现

在文章 递归 中,我们讨论了与递归的相关的问题,并给出了题目列表。基于递归的两个最典型的算法是回溯和分治。 对于回溯,在文章 枚举 中,我们通过若干 leetcode 的题目总结了多项式、指数、排列、组合型枚举。在文章 回溯法入门-递归实现指数,排列,组合型枚举 中,我们通过 acwing 的三道模板题把递归实现指数、排列、组合的代码放到了一起进行对比。 对于分治,在文章 分治 中,我们系统学习了

分形与分治

什么是分形分形,具有以非整数维形式充填空间的形态特征。(关于非整数维的含义和理论,可以看后面介绍的资料)。通常被定义为“一个粗糙或零碎的几何形状,可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状”,即具有自相似的性质。 分形是一个数学术语,也是一套以分形特征为研究主题的数学理论。分形理论既是非线性科学的前沿和重要分支,是研究一类现象特征的新的数学分科,相对于其几何形态,它与微分方程与

回溯法入门-递归实现指数,排列,组合型枚举

在文章 枚举 中,我们通过若干 leetcode 的题目总结了多项式、指数、排列、组合型枚举。 多项式枚举的状态空间是 $n^{k}$,实现方式是 n 层循环。没有例题。 指数型枚举,状态空间是 $2^{n}$,实现方式有递归和位运算。无重复集合和有重复集合都有实现。 排列型枚举,状态空间是 $n!$,实现方式是递归。无重复排列和有重复排列都有实现。 组合型枚举,状态空间 $\binom{n}{

大学基础算法笔记

摘要: 大学算法课笔记 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 大学基础算法笔记,2017年,共 52 页。 算法基础 基本特性 计数与渐进 分治与递归 算法设计 动态规划 贪心 随机化

下标映射

本文来看一种数组中常见的操作 — 下标映射。 有两个数组 nums 和 result。其中 nums 是原数组,算法过程中需要对 nums 中的元素位置进行改变,而 result 就是算法过程中对 nums 中的元素位置改变后生成的新数组。并且新数组 result 跟原数组 nums 有某种下标映射关系:原数组的下标 i,对应新数组的下标 j。 注意这种映射可以理解为 [1, 2, …, n] 到

按位单独处理

摘要: 按位单独处理的技巧 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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^

排序算法题目汇总

本文总结了力扣上 2000 题以内的关于排序的 37 道题。将场景相同的放到了一起。 场景上主要涉及数组排序、链表排序、自定义排序、非比较排序、排序组件的应用。 算法上涉及的点比较多。堆排序中涉及到堆,快速排序涉及到减治算法,归并排序涉及到分治算法,非比较排序中涉及到分桶算法等等。这些算法都是比较基础的,而且它们各自都有非常多的场景和题目。其中分桶算法以前总结过,可以满这篇 分桶法 。堆,分治和减

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

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

快速选择算法

背景快速选择算法是解决【从 N 个元素中选出前 K 个或第 K 个】这个问题的算法。这个问题是 topK 问题中比较简单的一类,稍微复杂一点的 topK 问题就需要用堆和值域二分等算法。关于 TopK 问题,可以参考这篇文章: topK问题分类汇总 快速选择算法是一种减治算法,通过 partition 将问题区间 [left, right] 划分为 [left, partition] 和 [par

分桶法

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

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

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

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

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

滑动窗口

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

减治法

partition 刚好在二分点 二分 1060. 有序数组中的缺失元素 partition 不一定在二分点 1545. 找出第 N 个二进制字符串中的第 K 位 1533. 找到最大整数的索引 topK topK问题分类汇总 4. 寻找两个正序数组的中位数 215. 数组中的第K个最大元素 973. 最接近原点的 K 个点 剑指 Offer 40. 最小的k个数

双指针

摘要: 本文系统梳理了双指针的算法要点。并汇总了 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 在文章 二分 中,我们总结了二分的常见类型,其中主要是区间二分以及值域二分。之后

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

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

格雷码

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

日期和时间

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

分类讨论

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

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

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

位运算疑难杂症

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

稀疏表维护RMQ

问题问题:给你一个数组 ,其中有 N 个数字,现在给你一次查询,给你区间[l ,r],问你在这个区间内的最值为多少 数组长度为 N,查询次数为 Q 主流解法 1、搜索,$O(n)$ 预处理 $O(qn)$ 在线查询。 2、稀疏表(ST),$O(n\log{n})$ 预处理 $O(q)$ 在线查询。 3、线段树/树状数组,$O(n)$ 预处理 $O(qlogn)$ 在线查询。 4、RMQ标准算法:先

倍增法

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

装箱问题

1564. Put Boxes Into the Warehouse I 1580. Put Boxes Into the Warehouse II 1564. Put Boxes Into the Warehouse I从右往左考虑 warehouse, j = n-1,...,0,[0..j] 的最小高度为 minh[j] 从 boxes 中找小于等于 minh[j] 的最高的箱子 12

自定义排序

自定义排序 791. 自定义字符串排序 1329. 将矩阵按对角线排序 1333. 餐厅过滤器 1030. 距离顺序排列矩阵单元格 524. 通过删除字母匹配到字典里最长单词 179. 最大数 406. 根据身高重建队列 1366. 通过投票对团队排名 1057. 校园自行车分配 1029. 两地调度 1094. 拼车 1058. 最小化舍入误差以满足目标 1090. 受标签影响的最大值 135

贪心-双指标规划问题

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

贪心-疑难杂症

Ref: 自定义排序 贪心问题汇总 406. 根据身高重建队列 860. 柠檬水找零 649. Dota2 参议院 乘船问题:881. 救生艇 910. 最小差值 II 927. 三等分 948. 令牌放置 1029. 两地调度 1247. 交换字符使得字符串相同 1338. 数组大小减半 1400. 构造 K 个回文字符串 1403. 非递增顺序的最小子序列 1578. 避免重复字母的最

贪心-分拆问题

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

贪心-部分背包

摘要: 部分背包问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 01 背包和完全背包是动态规划中很基础并且很重要的一类问题。 在 01 背包的基础上,对于每个物品 i,如果可以拿走其一部分,而不

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

奇数位置元素排在偶数位置元素之前 相邻 k 个元素不同 767. 重构字符串 358. K 距离间隔重排字符串 621. 任务调度器 1054. 距离相等的条形码 田忌赛马 870. 优势洗牌 455. 分发饼干 1433. 检查一个字符串是否可以打破另一个字符串 情侣牵手 组合数学5-群论 765. 情侣牵手 权值最大 1589. 所有排列中的最大和 1402. 做菜顺序

贪心-构造性问题

984. 不含 AAA 或 BBB 的字符串 1405. 最长快乐字符串 484. 寻找排列 651. 4键键盘 995. K 连续位的最小翻转次数 1046. 最后一块石头的重量 1253. 重构 2 行二进制矩阵 1605. 给定行和列的和求可行矩阵 1354. 多次求和构造目标数组 1144. 递减元素使数组呈锯齿状 1540. K 次操作转变字符串 1558. 得到目标数组的最少函数调用

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

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

贪心

摘要: 本文系统梳理了贪心相关的算法。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 正确性证明(Ref: 《算法竞赛进阶指南》) 微扰法 范围缩放

贪心-加油站问题

$1 基础问题134. 加油站问题在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。 说明:123如果题目有解,该答案即为唯一答案。输入数组均为非空数组,

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

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

逆向思维

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

递归

递归的三种情况 定义是递归的 数据结构是递归的 问题解法是递归的 $1 定义是递归的例如字典,字典中的词,是由其它词来定义的。而这些其它词的定义又会直接或间接地用到由它们定义的词。 使用递归有一个基本条件:有一些 base case 可以采用非递归的方式计算出来。 括号问题汇总语法分析问题分类汇总其它 87. 扰乱字符串 761. 特殊的二进制序列 776. 拆分二叉搜索树 1003. 检查替

分治

主定理 二分分治 932. 漂亮数组 169. 多数元素 23. 合并K个升序链表 53. 最大子序和 751. IP 到 CIDR 参考 线段树,树状数组 四分分治 1274. 矩形内船只的数目 参考 二维线段树,二维树状数组 CDQ分治 315. 计算右侧小于当前元素的个数 参考 离散化,权值线段树,权值树状数组 线段树和树状数组题目汇总 相似的场景概念 分治与

离散化

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

排列算法

枚举排列: 无重复: 46. 全排列 有重复: 47. 全排列 II DFS: 可以处理重复, 枚举 字典序法: 可以处理重复 SJT算法: 不能处理重复 下一个排列 31. 下一个排列 字典序法 第 K 个排列 60. 第k个排列 DFS + 剪枝 阶乘数系统 康托展开与康托编码 排列的哈希 $1 枚举排列 46. 全排列 47. 全排列 II 以上两题为输出所有的排列,一个