Tag: 代码模板

用字符串哈希解决经典问题:最长重复子串、最长公共子串

摘要: 可以用字符串哈希解决的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决,比

Floyd算法

摘要: Floyd算法的原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 历届图灵奖得主基本上都有高学历、高学位,绝大多数有博士头衔。这是可以理解的,因为创新型人才需要有很好的文化素养

迪杰斯特拉算法(Dijkstra)

摘要: 迪杰斯特拉算法原理与代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 迪杰斯特拉(Edsger Wybe Dijkstra)在一个充满科学气息的家庭背景中长大,父亲

序列自动机

摘要: 序列自动机原理、代码模板、应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们串讲一下序列自动机的原理和代码模板。然后解决力扣 392。 序列自动机在文章 词法分析-有限自动机 中,

牛顿插值的原理与实现

摘要: 牛顿插值的原理与应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在业务场景中,我们经常要找到某个指标与某个因素之间的变化关系,这种变化关系有时可以用函数来表示。 对于这

卢卡斯定理

摘要: 求组合数的代码模板和例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 卢卡斯定理设 p 是一个素数,将 m 和 n 写成 p 进制数: n = a_{0} + a_{1}p + a_{2

手撕平衡树-Treap

摘要: Treap 的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前,我们已经写过不少关于树的文章,包括二叉树、二叉查找树、平衡树。 二叉树 树的DFS

手撕平衡树-数组模拟链表实现二叉查找树

摘要: 用数组模拟链表的方式实现二叉查找树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们用数组模拟链表的方式实现二叉查找树,并形成代码模板。 关于二叉查找树,在文章 手撕

随机数据生成与对拍

摘要: 随机数据的生成 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 很多时候我们在写出一个解决问题的算法的程序之后,想要验证其正确性。比较直接的方法是构造随机数据,然后将自己的算

递归的机器实现

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

二分图匹配-最大匹配

摘要: 二分图最大匹配的算法:匈牙利算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于一个无向图 G,有 N 个节点(N >= 2),可以发分成 A, B 两个非空集合,其中 $A \c

用数组模拟链表的方式实现【带权有向图的邻接表】

在文章 邻接表 中,我们学习了邻接表及其应用,在文章 用数组模拟双向循环链表 中,我们学习了用数组模拟的方式实现链表,并用该链表解决了实际问题,同时 结合链表容易删除的特点使用逆向思维 中也介绍了一个思路完全一样的题目,也是用数组模拟链表解决的。 邻接表中的链表实际上也可以用数组模拟的方式来实现,本文我们就来看一下带权有向图的邻接表用数组模拟的实现方式。 带权有向图的邻接表在一个有 n 个点,m

用数组模拟双向循环链表

在文章 【模板】双向链表 中,我们实现了双向循环链表,并将其用在实现了 LFU,以及实现循环双端队列中。 在文章 邻接表,中我们学习了一种基于链表的数据结构: 邻接表。这种邻接表可以应用在桶、开散列表以及图和树存储中。 在文章 加索引的数组 和 加索引的链表 中,我们学习了对链表和数组中加各种索引的方式。 本文我们来看一种用数组模拟双向循环链表的实现方法,相关的基础知识可以看前面的几篇文章,重点是

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

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

快速幂

摘要: 本文介绍快速幂的算法原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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^

并查集-加边过程中维护具体连通分量

问题背景并查集回炉 基础并查集功能和题目列表: 并查集 带权并查集功能和题目列表: 带权并查集 并查集维护平面点的横纵坐标 并查集时光倒流 对于用[带权]并查集解决加边连通性的问题,我们之前处理过以下几类问题: 加边过程中动态地处理【两个点 x, y 是否连通】的查询问题 加边过程中动态地处理【某个点 x 对应的连通分量的大小】的查询问题 加边过程中动态地处理【当前连通分量的个数】的查询问题

模拟退火

摘要: 介绍模拟退火的原理并解决力扣 1515 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 梯度下降 和 爬山法 中我们学习了解决在目标函数上找最优解的两类算法,

梯度下降

摘要: 梯度下降的原理和代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文介绍梯度下降的算法原理和代码模板。在梯度概念的基础上,介绍梯度下降的算法,以及批梯度下降

一点绕另一点旋转

摘要: 一点绕另一点旋转的原理和代码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 点(向量) $\vec{P}$ 绕 O 旋转 $\theta$点 $\vec{P}$ 绕原点 O 旋转后的点为 $

半平面交

摘要: 本文介绍计算几何中半平面交算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基于二维

摘要: 本文介绍计算几何中与点相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 本文我

凸包的直径,旋转卡尺算法

摘要: 本文介绍计算几何中求凸包的直径的算法:旋转卡尺 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类

扫描线算法(Line-Sweep)

摘要: 扫描线算法:直线平移扫描 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们介绍一个计算几何中非常重要的算法:扫描线算法。除了计算几何之外,扫描线算法还可以解决很多区间的问题,力

多边形

摘要: 本文介绍计算几何中与多边形相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此

直线和线段

摘要: 本文介绍计算几何中与直线和线段相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。

【模板】二维向量的实现

摘要: 本文介绍一个向量的代码模板,解决几何问题是会频繁使用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文介绍一个向量的代码模板,解决几何问题是会频繁使用,在文章 几何题汇总 中,我们

凸包

摘要: 本文介绍计算几何中关于凸包的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基

小数转分数

摘要: 小数转分数的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的小数转分数的问题。在编程中,除了整数以外,我们主要用的是小数,比如 float、double

线性空间与线性基

摘要: 本文介绍线性基的算法原理和代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 高斯消元与线性方程组 中,我们学习了高斯消元的原理和代码模板。有了高斯消元算法的基础,本文我们看

高斯消元与线性方程组

摘要: 本文介绍高斯消元的算法原理和代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍高斯消元的算法原理和代码模板。首先简要介绍一下线性方程组与高斯消元,以及高斯消元的特殊情况:无

【模板】双向链表

双向循环链表 节点定义 接口 迭代器相关 定点增删改查 头尾增删改查 模板: 双向循环链表 测试: 剑指 Offer 62. 圆圈中最后剩下的数字 应用 460. LFU缓存 【模板】双向链表+哈希映射,有序字典,LRU,LFU 模板: 641. 设计循环双端队列 $1. 双向循环链表(1) 节点定义1234567891011typedef int DLType;const

【模板】无重哈希映射

哈希集合 无重映射 哈希映射在哈希集合基础上的变化 模板:闭散列表无重哈希映射 模板:开散列表无重哈希映射 测试: 706. 设计哈希映射 应用: 460. LFU缓存 有重映射 $1 哈希集合哈希映射是将哈希集合中的每个节点加一个数据的字段,其余部分与哈希集合基本一样。支持集合增删改查的哈希表理论也与哈希集合一样。 【模板】哈希集合 $2 无重映射 insert(k, v):

【模板】哈希集合

哈希函数 取余 相乘取整 哈希冲突 闭散列 线性探测 平方探测 再散列探测 开散列 邻接表 重哈希(rehash) 原理 触发时机 可重集合实现方式 模板 闭散列表 (无重集合/可重集合) 开散列表 (无重集合/可重集合) 测试:705. 设计哈希集合 应用:1074. 元素和为目标值的子矩阵数量 $1 哈希函数(1) 取余1234int hash1(const

字符串哈希

摘要: 本文系统梳理了字符串哈希相关的要点,并通过字符串精确匹配问题给出代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们系统串讲一下字符串哈希算法。字符串哈希是一种哈希函数

对顶堆

摘要: 对顶堆的思想,在中位数问题中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二叉堆 中,我们详细学习了二叉堆的原理、代码模板,以及在排序中的应用。 $0 场景维护一个数据结构支

二叉堆

摘要: 经典的二叉堆的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们串讲一下经典的二叉堆的原理、实现,代码模板和应用。 $1 二叉堆原理堆是一种支持插入key,删除

实数区间二分

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

三分查找

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

base64编码的原理与实现

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

线段树区间修改

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

单调队列

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

k叉哈夫曼树

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

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

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

进制转换

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

跳表

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

有向图的必经点,支配树

摘要: 有向图的必经点,支配树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个从业务场景中抽象出来的图论的问题:有向图的必经点。给定有向图上的两个点 S 和 T,从

稀疏表维护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 的幂次,当需要求其它位置的时候,利用以下性质,