模板栏

摘要: 算法代码模板整理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

• 01 基础算法
• 02 数据结构
• 03 字符串
• 04 搜索
• 05 动态规划
• 06 图论
• 07 组合数学
• 08 几何
• 09 数论
• 10 概率
• 11 博弈
• 12 代数
• 13 随机

---

01. 基础算法

知识点	C++模板
二分	整数二分 实数二分 三分
倍增	倍增法 快速幂和矩阵快速幂 稀疏表RMQ LCA, 树上倍增
位运算	基础位运算 【STL】bitset
离散化	离散化
枚举	枚举子集, 排列, 组合
前缀和	前缀和与差分 差分维护区间加法
排序	链表排序 数组排序 非比较排序
区间合并	区间合并
高精度运算	高精度运算

---

02. 数据结构

知识点	C++模板
栈, 队列, 链表	单调栈 单调队列
跳表	跳表
二叉查找树	二叉查找树BST
平衡树	大小平衡树
线段树	线段树,树状数组 权值线段树,权值树状数组 二维线段树,二维树状数组 线段树维护区间最值 线段树区间修改
哈夫曼树	2叉哈夫曼树 k叉哈夫曼树
堆	二叉堆
并查集	并查集 带权并查集
Trie	Trie 双向Trie 01Trie

---

03. 字符串

• 字符串精确匹配
• 字符串哈希
• 后缀数组
• 高度数组
• 字典序

---

04. 搜索

基础搜索

树的BFS遍历
树的DFS遍历
DFS
BFS

进阶搜索

双向搜索
剪枝
迭代加深
IDAstar
Astar
搜索顺序

---

05. 动态规划

---

06. 图论

知识点	C++模板
环	无向图的环 有向图的环
连通分量	有向图的连通分量 无向图的连通分量 无向图的双连通分量
桥和割点	tarjan算法 无向图的桥 无向图的割点
哈密顿路径 欧拉路径	哈密顿路径 欧拉路径
最短路径	带权图最短路径
拓扑排序	拓扑排序
最小生成树	最小生成树

---

07. 组合数学

知识点	C++模板
排列	全排列与字典序转换, 康托编码
组合	组合数 多重集的组合数
容斥	容斥计数
母函数	-
群论	-

---

08. 几何

知识点	C++模板
向量	向量 【STL】复数
基本元素	点 极角 直线和线段 旋转
距离	拆目标函数中的绝对值 曼哈顿距离
扫描线	扫描线 Angular Sweep
多边形与凸包	多边形 凸包 旋转卡尺 半平面交

---

09. 数论

知识点	C++模板
素数	素数筛 约数 【C++17】最大公约数
同余	同余
数制	分数转小数, 数字运算的 Corner Case 负进制数与模负数 进制转换 小数转分数,连分数 取模与分数取整

---

10. 概率

---

11. 博弈

---

12. 代数

知识点	C++模板
线性基	高斯消元与线性方程组 线性空间与线性基 异或空间
多项式	-

---

13. 随机

知识点	C++模板
随机数	【STL】随机数
洗牌	【随机算法】洗牌
采样	【随机算法】加权蓄水池抽样 【随机算法】蓄水池抽样 【随机算法】拒绝采样

---