排序_插入排序
简述 插入排序思想，假设对数组A[p...r]排序: 维持不变式：设当前排序的元素是 A[q]，则保持A[p...q-1]为排好的，A[q]在A[p...q-1]中找到它的位置坐下 复杂度 O(n^2) 原地排序 实现
搜索与图论模板
树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 树与图的遍历 拓扑排序 时间复杂度O(n+m),n表示点数，m表示边数 朴素dijkstra算法 时间复杂度O(n*n+...
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 递归实现 插值查找 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较 $$ mid = \frac{(low+high)}{2} $$ $$ mi...
数学知识模板
试除法判定质数 试除法分解质因数 朴素筛法求素数 线性筛法求素数 试除法求所有约数 约数个数和约数之和 欧几里得算法 求欧拉函数 筛法求欧拉函数 快速幂 扩展欧几里得算法 高斯消元 递归法求组合数 通过预处理逆元的方式求组合数 Lucas定理 分解质因数法求组合数 卡特兰数 NI...
匹配_Rabin_karp匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称为字符串。 原理 假设 M={0,...
匹配_朴素字符串匹配算法
字符串匹配 字符串匹配的形式化定义如下：假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称...
数据结构_最小优先级队列
概述 优先级队列是一种用来维护由一组元素构成集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字。一个最小优先级队列支持以下操作： insert(S,x):将元素x插入到集合S中 min(S)：返回S中具有最小关键字的元素 extract_min(S):去掉并返回S中具有...
动态规划_最长公共子序列
简述 最长公共子序列算法思想，令 X=< x1,x2,...xm > Y=<y1,y2,...yn> 为两个序列， Z=<z1,z2,...zk>为X和Y的某一个最长公共子序列： 如果 xm=yn，则zk=xm=yn,且Z(k-1)是X(m-1...
排序_基数排序
简述 基数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且不超过RADIXWITH位（有模板的RADIXWITH参数指定）： 首先对A中所有元素按照个位数大小进行排序（原地的） 再对A中所有元素按照个十数大小进行排序（原地的） 一直到最后按照A中所有元...
搜索当前标签