目录
- 链表与邻接表：树与图的存储
- 栈与队列：单调队列、单调栈
- kmp
- Trie
- 并查集
- 堆
- Hash表
- stl简述
1. 链表与邻接表
1.1链表
1.1.1 单链表
组成
$head$存储链表头，$e$[ ]存储节点的值，$ne$[ ]存储节点的next指针，$idx$表示当前可用结点的下标
int head, e[N], ne[N], idx;
初始化
void init()
{
head = -1;
idx = 0;
}
操作
$(1)$ 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
$(2)$ 将头结点删除，需要保证头结点存在
void remove()
{
head = ne[head];
}
$(3)$删除任意点同上，懒惰删除，将上一个结点的指针域指向当前结点的下一个结点即可
1.1.2 双链表
组成
$e$[ ]表示节点的值，$l$[ ]表示节点的左指针，$r$[ ]表示节点的右指针，$idx$表示当前可用结点
int e[N], l[N], r[N], idx;
初始化
0是左端点，1是右端点，二者作为哨兵结点
void init()
{
r[0] = 1, l[1] = 0;
idx = 2;
}
操作
操作都要注意内部指针指向问题
在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
1.2 邻接表
邻接表就是多个链表
表示和单链表相似，就是原来是一个头结点$h$，现在是头结点数组
int h[N], e[N], ne[N], idx ;
头结点数组需要初始化为空指针（-1）
memset(h, -1, sizeof h);
2. 栈与队列：单调队列、单调栈
2.1 栈
2.1.1 模拟栈
使用数组下标是从1开始的，位置0不用于存储
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
2.1.2 单调栈
常见模型：找出每个数左/右边离它最近的比它大/小的数
在栈内维护一个单调数列（递增或者递减）
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(q[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
2.2 队列
2.2.1 模拟队列
这里数组下表从$0$开始使用
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}
2.2.2 单调队列
常见模型：找出滑动窗口中的最大值/最小值
流程：
1. 判断队头是否滑出窗口
2. 入队
3. 输出答案
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
3. KMP算法
字符串下标都是从$1$开始
$s$[ ]是模式串，$p$[ ]是模板串, $n$是$s$的长度，$m$是$p$的长度
我们每次都是拿$s[i]$与p$[j + 1]$行匹配，成功则继续匹配，失败就从$ne[i]$继续匹配
求$ne[ ]$可以看做字符串自己与自己匹配的过程
求Next数组：
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
// 因为我们是从前往后找每一个i 的ne值，因此用到的一定是已经求出来的
//模板串短的话，可以考虑暴力做法。KMP算法自己手工模拟几遍效果比较好
if (p[i] == p[j + 1]) j ++ ; //如果下一个匹配成功，那么ne[ ]的下标也可以右移
ne[i] = j;
}
匹配
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
//当前字符未匹配成功，并且不是第一个字符时， j = ne[j]，前后缀是相等的，利用了已有信息
if (s[i] == p[j + 1]) j ++ ;
//结束条件有两个，如果这时候第i个字符匹配上了，那么 j ++
if (j == n)
{
//一组匹配成功的具体逻辑
//j = ne[j];这一步是进行下一次匹配
}
}
4. Trie树（字典树）
trie树又称字典树，是高效查找和存储字符串的一种数据结构
一般情况只会存储有限少量的字符，$eg:$ 英文小写字母，英文大写字母，阿拉伯数字
$trie$树的构成
$N$表示要开的总结点数， $M$表示每个结点指针域的数量
$0$号点既是根节点，又是空节点
$son$[ ][ ]存储树中每个节点的子节点，第一维是该节点下标，第二维存储的是指向的下一个结点的下标；这里是数组模拟指针的一个过程
$cnt$[ ]存储以每个节点结尾的单词数量
$idx$存的是已经使用的结点下标，++即可得到可用的下标
int son[N][M], cnt[N], idx;
$trie$的树的基本操作
1. 插入操作
$p$表示当前结点下标
字符串结尾是 \0，当不是结尾的时候就往下走
如果结点不存在，我们就创建一个
结点存在，我们就接着遍历这个结点
字符串走完时，在末位结点$cnt ++ $，表示以该点结尾的单词多了一个
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
2. 查询字符串出现的次数
与插入很相似
不同的是，如果往下挨个字符查找时候
如果这个字符不存在，表示该单词不存在，就返回$0$
遍历完每一个字符后，看看以改点结尾的单词个数，返回$cnt$[ ]
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
5. 并查集
这里介绍朴素并查集，并查集一般还需要维护额外信息，如维护大小，维护到祖宗结点距离，额外信息需要具体题目集体分析
维护大小的并查集： https://www.acwing.com/solution/content/75667/
维护到祖宗结点距离的并查集： https://www.acwing.com/solution/content/75751/
并查集有路径压缩与按秩合并两种操作，不过我们一般只会用到路径压缩
路径压缩的并查集可以以近乎$O(1)$的时间来完成查询与合并操作
并查集初始化
int p[N]
for (int i = 1; i <= n; i ++ ) p[i] = i;
$p[N]$表示的是某一个结点所在集合的代表元素的下标(或者说是父节点，没有父节点的结点存自己下标)
初始化时候，每个结点是一个独立的集合，而每个集合的代表元素都是自己
并查集的常见操作
1. 寻找祖宗结点
这里可以同时进行路径压缩，之前的画出来的树，是很多结点依次指向直接父节点，路径压缩后，每个结点的父节点都会是祖宗结点，减少了下一次查询与合并的时间
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]); // 每一个p[x]最后都会赋值为它的祖宗结点下标，即完成了路径压缩
return p[x];
}
2. 合并a和b所在的两个集合
让$a$集合的祖宗结点（代表元素）的父节点设置为$b$集合的祖宗结点
p[find(a)] = find(b);
6. 堆
由于支持任意元素删除修改的模拟堆不太常用，这里就不介绍，只介绍数组模拟堆排序
支持任意元素删除修改的模拟堆见： https://www.acwing.com/solution/content/75671/
下面写的都是小根堆
组成
$h$[ ]存数据,$cnt$表示堆的大小
int h[N], cnt;
两个基本操作
下滤
堆的某一个元素，从当前位置，不断向下调整，让沿路的子树都满足堆的性质
首先找到当前结点与两个子节点中最小的结点，然后如果最小的结点不是当前结点，就将它与当前结点交换，然后递归操作交换后的结点
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
上滤
堆的某一个元素，从当前位置，不断向上调整，让沿路的子树都满足堆的性质
从当前结点溯流而上，遇到不满足的时候，就交换
void up(int u)
{
while (u / 2 && h[u] < h[u / 2] )
{
swap(h[u], h[u * 2]);
u >>= 1;
}
}
常见操作
1. 堆的插入
在堆的最后补充一个元素，然后进行上滤操作
2. 删除最小值
将最后一个元素覆盖第一个元素，然后进行下滤操作
3. 堆的构造
我们当然可以去每一个元素挨个插入去构造，不过这样时间复杂度是$n log n$的
有一个$O(n)$的建堆方式，也就是从树的倒数第二层，依次向上执行下滤操作，每次操作都保证了以当前结点为根的子树满足堆的要求
for (int i = n / 2; i; i -- ) down(i);
7. 哈希表
7.1 模拟哈希表
哈希函数均是对$N$取模， $N$需要时质数
开放寻址法：
线性探测再散列，每次位置有数据时，就挨个往下找，直到有一个空位
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
链式存储法
这里用邻接表来存数据
记得链表头数组要初始化 memset(h, -1, sizeof -1)
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
7.2 字符串哈希
字符串哈希，是将每一位字符（的ASCII码）当做一个$P$进制的数，最后将字符串表示的$P$进制数字对$N$取模，模下来的就是我们哈希出来的数字
字符串哈希的时候，我们不考虑冲突，默认人品是足够好的，给出的方法能在$99$%+的情况下避免冲突
映射后不能为0，映射为0是一定会冲突的，A为0，那AA、AAA都会是0
$P$一般取131或者13331
$N$可以取$2 ^ {64}$，我们如果用$unsigned$ $long$ $long$ 存储数据，就不用手动取模了，溢出操作就会自动取模
8. stl简述
vector（变长数组），倍增的思想，支持比较运算（按字典序）
定义：：
vector <int> a; 定义：一个vector数组a
vector <int> a(10); 定义：一个长度为10的vector数组a
vector <int> a(10,3); 定义：一个长度为10的vector数组a，并且所有元素都为3
常用函数：：
size(); 返回元素个数
empty(); 返回是否是空
clear(); 清空
front(); 返回vector的第一个数
back(); 返回vector的最后一个数
push_back(); 向vector的最后插入一个数
pop_back(); 把vector的最后一个数删掉
begin(); vector的第0个数
end(); vector的最后一个的数的后面一个数
倍增的思想：
系统为某一程序分配空间是，所需时间，与空间大小无关，与申请次数有关
遍历方法
假设有个vector <int> a;
第一种：
for(int i = 0;i < a.size();i ++) cout<<a[i]<<" ";
第二种：
for(vector <int>::iterator i = a.begin();i != a.end();i ++) cout<<*i<<" "; vector <int>::iterator可以写为auto
第三种：
for(auto x : a) cout<<x<<" ";
pair，支持比较运算，以first为第一关键字，以second为第二关键字（按字典序）
定义：：
pair <类型,类型> 变量名; 两个类型可以不同
初始化方式：
假设有个pair <int,string> p;
第一种：
p = make_pair(10,"abc");
第二种：
p = {10,"abc");
常用函数：：
first(); 第一个元素
second(); 第二个元素
string（字符串）
常用函数：：
substr(); 返回每一个子串
c_str(); 返回这个string对应的字符数组的头指针
size(); 返回字母个数
length(); 返回字母个数
empty(); 返回字符串是否为空
clear(); 把字符串清空
queue（队列）
定义：：
queue <类型> 变量名;
常用函数：：
size(); 这个队列的长度
empty(); 返回这个队列是否为空
push(); 往队尾插入一个元素
front(); 返回队头元素
back(); 返回队尾元素
pop(); 把队头弹出
注意：队列没有clear函数！！！
清空：
变量名 = queue <int> ();
priority_queue（优先队列，堆）
注意：默认是大根堆！！！
定义：：
大根堆：priority_queue <类型> 变量名;
小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
常用函数：
size(); 这个堆的长度
empty(); 返回这个堆是否为空
push();往堆里插入一个元素
top(); 返回堆顶元素
pop(); 弹出堆顶元素
注意：堆没有clear函数！！！
stack（栈）
常用函数：
size(); 这个栈的长度
empty(); 返回这个栈是否为空
push(); 向栈顶插入一个元素
top(); 返回栈顶元素
pop(); 弹出栈顶元素
deque（双端队列）
常用函数：
size(); 这个双端队列的长度
empty(); 返回这个双端队列是否为空
clear(); 清空这个双端队列
front(); 返回第一个元素
back(); 返回最后一个元素
push_back(); 向最后插入一个元素
pop_back(); 弹出最后一个元素
push_front(); 向队首插入一个元素
pop_front(); 弹出第一个元素
begin(); 双端队列的第0个数
end(); 双端队列的最后一个的数的后面一个数
set，map，multiset，multimap 基于平衡二叉树（红黑树），动态维护有序序列
set/multiset
注意：set不允许元素重复，如果有重复就会被忽略，但multiset允许！！！
常用函数：
size(); 返回元素个数
empty(); 返回set是否是空的
clear(); 清空
begin(); 第0个数，支持++或--，返回前驱和后继
end(); 最后一个的数的后面一个数，支持++或--，返回前驱和后继
insert(); 插入一个数
find(); 查找一个数
count(); 返回某一个数的个数
erase();
（1）输入是一个数x，删除所有x O(k + log n)
（2）输入一个迭代器，删除这个迭代器
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器
map/multimap
常用函数：
insert(); 插入一个数，插入的数是一个pair
erase();
（1）输入是pair
（2）输入一个迭代器，删除这个迭代器
find(); 查找一个数
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器
unordered_set，unordered_map，unordered_muliset,unordered_multimap 基于哈希表
和上面类似，增删改查的时间复杂度是O(1)
不支持lower_bound()和upper_bound()
bitset 压位
定义：
bitset <个数> 变量名;
支持：
~，&，|，^
>>，<<
==，!=
[]
常用函数：
count(); 返回某一个数的个数
any(); 判断是否至少有一个1
none(); 判断是否全为0
set(); 把所有位置赋值为1
set(k,v); 将第k位变成v
reset(); 把所有位变成0
flip(); 把所有位取反，等价于~
flip(k); 把第k位取反
棒~