常用代码模板2——数据结构
单链表
// head存储链表头节点的下标，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前可以用的最新的点的下标
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void add_to_head(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove_head()
{
head = ne[head];
}
// 将x插到下标是k的点后面
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
//打印：for(int i = head; i != -1; i = ne[i] ) cout << e[i] << ' ';
双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前可以用的最新的点的下标
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点，1是右端点
//0,1相当于是虚节点，只起到标识链表的开始和结束的作用，不存值
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x(a是节点的idx值，假如节点是第k个插入的数，那a = k + 1)
// 在最左端插入：insert(0, x);
// 在最右端插入：insert(l[1], 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];
}
//打印： for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
栈
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0) // tt > 0 为不空
{
}
队列
1. 普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 从队尾弹出一个数(模拟deque)
tt --;
// 队头的值
q[hh];
// 队尾的值
q[tt];
// 判断队列是否为空
if (hh <= tt) // hh <= tt 为不空
{
}
2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
// 少用一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)
{
}
// 判断队列是否满了
if (hh == (tt + 1) % N)
单调栈
// 先思考暴力做法，再挖掘单调性，考虑符合什么条件的元素是没用的，把它删掉
// 消除某种性质的逆序对
// 常见模型：找出每个数左边离它最近的比它大/小的数
// 步骤：弹栈（维护单调性）-> 新元素入栈
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
单调队列
// 先思考暴力做法，再挖掘单调性，考虑符合什么条件的元素是没用的，把它删掉
// 消除某种性质的逆序对
// 常见模型：找出滑动窗口中的最大值/最小值
// 步骤：队首出队（维护窗口长度）-> 队尾出队（维护单调性）-> 新元素入队
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 -- ; // hh用于维护队列长度， 所以要从队尾出队
q[ ++ tt] = i;
}
KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// s和q都从1开始存
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j; // 前缀为p[1~j]，所以长度为j
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m) //匹配成功
{
//此时i为母串中匹配成功的子串的终点
j = ne[j];
// 匹配成功后的逻辑
}
}
Trie树
trie树结构：
// 高效地存储和查找字符串集合的数据结构
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// idx表示当前可以用的最新的层数
// son[][]存储树中每个节点的子节点，这个节点的子节点要储存在哪一层，由idx分配，最多到N-1层，由于idx递增，所以每层只会存一个字母
// cnt[]存储以每个节点结尾的单词数量
// N要大于所有字符串的总长度
// 插入一个字符串
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; // 如果son[p][u]值为0，说明该节点为空，令其等于++idx，既创建了该节点，又分配该节点的子节点储存的层数
p = son[p][u]; // 移动到子节点的层数
}
cnt[p] ++ ; // 由于一个子节点只有一个父节点，所以能使p到达该层的字符串是唯一的，因此cnt[p]可以表示该字符串出现的次数
}
// 查询字符串出现的次数
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];
}
并查集
1. 朴素并查集
// 处理的问题：1.将两个集合合并 2.询问两个元素是否在一个集合当中
// 时间复杂度：最坏O(nlogn)
// 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号（即树根有p[x]==x）。每个节点储存它的父节点，p[x]表示x的父节点
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点 + 路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]); // 路径压缩
return p[x]; // 返回x的祖宗节点
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：（令a的祖宗节点的父节点为b的祖宗节点）
p[find(a)] = find(b);
// 判断两个点是否属于同一集合
if(find(a) == find(b))
{
}
2. 维护size的并查集
int p[N], cnt[N];
// p[]存储每个点的祖宗节点, cnt[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
cnt[i] = 1;
}
// 合并a和b所在的两个集合：
// if(find(a) == find(b)) 跳过，否则会size会自增
cnt[find(b)] += cnt[find(a)]; // 维护size
p[find(a)] = find(b);
3. 维护到祖宗节点距离的并查集
// 带权并查集精髓总结：只要两个元素在一个集合里面，通过它们与根节点的距离就能知道它们的相对关系。
int p[N], d[N];
// p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
堆
堆的结构：完全二叉树，父节点小于等于两个子节点，堆顶最小
// 处理的问题：寻找一组数里的最小值或最大值
// h[N]存储堆中的值, 下标从1开始，h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[idx]存储第idx个插入的点在堆中的下标(idx -> k)
// hp[k]存储堆中下标是k的点是第几个插入的(k -> idx)
// hsize是堆的大小
int h[N], ph[N], hp[N], hsize;
// 交换两个点，及其映射关系
void heap_swap(int a, int b) // 传入的是下标a,b
{
swap(ph[hp[a]],ph[hp[b]]); // 交换idx到k的映射关系
swap(hp[a], hp[b]); // 交换k到idx的映射关系
swap(h[a], h[b]); // 交换k到val的映射关系
}
// 一个数变大，下沉（与三个节点中的最小者交换）O(logn)
void down(int u) // 传入下标u
{
int t = u;
if (u * 2 <= hsize && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= hsize && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t); // swap(h[u], h[t]);
down(t);
}
}
// 一个数变小，上浮（与父节点比较）O(logn)
void up(int u) // 传入下标u
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2); // swap(h[u], h[u/2]);
u >>= 1;
}
}
// O(n)建堆
// 可以证明，对于一个节点数为n的完全二叉堆，第一层至倒数第二层的节点总数为n/2，且由下标在堆中的排列规律可知，n/2总是倒数第二层的最后一个节点。因此，由n/2开始down，可以使堆从右到左、从下到上建成
for (int i = n / 2; i; i -- ) down(i);
堆的操作：
1. 插入一个数
h[ ++ hsize] = x; up(hsize);
2. 求集合当中的最小值
h[1];
3. 删除最小值
h[1] = h[hsize]; hsize -- ; down(1);
// heap_swap(1, hsize), hsize -- , down(1);
4. 删除任意一个元素
h[k] = h[hsize]; hsize -- ; down(k); up(k);
// heap_swap(k, hsize), hsize -- , down(k), up(k);
5. 修改任意一个元素
h[k] = x; down(k); up(k);
一般哈希
拉链法图解
开放寻址法图解
// 把较大的值域(-1e9~1e9)映射到0~N(N为1e5/1e6, N为质数并离2的整次幂尽可能远)
// 操作：1. 插入一个数 2. 查找一个数
// 冲突：两个数取模后值相同，有两种处理方法
查找质数N
// val在拉链法中为数据项数，在开放寻址法中为数据项数的2~3倍
for (int i = val; ; i++)
{
bool flag = true;
for (int j = 2; j <= i / j; j ++ )
{
if(i % j == 0)
{
flag = false;
break;
}
}
if (flag)
{
cout << i;
break;
}
}
(1) 拉链法
// 每一个h[]是一个头指针，指向一条单链表
// idx是e[]和ne[]中当前可以用的最新的点的下标
int h[N], e[N], ne[N], idx;
// 将所有头指针初始化为指向空
memset(h, -1, sizeof(h));
// 向哈希表中插入一个数
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;
}
(2) 开放寻址法
// 先约定一个数null, 当h[]==null时, h[]为空
// 思路：先算哈希值，如果哈希值所在下标已经存数了，就往后找空位，找到空位就存下去，并返回空位的下标。如果找到数组的尽头还没有空位就移动到开头找。如果发现h[]是null，说明不存在这个数，此时的下标就是这个数可以存储的位置
int h[N];
// 数据范围为-1e9~1e9
const int null = 0x3f3f3f3f
memset(h, 0x3f, sizeof(h));
// 如果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;
}
字符串哈希
哈希值计算图解
get(int l, int r)原理图解
// 将字符串的逐位比较简化为它们的哈希值的比较，快速判断两个字符串是否相等
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低(哈希值为字符串作为P进制数化为十进制数后的结果模上一个数)
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
// ull的范围是0~2^64-1, 2^64-1的二进制为0到63位全1, 例如2^64溢出了, 二进制为0到63位为0, 第64位为1, 由于ull无符号, 则2^64会被解释为0, 就是2^64%2^64, 所以用ull来存储数据, 可以保证所有的数都是%2^64的结果
注意：字符串下标从1开始
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get_hash(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
C++ STL简介
1. vector
vector, 变长数组，倍增的思想
初始化：
vector <int> a;
vector <int> a(10); 一个长度为10的vector
vector <int> a(10,3); 长度为10，所有元素都为3
size() 返回元素个数 O(1)
empty() 返回是否为空 O(1)
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序 if(a < b){ }
2. pair
pair<int, int>
定义
pair <类型,类型> 变量名; 两个类型可以不同
初始化方式：
假设有个pair <int,string> p;
第一种：
p = make_pair(10,"abc");
第二种：
p = {10,"abc");
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
应用：
1. 存储有两种属性的东西，把要排序的属性存在first
2. 存储有三种属性的东西，pair<int, pair<char, int>>
3. 字符串
string，字符串
初始化：string a="initial";
支持 + =
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串，长度默认到结尾
查找子串：
pos = a.find(b, pos=0) // b可以是string或c-string
返回子串的起始下标，没有返回-1
示例：
string a="aaa";
auto pos = a.find("a");
while (pos != -1)
{
cout << pos << ' ';
pos = a.find("a", pos + 1);
}
c_str() 返回字符串所在字符数组的起始地址
示例：
printf("%s", a.c_str());
4. 队列
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
注意没有clear()!
清空：变量名 = queue <int> ();
5. 堆
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
注意没有clear()!
定义成小根堆的方式：
priority_queue<int, vector<int>, greater<int>> heap;
6. 栈
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
注意没有clear()!
7. 双端队列
deque, 双端队列, 效率低
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
8. set, map, multiset, multimap
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列,
size()
empty()
clear()
begin()/end()
支持 ++, -- ，时间复杂度 O(logn)
set/multiset (set不支持重复元素, multiset可以)
默认升序排列, 定义成降序：set<int, greater<int>>
insert() 插入一个数
find() 查找一个数, 不存在返回end()
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound() // 不存在则返回end()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 不存在的映射会直接创建出来。注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
first, 每一项的下标
second, 每一项的值
9. 哈希表
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
初始化：
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
不支持 lower_bound()/upper_bound()， 迭代器的++，--
10. bitset
bitset, 圧位，每一个字节存8位，使用的空间是bool数组的1/8
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 把所有位取反, 等价于~
flip(k) 把第k位取反