C++算法（数据结构）版

有些题目不是完整的题目，如需查看完整的题目请移步到acwing的算法基础课中

单链表

链表：

（单向）链表是由节点和指针构成的数据结构，每个节点存有一个值，和下一个指向下一个节点的指针，因此很多的链表问题可以用递归来处理。链表不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值

基本操作：

在链表头部插入 / 删除一个数

在链表尾部插入 / 删除一个数

在链表中间插入 / 删除 一个数

• 单链表（邻接表）常用于存储图和树

题目：

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的一个数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

完整题目：（https://www.acwing.com/problem/content/description/828/）acwing算法基础课

思路：

插入操作：

• 当链表为空时，idx = 0
• 当插入第一个元素后(设第一个插入的元素为 a ) 则，e[0] = a , idx = 1
• 当插入第二个元素后(设第二个插入的元素为 b ) 则，e[1] = b , idx = 2
• 当插入第三个元素后(设第三个插入的元素为 c ) 则，e[2] = c , idx = 3
• 当插入第四个元素后(设第四个插入的元素为 d ) 则，e[3] = d , idx = 4

所以；第 K 个插入的数的索引值为 k - 1

删除加插入操作：

• 当链表为空时，idx = 0
• 插入第一个元素 a 后：e[0] = a, idx = 1，
• 插入第二个元素 b 后：e[1] = b, idx = 2,
• 删除第一个插入的元素 a：head 变为 1， idx 不变，= 2。
• 删除第二个插入的元素 b：head 变为 2， idx 不变，=2。
• 插入第三个元素 c 后：e[2] = c, idx = 3。

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N  = 100010;int head,idx;
int ne[N],e[N];void init()
{head = -1;idx = 0;
}void add_to_head(int x)
{e[idx] = x;ne[idx] = head;head = idx++;
}void add(int k,int x)
{e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}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) head = ne[head];remove(k - 1);  //第k个元素对应的索引为k - 1}else{cin>>k>>x;add(k - 1,x);  //第k个元素对应的索引为k - 1}}for(int i = head;i != -1;i = ne[i])cout<<e[i]<<" ";cout<<endl;return 0;}

总结模板：（acwing——Y总的）

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;// 初始化
void init()
{head = -1;idx = 0;
}// 在链表头插入一个数a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}// 将头结点删除，需要保证头结点存在
void remove()
{head = ne[head];
}

双链表

题目：

实现一个双链表，双链表初始为空，支持 5 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 x。
2. R x，表示在链表的最右端插入数 x。
3. D k，表示将第 k 个插入的数删除。
4. IL k x，表示在第 k 个插入的数左侧插入一个数。
5. IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

思路：

和上面的单链表差不多

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;int idx;
int l[N],r[N],e[N];void init()
{//0表示左端点，1表示右端点l[1] = 0;r[0] = 1;idx = 2;
}//在下标是k的点的右边，插入xl[idx] = 
void add(int k,int x)
{e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;idx++;
}void remove(int k)
{r[l[k]] = r[k];l[r[k]] = l[k];
}int main()
{int m;cin>>m;init();while(m--){int k,x;string op;cin>>op;if(op == "L"){cin>>x;add(0,x);}else if(op == "R"){cin>>x;add(l[1],x);}else if(op == "D"){cin>>k;remove(k + 1);}else if(op == "IL"){cin>>k>>x;add(l[k + 1],x);}else{cin>>k>>x;add(k + 1,x);}}for(int i = r[0]; i != 1;i = r[i])cout<<e[i]<<" ";return 0;
}

