©2020-2024 ioDraw All rights reserved
1.链表与邻接表：树与图的存储
我们将结构体和指针结合来实现链表
struct Node { int val; Node * next; }; new Node;//这样创建结点是相当慢的
我们算法主要是用数组来模拟链表，这样效率会高一些。
数组模拟单链表
邻接表：存储图和树
实现一个单链表，链表初始为空，支持三种操作：
*
向链表头插入一个数
*
删除第k个插入的数后面的数
*
在第k个前面插入一个数
#include<iostream> using namespace std; const int N = 100010;
//head为头结点的下标 //e[i]表示节点i的值 //ne[i]表示节点i的节点next指针 //idx存储当前已经使用到的点的位置 int
head, idx, e[N], ne[N]; void init() { head = -1; idx = 0; }
//将x插入到头结点 void add_to_head(int x) { e[idx] = x; ne[idx] = head; head
= idx; idx++; } //将x插入到k的节点位置 void add(int k, int x) { e[idx] = x;
ne[idx] = ne[k]; ne[k] = idx; idx++; } //将k后面的点去掉 void remove(int k) {
ne[k] = ne[ne[k]]; } int main() { int m; cin >> m; init();
while(m--) { int k, x; char op; cin >> op;
if(op == 'H') { cin >> x; add_to_head(x);
} else if(op == 'D') { cin >> k; if(k ==
0) head = ne[head]; remove(k-1); } else {
cin >> k >> x; add(k-1, x); } } for(int i = head;i
!= -1;i = ne[i]) { cout << e[i] << ' '; } return 0; }
数组模拟双链表的模板：
#include<iostream> using namespace std; const int N = 100010; int m; int
e[N], l[N], r[N], idx; void init() { //0表示左端点，1表示右端点 r[0] = 1, l[1] =
0; idx = 2; } //在下标的k的右边插入x void add(int k, int x) { e[idx] = x;
r[idx] = r[k]; l[idx] = k; l[r[k]] = idx; r[k] = idx; } //删除第k个点
void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; }
2.栈与队列：单调队列、单调栈
栈是先进后出，队列是先进先出。
数组实现栈：
#include<iostream> using namespace std; const int N = 100010; int stk[N],
tt; //插入stk[++tt] = x; //弹出tt--; //判断栈是否为空 if(tt>0) 不为空，否则为空 //栈顶
stk[tt];
数组实现队列
#include<iostream> using namespace std; //在队尾插入元素，在队头弹出元素 int q[N], hh, tt =
-1; //判断队列是否为空 if(hh <= tt) not empty; else empty; //取出队头、队尾元素 q[hh]; q[tt];
单调栈例题：
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 -1。
int tt; for(int i = 1;i <= n; i++) { while(tt && check(q[tt], i)) t--;
stk[++tt] = i; }
题目代码：
#include<iostream> using namespace std; const int N = 1e5 + 10; int n; int
q[N], tt; int main() { scanf("%d", &n); for(int i = 0;i < n; i++) {
int x; scanf("%d",&x); while(tt && stk[tt] >= x) tt--;
if(tt) printf("%d ",stk[tt]); else printf("-1 ");
stk[++tt] = x; } return 0; }
只有出栈和入栈两次操作，所以它的时间复杂度为O(n)
单调队列例题：
移动窗口的例题，k为窗口大小且k=3，打印出三个数中最小数，如果窗口下数不足，则输出-1
1 3 -1 -3 5 3 6 7
由上面的例子我们可以知道在3 -1 -3这个序列中3绝对不可能为最小值，-3的生命周期要比3长。我们要优化该形式，可以用单调队列的形式，将不满足的点删掉。
我们的队列里存的不是值而是下标。
int hh = 0, tt = 1; for(int i = 0;i < n; i++) { if(hh <= tt &&
check_out(q[hh])) hh++; while(hh <= tt && check(q[tt],i)) tt--; q[++tt] =
i; }
本题代码
#include<iostream> using namespace std; const int N = 1e6 + 10; int n,k;
int a[N], q[N]; int main() { scanf("%d%d", &n, &k); for(int i = 0;i
< n; i++) { scanf("%d", &a[i]); } int hh = 0, tt = -1;
for(int i = 0;i < n; i++) { //判断队头是否已经超出滑出窗口 if(hh <= tt && i
- k + 1 > q[hh]) hh++; while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i; if(i >= k - 1) printf("%d ", a[q[hh]]); }
printf(""); return 0; }
3.kmp算法
KMP算法是一种字符串匹配算法，用于在一个字符串中查找另一个字符串出现的位置。它的全名是Knuth-Morris-Pratt算法，是由Donald
Knuth、James H. Morris和Victor S. Pratt三人共同发明的。
S[N]，p[M]我们如果用暴力算法（朴素做法）来做的话，代码如下：
for(int i = 1;i <= n; i++) { bool flag = true; for(int j = 1;j <= m;
j++) { if(s[i] != p[j]) { flag = false;
break; } } }
KMP算法的思想是在匹配过程中，尽量利用已经匹配过的信息来快速跳过不匹配的位置，从而达到减少匹配次数和提高匹配效率的目的。具体来说，它通过预处理出一个next数组，来记录匹配模式串中每个位置上最长的相同前缀和后缀的长度。在匹配过程中，如果发现当前字符不匹配，就可以利用next数组中记录的信息，快速地将模式串向右移动一定的距离，而无需重新从头开始匹配。
KMP算法的时间复杂度为O(m+n)，其中m和n分别为匹配串和模式串的长度。相比于暴力匹配算法，KMP算法可以在很大程度上减少匹配的次数，从而提高匹配的效率。但是，KMP算法的实现比较复杂，需要对next数组进行正确的计算和处理，因此在实际应用中需要仔细考虑其实现方式和适用场景。
next[i] = j， p[1, j] = p[i - j + 1, i]
acwing的KMP算法例题
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串P在模式串S中多次作为子串出现。求出模板串P在模式串S中所有出现的位置的起始下标。
输入样例：3 aba 5 ababa 输出：0 2
代码：
#include<iostream> using namespace std; const int N = 1e4 + 10, M = 1e5 +
10; int n, m; char p[N], s[M]; int ne[N]; int main() { cin >> n >> p + 1
>> m >> s + 1; //求next的过程 for(int i = 2, j = 0;i <= n; i++) {
while(j && p[i] != p[j + 1]) j = ne[j]; if(p[i] == p[j + 1]) j++;
ne[i] = j; } //kmp的匹配过程 for(int i = 1, j = 0;i <= m; i++) {
while(j && s[i] != p[j + 1]) j = ne[j]; if(s[i] == p[j + 1]) j++;
if(j == n) { //匹配成功 printf("%d ",i - n);
j = ne[j]; } } return 0; }
4.Trie树
Trie（又称前缀树或字典树）是一种基于树结构的数据结构，用于快速地检索和插入字符串。Trie的每个节点代表一个字符串的前缀，从根节点到叶子节点的路径上表示一个完整的字符串。
Trie的特点是它的每个节点都有多个子节点，每个子节点代表一个字符。根节点没有父节点，每个非叶子节点的子节点数等于它的编号（从0开始）减去1。
在Trie中，插入一个字符串的操作是从根节点开始，按照字符串的字符顺序依次遍历每个字符，如果当前节点的子节点中没有对应字符，就新建一个子节点，并将当前节点移动到该子节点。如果已经遍历到字符串的末尾，则说明该字符串已经成功插入到Trie中。
Trie的另一个常见操作是查找一个字符串是否存在于Trie中。从根节点开始，按照字符串的字符顺序依次遍历每个字符，如果当前节点的子节点中没有对应字符，则说明该字符串不存在于Trie中。如果已经遍历到字符串的末尾，且当前节点是一个叶子节点，则说明该字符串存在于Trie中。
Trie的主要优势是它可以快速地检索和插入字符串，时间复杂度为O(m)，其中m为字符串的长度。但是，由于Trie的每个节点都需要存储多个子节点，因此它的空间复杂度比较高，适用于数据规模较小的情况。在大数据处理和文本处理等领域，Trie通常被用来实现词典和关键字过滤等功能。
trie字符串统计：
维护一个字符串集合，支持两种操作：
*
‘lx’向集合中插入一个字符串x
*
‘Qx’询问一个字符串在集合中出现了多少次
一共有N次操作，输入的字符串总长度不超过105，字符串仅包含小写英文字母。
#include<iostream> using namespace std; const int N = 1e5 + 10; int
son[N][26], cnt[N], idx;//下标是0的点，既是根节点，有是空节点 int str[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; p = son[p][u]; }
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]; } int main() { int n;
scanf("%d", &n); while(n--) { char op[2]; scanf("%s%s", op,
str); if(op == 'I') insert(str); else printf("%d\n", query(str));
} return 0; }
最大异或对
5.并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
*
将两个集合合并
*
询问两个元素是否在一个集合当中。
基本原理：每隔几何用一棵树来表示，树根的编号就是一整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。
问题1：如何判断树根：if(p[x] == x);
问题2：如何求x的集合编号：while(p[x] != x) x = p[x];
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y
基本上来说是O(1)的时间复杂度
合并集合：
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作一共有两种
*
将编号为a，b的两个数所在集合进行合并，如果两个数已经在集合中，即忽略这个操作
*
询问编号为a，b的两个数是否在同一个集合中
#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m;
int p[N]; int find(int x)//返回x的祖宗结点+路径压缩 { if(p[x] != x) p[x] =
find(p[x]); return p[x]; } void merge(int a, int b) { p[find(a)] =
find(b); } int main() { scanf("%d%d", &n, &m); for(int i = 1;i <=
n; i++) p[i] = i; while(m--) { char op[2]; int a, b;
scanf("%s%d%d", op, &a, &b); if(op[0] == 'M')
merge(a, b); else { if(find(a) == find(b))
printf("Yes\n"); else printf("No\n"); } }
return 0; }
近乎O(1)的时间
连通块中点的数量：
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作一共有三个：
*
“Cab”，在点a和点b之间连一条边，a和b可能相等
*
“Q1ab”，询问点a和点b是否在同一连通块内，a和b可能相等
*
“Q2ab”，询问点a所在的联通快中点的个数。
#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m;
int p[N], size[N]; int find(int x) { if(p[x] != x) p[x] = find(p[x]);
return p[x]; } void merge(int a, int b) { p[find(a)] = find(b); } int
main() { scanf("%d%d", &n, &m); for(int i = 1;i <= n; i++) {
p[i] = i; size[i] = 1; } while(m--) { char op[5];
int a, b; scanf("%s", op); if(op[0] == 'C')
{ scanf("%d%d", &a, &b); if(find(a) == find(b))
continue; size[find(b)] += size[find(a)]; merge(a, b);
} else if(op[1] == '1') { scanf("%d%d", &a, &b);
if(find(a) == find(b)) printf("Yes\n"); else
printf("No\n"); } else {
scanf("%d", &a); printf("%d\n", size[find(a)]); } }
return 0; }
食物链
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话； 2） 当前的话中X或Y比N大，就是假话； 3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
#include<iostream> using namespace std; int main() { return 0; }
6.堆
如何手写一个堆？
堆是维护数与集合。
堆是一种数据结构，它满足以下两个条件：
*
完全二叉树：堆的总是一棵完全二叉树，即除了最后一层外，其他层都是满的，并且最后一层的节点都集中在左侧。
*
堆性质：对于每个节点X，其父节点的值小于等于（或大于等于，称为最小堆）其子节点的值。
堆通常用于实现优先队列，其中每个节点代表一个事件或任务，节点的值表示任务的优先级。通过将任务按照优先级从上到下放置在堆中，可以保证优先级最高的任务总是最先被执行。
在实现上，堆可以使用数组来表示。对于一个节点X，其父节点和子节点的位置可以通过简单的数学计算来确定。例如，对于一个最小堆，节点X的父节点和左子节点的位置可以通过以下公式计算：
*
父节点位置：parent(X) = (X-1)/2
*
左子节点位置：left_child(X) = 2*X + 1
堆也可以用来实现优先级调度、任务调度等应用。
*
插入一个数 heap[++size] = x; up(size);
*
求集合当中的最小值 heap[1];
*
删除最小值 用最后一个元素覆盖根节点 heap[1] = heap[size];size--;down(1);
*
删除任意元素 heap[k] = heap[size];size--;
*
修改任意元素 heap[k] = x; down(k); up(k);
838.堆排序：
输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式：第一行包含整数n和m，第二行包含n个整数，表示整数数列。
输出格式：共一行，包含m个整数，表示整数数列中前m小的数。
5 3 \n 4 5 1 3 2
1 2 3
代码：
#include<iostream> #include<algorithm> using namespace std; const int N =
1e5 + 10; int n, m; int h[N], size; void down(int u) { int t = u;
if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if(u * 2 + 1 <= size && h[u
* 2 + 1] < h[t]) t = u * 2 + 1; if(u != t) { swap(h[u], h[t]);
down(t); } } int main() { scanf("%d%d", &n, &m); for(int i = 1;i
<= n; i++) scanf("%d", &h[i]); size = n; for(int i = n / 2; i;
i--) down(i); while(m--) { printf("%d ", h[1]); h[1] =
h[size]; size--; down(1); } return 0; }
839.模拟堆：
维护一个集合，初始时集合为空，支持如下几种操作：
*
"lx"，插入一个数x；
*
“PM”，输出当前集合中的最小值；
*
“DM”，删除当前集合的最小值（当最小值不唯一时，删除最早插入的最小值）；
*
“Dk”，删除第k个插入的数；
*
“Ckx”，修改第k个插入的数，将其变为x；
现在要进行N次操作。对于所有第2个操作，输出当前集合的是小值。
#include<iostream> #include<algorithm> #include<string.h> using namespace
std; const int N = 1e5 + 10; int h[N], ph[N], hp[N], size; void
heap_swap(int a, int b) { swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]);
swap(h[a], h[b]); } void down(int u) { int t = u; if(u * 2 <= size
&& h[u * 2] < h[t]) t = u * 2; if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t])
t = u * 2 + 1; if(u != t) { heap_swap(u, t); down(t); } }
void up(int u) { while(u / 2 && h[u / 2] > h[u]) { heap_swap(u /
2, u); u /= 2; } } int main() { int n, m = 0; scanf("%d", &n);
while(n--) { char op[10]; int k, x;
scanf("%s", op); if(!strcmp(op, "I")) { scanf("%d",
&x); size++; m++; ph[m] = size, hp[size] = m;
h[size] = x; up(size); } else if(!strcmp(op,
"PM")) printf("%d\n", h[1]); else if(!strcmp(op, "DM")) {
heap_swap(1, size); size--; down(1); }
else if(!strcmp(op, "D")) { scanf("%d", &k); k =
ph[k]; heap_swap(k, size); size--; down(k),
up(k); } else { scanf("%d%d", &k, &x);
k = ph[k]; h[k] = x; down(k), up(k); } }
return 0; }
7.Hash表
哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。
哈希表可以用来实现动态集合。它支持以下操作：
*
插入：将一个元素插入到哈希表中。
*
删除：将一个元素从哈希表中删除。
*
搜索：在哈希表中查找一个元素。
哈希表的实现基于哈希函数，它将键映射到存储桶（bucket）中。每个存储桶是一个链表，链表中的每个节点都包含一个键值对。当插入一个元素时，哈希函数将键映射到一个存储桶，然后将元素添加到该存储桶的链表中。当搜索一个元素时，哈希函数将键映射到相应的存储桶，然后在该存储桶的链表中查找元素。
哈希表有多种实现方式，其中最常用的是开放地址法和相联数组法。开放地址法在哈希表中使用一个数组来存储存储桶，当发生哈希冲突时，它使用线性探测、二次探测、双重散列等方法来找到空槽位。相联数组法在哈希表中直接使用一个数组来存储键值对，当发生哈希冲突时，它将新元素添加到数组的末尾。
哈希表在计算机科学中广泛应用，例如在数据库、操作系统、网络通信等领域。它能够提供常数级别的查找效率，比其他数据结构更高效。
7.1哈希表的存储结构
1.开放寻址法 2.拉链法
840.模拟散列表
维护一个集合，支持如下几种操作：
*
“lx”，插入一个数
*
“Qx”，询问数x是否在集合中出现过
现在要进行N次操作，对于每个询问操作输出对应的结果
一般情况下，对哈希函数进行取模，但是由于取模的原因，可能会有冲突，若干不同的数可能会映射在同一个位置。
开放寻址法：
#include<iostream> #include<cstring> using namespace std; cosnt int N =
200003, null = 0x3f3f3f3f; int h[N]; int find(int n) { int t = (x % N +
N) % N; while(h[t] != null && h[t] != x) { t++; if(t ==
N) t = 0; } return t; } int main() { int n;
scanf("%d", &n); merset(h, 0x3f, sizeof(h)); while(n--) {
char op[2]; int x; scanf("%s%d", op, &x); int k =
find(x); if (op == 'I') { h[k] = x; } else
{ if (h[k] != null) puts("Yes");
else puts("No"); } } return 0; }
拉链法：
#include<iostream> #include<cstring> using namespace std; const int N =
100003; 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; else return false;
} int main() { int n; scanf("%d", &n); memset(h, -1, sizeof(h));
while(n--) { char op[2]; int x; scanf("%s%d", op,
&x); if(op == "I") insert(x); else {
if(find(x)) puts("Yes"); else puts("No"); } } return 0; }
7.2.字符串前缀哈希方法
str = "ABCDEFADCYUGHJJDFDGKHJK"
预处理：特殊h[0] = 0
h[1] = "A"的对应的哈希值，后面的一样 h[2] = "AB" h[3] = "ABC".....
*
不能映射为0
*
Rp足够好，不产生冲突
841.字符串哈希
给定个长度为的字符串，再给定m个询问，每个询问包含四个整数l1，r1，l2，r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
#include<iostream> using namespace std; typedef unsigned long long ULL;
const int N = 100010; int n, m; char str[N]; ULL h[N], p[N]; ULL get(int l,
int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() {
scanf("%d%d%s", &n, &m, str + 1); p[0] = 1; for(int i = 1;i <= n;
i++) { p[i] = p[i-1] * p; h[i] = h[i-1] * p + str[i]; }
while(m--) { int l1, r1, l2, r2; scanf("%d%d%d%d",&l1, &r1,
&l2, &r2); if(get(l1, r1) == get(l2, r2))
puts("Yes"); else puts("No"); } return 0; }
8.C++STL使用技巧
vector：变长数组，倍增的思想
string：字符串，substr()，c_str()
queue：队列，push(), front(), pop()
priority_queue：优先队列，push()， top()，pop()
stack：栈，push(), top(), pop()
deque：双增队列
set, map, multiset和multimap：基于平衡二叉树，动态维护有序序列
unorder_set、unorder_map、unorder_multiset、unorder_multimap：基于哈希表
bitset：压位
list
#include<iostream> #include<algorithm> #include<vector> #include<cstring>
#include<cstdio> using namespace std; int main() { vector<int> a(10, 3);
//vector<int> a[10]; a.size();//返回元素个数 a.empty();//返回是否为空
a.clear();//清空 a.front();//返回第一个数 a.back();//返回最后一个数
a.push_back();//尾插 a.pop_back();//尾部释放 a.begin()/a.end();//vector的迭代器
for(int i = 0;i < 10; i++) a.push_back(); for(int i = 0;i <
a.size(); i++) cout << a[i] << ' '; cout << endl;
for(vector<int>::iterator i = a.begin();i != a.end(); i++) cout << a[i]
<< ' '; cout << endl; //支持比较运算 vector<int> a(4, 3), b(3, 4);
if(a > b) cout << "a > b" << endl; return 0; }
系统内某一程序分配空间时，所需时间，与空间大小无关，与中间次数有关
pair<int, int>：存储一个二元组
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio>
#include<vector> using namespace std; int main() { pair<int, string>p;
p.first; p.second; //支持比较运算 //以first为第一关键词，以second为第二关键词 p
= make_pair(10, "yxc"); p = {20, "abc"}; pair<int, pair<int>>w;
return 0; }
string
#include<iostream> #include<cstring> #include<algorithm> using namespace
std; int main() { string a = "yxc"; a += "def"; a += "c";
cout << a << endl; cout << a.substr(2, 3) << endl; return 0; }
queue队列
#include<iostream> #include<queue> #include<algorithm> #include<vector>
using namespace std; int main() { queue<int> q; q = queue<int>;
//优先队列 priority_queue<int> heap; heap.clear();
priority_queue<int, vector<int>, greater<int>> heap;//定义一个小根堆 return 0; }
stack栈
deque双端队列
size() empty() clear() front() back() push_front() pop_front() push_back
pop_back() begin() end()
缺点就是deque比较慢
set
#include<iostream> #include<vector> #include<set> #include<algorithm> using
namespace std; int main() { set<int> S; multiset<int>
S1;//可以有重复元素，set不允许 S.insert(1);//插入一个数 S.find();//查找一个数
S.count();//返回某一个数的个数 S.erase();//1.输入的是一个数，就删除该数的所有存储 2.输入一个迭代器，就删除这个迭代器
S.lower_bound(x);//返回大于等于x的最小的数的迭代器 S.upper_bound(x);//返回大于x的最小数的迭代器
return 0; }
map/multimap
insert()插入的数是一个pair erase()输入的参数是pair或者是迭代器 find()
[] 时间复杂度是O(nlogn) lower_bound() upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap
哈希表 和上面的类似，增删查改的时间复杂度是O(1)
不支持lower_bound()和upper_bound()，迭代器的++、--
bitset，压位
bitset<10000>S;~, &, |, ^, >>, <<, ==, !=,
count()返回有多少个1
any()判断是否至少有一个1
none()判断是否为0
set()把所有位置都换成1
reset()把所有位都变成0
flip()等价~ flip(k)把第k位反转。