Tag: 基础算法

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

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

均分纸牌问题

摘要: 贪心算法经典问题:均分纸牌 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下贪心算法的经典问题:均分纸牌问题。该问题在移牌规则上有两个比较常见的变种,一个是允许环形移牌,一个是

力扣2106-摘水果

摘要: 一个比较综合的前缀和问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,今天我们来看一个比较综合的问题,涉及到前缀和、二分和滑动窗口的综合,并且非常考验耐心。 题目 2106. 摘水

力扣372-超级次方

摘要: 力扣 372:快速幂、扩展欧拉定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 题目 372. 超级次方 你的任务是计算 ab 对 1337 取模,a 是一个正整数,b 是一个非常大的正

力扣1813-句子相似性3

摘要: 双串单向双指针 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,今天我们来看一个双指针的问题,力扣 1813。本题比较纯粹,就是双串单向双指针,没有综合其他的算法。 双串单向双指针是双

【Leetbook】区间问题

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

力扣1658-将x减到0的最小操作数

摘要: 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,今天我们来看一个单串单向双指针的问题。本题的特点是随着窗口左端点 left 变大,合法的窗口右端点 right 也会变大,这样的话我们

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

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

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

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

多米诺与托米诺骨牌平铺

摘要: 动态规划解决计数问题,模下矩阵快速幂优化 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,之前在文章 计数DP 中我们总结了常见的使用动态规划解决计数问题的题目,在文章

最大子数组和的绝对值

摘要: 本文介绍最大子数组和的一类变种:和最大改为和的绝对值最大 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个

最大子数组乘积

摘要: 最大子数组乘积,最大子数组和的一个变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法

带长度限制的最大子数组和

摘要: 带长度限制的最大子矩阵和 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法,都非常主流,并且

【树形DP】树的直径

摘要: 力扣 1245, 1522,树的直径,最经典的树形 DP 题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,我们继续研究力扣秋季赛的题目。在十一之前参加了力扣秋季赛个人赛,

算法导论第四版

摘要: 算法导论第四版介绍 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍一下算法导论第四版。本书的第四版是去年出来的,新增了机器学习算法等内容,还是有不少更新的。本书完整下载链接如下

【逆向思维】力扣780-到达终点

算法要点: 逆向思维,参考文章 逆向思维。 $1 题目题目链接780. 到达终点 题目描述给定四个整数 sx , sy ,tx 和 ty,如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty),则返回 true,否则返回 false。 从点 (x, y) 可以转换到 (x, x+y) 或者 (x+y, y)。 12提示:1 <= sx, sy, tx, ty

分治-逆序对个数

摘要: 分治法解逆序对个数问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分治 中,我们详细总结了分治法的内容,分治法有一个重要应用是归并排序。关于归并排序的算法细节和代码模板,可以参考

二分/手撕平衡树/分治/stable_sort

摘要: 综合题:二分、平衡树、分治、stable_sort 四种解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个排序的变种问题。跟排序一样,本题的解法也非常多,并且每个算法都是主流

差分的应用

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

递归的机器实现

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

分形与分治

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

枚举和找规律

摘要: 综合题:枚举+找规律 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个模拟的综合题,涉及到找规律、枚举、位运算等算法点。 题目95. 费解的开关 25 盏灯排成一个 5 * 5

【分治】A的B次方的所有约数之和

摘要: 综合题:分治+分解质因数+模下快速幂 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分治 中,我们系统学习了分治算法,了解了分治的思想和流程,以及研究分治算法时间复杂度的主定理,然后

力扣2104-子数组的范围和

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 面试好题连载 中,我们提到了适合作为面试题的几个标准大致如下: 对于

结合链表容易删除的特点使用逆向思维

逆向思维是一种常见的算法思维方式,在文章 逆向思维 中,我们例举了不少 leetcode 上用逆向思维解决的问题。 链表由于有易于删除的特点,因此经常与逆向思维结合使用。 在例如在文章 加索引的数组,用数组模拟双向循环链表 中我们解决的 136. 邻值查找。 本文我们再看一个类似的题 106. 动态中位数,本题的主流解法是 对顶堆,它是在线算法。这里我们用基于链表和逆向思维的离线算法。 问题依次读

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

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