总结模板：（acwing——Y总的）

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;// 初始化
void init()
{//0是左端点，1是右端点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. push x – 向栈顶插入一个数 x；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果

完整题目：（https://www.acwing.com/problem/content/description/830/） acwing算法基础课

思路：

有数组来模拟栈：

• 用top表示栈顶所在的索引。初始时，top = -1。表示没有元素。

• push x ：入栈 ，st[++top] = x。

• pop : 出栈， top–。

• empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”

• query ： 返回栈顶元素。st[top]

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;
int st[N];
int top = -1;int main()
{int m;cin>>m;while(m--){string op;cin>>op;if(op == "push"){int x;cin>>x;st[++top] = x;}if(op == "pop"){top--;}if(op == "empty"){cout<<(top == -1 ? "YES": "NO")<<endl;}if(op == "query"){cout<<st[top]<<endl;}}return 0;
}

总结模板：（acwing——Y总的）

// tt表示栈顶
int stk[N], tt = 0;// 向栈顶插入一个数
stk[ ++ tt] = x;// 从栈顶弹出一个数
tt -- ;// 栈顶的值
stk[tt];// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}

队列

队列：是一个特殊的数组。最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素。

题目;

实现一个队列，队列初始为空，支持四种操作：

1. push x – 向队尾插入一个数 x；
2. pop – 从队头弹出一个数；
3. empty – 判断队列是否为空；
4. query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

完整题目：（https://www.acwing.com/problem/content/description/831/）

思路：

• 用一个数组 q 保存数据。

• 用 hh 代表队头，q[hh] 就是队头元素， 用 tt 代表队尾， q[tt] 就是队尾元素

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;
int hh =0;
int tt = -1;
int q[N];int m;
string s;void push(int x)
{q[++tt] = x;
}void pop()
{hh++;
}void empty()
{if(tt >= hh)cout<<"NO"<<endl;else cout<<"YES"<<endl;
}void query()
{cout<<q[hh]<<endl;
}int main()
{cin>>m;while(m--){cin>>s;if(s == "push"){int x;cin>>x;push(x);}if(s == "pop"){pop();}if(s == "empty"){empty();}if(s == "query"){query();}}return 0;
}

总结模板：（acwing——Y总的）

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;// 向队尾插入一个数
q[ ++ tt] = x;// 从队头弹出一个数
hh ++ ;// 队头的值
q[hh];// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{}

这适用于普通队列，若是循环队列还需要加上

if (tt == N) tt = 0; 的判断条件

单调栈

单调栈是通过维持栈内值的单调递增（递减）性，在整体$o(n)$的时间内处理需要大小比较的问题。

题目：

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

思路：

• 用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素
• 我们只需要维护一个从栈顶到栈底单调递减的栈，每次不符合单调性就弹栈，最后输出栈顶即可，最后输出答案

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;int stk[N],tt;
int n;int main()
{cin>>n;for(int i = 0;i < n;i++){int x;cin>>x;while(tt && stk[tt] >= x) tt--;if(tt) cout<<stk[tt]<<' ';else cout<<-1<<' ';stk[++tt] = x;}return 0;
}

核心部分：

while(tt && stk[tt] >= x) tt--;
if(tt) cout<<stk[tt]<<' ';
else cout<<-1<<' ';stk[++tt] = x;

总结模板：（acwing——Y总的）

//常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i;
}

单调队列

题目：

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

思路：

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 1000010;int n,k;
int hh = 0,tt = -1;
int q[N],a[N];int main()
{scanf("%d%d",&n,&k);for(int i = 0;i < n;i++){scanf("%d",&a[i]);//移除窗口外的元素（队首出队）if( i - k +1 > q[hh])  ++hh;  // 若队首出窗口，hh加1//维护队列单调性（保证队列递增）while(hh <= tt && a[i] <= a[q[tt]]) --tt;   // 若队尾不单调，tt减1q[++tt] = i;    // 当前元素入队，下标加到队尾if(i + 1 >= k)printf("%d ",a[q[hh]]);   // 输出结果}printf("\n");hh = 0,tt = -1;for (int i = 0; i < n; ++ i){if (i - k + 1 > q[hh]) ++ hh;//维护队列单调性（保证队列递减）while (hh <= tt && a[i] >= a[q[tt]]) -- tt;q[++ tt] = i;if (i + 1 >= k) printf("%d ", a[q[hh]]);}printf("\n");return 0;
}

总结模板：（acwing——Y总的）

//常见模型：找出滑动窗口中的最大值/最小值
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;
}

KMP

• KMP 算法常用于解决「模式串在文本串中是否存在匹配」的问题

题目：

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

思路：

求next数组 , 利用Next数组避免回溯 , 匹配字符串

实现代码：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010, M = 1000010;int n, m;
char p[N], s[M];
int Next[N];int main() 
{cin >> n >> p + 1 >> m >> s + 1;for (int i = 2, j = 0; i <= n; i++) {// 若当前字符不匹配，通过Next数组回溯j到上一个可能匹配的位置while (j && p[i] != p[j + 1]) j = Next[j];// 若匹配，j后移（延长前缀后缀的匹配长度）if (p[i] == p[j + 1]) j++;// 记录当前位置的最长匹配长度Next[i] = j;}for (int i = 1, j = 0; i <= m; i++){// 若不匹配，根据Next数组将j跳转到合适位置（避免i回溯）while (j && s[i] != p[j + 1]) j = Next[j];if (s[i] == p[j + 1]) j++;if (j == n) {printf("%d ", i - n); j = Next[j];}}return 0;
}

总结模板：（acwing——Y总的）

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的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;
}// 匹配
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){j = ne[j];// 匹配成功后的逻辑}
}

Trie

• Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构

题目：

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

完整题目：（https://www.acwing.com/problem/content/837/）acwing 算法基础课

思路：

Trie 树中每个节点存储一个字符，从根节点到叶节点的一条路径存储一个字符串。

实现代码：

#include<iostream>using namespace std;const int N = 100010;char str[N];
int cnt[N],idx,son[N][26];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];   //使“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];  //返回字符串出现的次数
}int main()
{int n;cin>>n;while(n--){char op[2];scanf("%s%s",op,str);if(op[0] == 'I')insert(str);elseprintf("%d\n",query(str));}return 0;
}

总结模板：（acwing——Y总的）

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// 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] ++ ;
}// 查询字符串出现的次数
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];
}

并查集

并查集可以动态的连通两个点，并且可以非常快速的判断两个点是否连通

题目：

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1 ≤ n,m ≤ $10^5$

思路：

基本原理：

每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示它的父节点

实现代码：

#include<iostream>using namespace std;const int N = 100010;int n,m;
int p[N];int find(int x)
{if(x != p[x])p[x] =  find(p[x]);return p[x];
}void merge(int a,int b)
{int pa = find(a);int pb = find(b);if(pa != pb)p[pa] = pb;}void query(int a,int b)
{int pa = find(a);int pb = find(b);if(pa == pb) cout<<"Yes"<<endl;else cout<<"No"<<endl;return ;
}int main()
{cin>>n>>m;for(int i = 1;i <= n;i++)p[i] = i;while(m--){char op;cin>>op;int a,b;cin>>a>>b;if(op == 'M'){merge(a,b);}else{query(a,b);}}return 0 ;
}

朴素并查集–总结模板：（acwing——Y总的）

int p[N]; //存储每个点的祖宗节点// 返回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;// 合并a和b所在的两个集合：
p[find(a)] = find(b);

堆

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为 $O(nlogn)$， 它也是不稳定排序。
• 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆。
• 每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。

题目：

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围

1 ≤ m ≤ n ≤ $10^5$

思路：

1. 将序列构造成一个大顶堆，再将其与末尾元素进行交换， 此时末尾就为最大值。
2. 然后将剩余元素重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了。

实现代码：

#include<iostream>using namespace std;const int N = 100010;int n,m;
int cnt;
int a[N];void down(int u)
{//t记录最小点的编号int t = u;//有左儿子，并且左儿子比t节点的值小，更新tif(2 * u <= cnt && a[2 * u] < a[t]) t = 2 * u;//有右儿子，并且右儿子比t节点的值小，更新tif(2 * u + 1 <= cnt && a[2 * u + 1] < a[t]) t = 2 * u + 1;if(u != t){swap(a[u],a[t]);down(t);}}int main()
{cin>>n>>m;cnt = n;for(int i = 1;i <= n;i++)cin>>a[i];//从第一个非叶节点开始，从右到左，从下到上处理每个节点for(int i = n / 2;i >= 1;i--)down(i);while(m--){cout<<a[1]<<" ";swap(a[1],a[cnt]);//右边界左移cnt--;down(1);}return 0;
}

总结模板：（acwing——Y总的）

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
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] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希表

• 哈希表（hash table,hash map）,又称散列列表，使用O(n)空间复杂度存储数据，通过哈希函数映射位置，从而实现近似O(1)时间复杂度的插入，查找，删除等操作。哈希表可以用来统计频率，记录内容等等
• 如果元素有穷，并且范围不大，那么可以用一个固定大小的数组来存储或统计元素。

Hash表的主要基本操作：

1. 计算Hash函数的值
2. 定位到对应链表中依次遍历，比较

常用方法：

拉链法

开放寻址法

拉链法代码模板–总结模板：（acwing——Y总的）

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;
}

开放寻址法代码模板–总结模板：（acwing——Y总的）

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;
}