大学数据结构笔记

摘要: 大学数据结构的笔记 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 大学数据结构笔记,2017年,共 51 页。主要内容如下: 数据结构基础 栈 队列 表 静态查找表 高级

大学基础算法笔记

摘要: 大学算法课笔记 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 在文章 多米诺与托米诺骨牌平铺 中,我们用矩阵快速幂优化 DP 的方式解决了一个计数问题

快速乘法

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

排序算法题目汇总

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

【分类讨论】力扣29-两数相除

摘要: 本文详细拆解 leetcode 29-两数相除,主要涉及分类讨论。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 面试好题连载 中,我提到了我认为的适合作为面试题的标准,这里复习一下

力扣437-路径总和3

摘要: 在树结构上维护前缀和的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 面试好题连载 中,我提到了我认为的适合作为面试题的标准,这里复习一下: 对于适合面试的题目,以下几个

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

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

力扣524-通过删除字母匹配到字典里最长单词

在文章 面试好题连载 中,我提到了我认为的适合作为面试题的标准,这里复习一下: 对于适合面试的题目,以下几个要点中 (1)(2)(5)必须满足,(3)(4)至少满足一个: (1) 考查基础的数据结构和主流算法,避开邪门算法和脑筋急转弯(2) 暴力方法很容易想到(3) 最好有两种以上的优化方式(4) 最好有两三道递进的题可以放到一起(5) 最终代码不长 今天我们看一个比较基础的题,leetcod

力扣689-三个无重叠子数组的最大和

算法要点 同时预处理出前缀和和后缀和 参考: 前缀和问题分类汇总 $1 题目题目链接 689. 三个无重叠子数组的最大和 题目描述给定数组 nums 由正整数组成,找到三个互不重叠的子数组的最大和。 每个子数组的长度为k,我们要使这3*k个项的和最大化。 返回每个区间起始索引的列表(索引从 0 开始)。如果有多个结果,返回字典序最小的一个。 1234注意:nums.length的范围在

力扣1352-最后K个数的乘积

摘要: 一个前缀和的变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 前缀和是力扣上非常常见的一个算法知识点,题非常多。在文章 【模板】前缀和与差分 中,我们介绍了前缀和与差分的算法原理和代码

力扣1124-表现良好的最长时间段

算法要点 前缀和 单调栈 相关题目 力扣962-最大宽度坡 $1 题目题目链接1124. 表现良好的最长时间段 题目描述给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」,意味在这段时间内,「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时

力扣1792-最大平均通过率

第 232 周赛 C 题 算法要点 堆贪心 参考: 贪心 $1 题目题目链接 1792. 最大平均通过率 题目描述一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] = [passi, totali] ,表示你提前知道了第 i 个班级总共有 totali 个学生,其中只有 passi 个学生可以通过

快速选择算法

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

最大子矩阵和

摘要: 最大子矩阵和问题,有两种处理二维情况的方式。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解

带大小限制的最大子数组/子矩阵和

摘要: 带大小限制的最大子矩阵和 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法,都非常主流,并且

分桶法

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

力扣LCP37-最小矩形面积

摘要: LCP37,计算几何问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们来看一个比较难的计算几何题,力扣 LCP37,本题是2021力扣杯春季赛团队赛第5题。算法要点如下: 两条直

二叉树的建树

摘要: 本文介绍了一类由给定的递归定义的建树规则进行建树的问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 相关的内容: 递归 中缀表达式建表达式树 后缀表达式建表达式树 抽象问题给出一组

力扣LCP03-机器人大冒险

摘要: LCP03,减治法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天看一个中等题吧,LCP 03,算法的思想还是非常主流的,就是经常跟分治法容易搞混的减治法,参考文章:减治法,注意细节处理

Python3自定义排序

摘要: Python 3 中如何实现自定义排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 自定义排序是算法中很常见的一个操作,参考自定义排序。 $1 自定义排序在 Python2 中,sort