Acwing算法基础课第二讲总结（正在写）
目录
本讲主要内容
单链表，双链表，栈，队列，单调栈，单调队列，KMP，Tire，并查集，堆，哈希表。
单链表
Acwing-826 单链表
思路
模板题。代码中
head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+10;
int head, e[maxn], ne[maxn], idx; //idx充当题目中k的作用，但是注意是idx从0开始，而k从1开始，所以对应的用到k的地方需要减一
void init(void)
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
//插入到第k个数后
void add_to_back(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
int main(void)
{
int m;
cin >> m;
init();
while(m--)
{
char op;
cin >> op;
if(op == 'H')
{
int x;
cin >> x;
add_to_head(x);
}
else if(op == 'D')
{
int k;
cin >> k;
//k为0时删除头结点
if(k == 0) head = ne[head];
else remove(k - 1);
}
else if(op == 'I')
{
int k, x;
cin >> k >> x;
add_to_back(k-1, x);
}
}
for(int i = head; i != -1; i = ne[i] ) cout << e[i] << ' ';
cout << endl;
return 0;
}
双链表
Acwing-827 双链表
思路
模板题。代码中
e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
参考代码
#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5+10;
int e[maxn], l[maxn], r[maxn], idx;
void init(void)
{
//0是左端点，1是右端点
r[0] = 1;
l[1] = 0;
idx = 2;
}
// 在节点k的右边插入一个数x
void insert(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx++;
}
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
int main(void)
{
int m;
cin >> m;
init();
while(m--)
{
//这里注意定义为string，因为操作序列有字符串
string op;
cin >> op;
int k, x;
if(op == "L")
{
cin >> x;
insert(0, x); //最左端即为左端点后面插入
}
else if(op == "R")
{
cin >> x;
insert(l[1], x); //最右端插入即为右端点前插入
}
else if(op == "D")
{
cin >> k;
remove(k+1); //类比单链表，这里由于idx充当k的作用，且从2开始，而k从1开始，所以为idx比k多1
}
else if(op == "IL")
{
cin >> k >> x;
insert(l[k+1], x);
}
else
{
cin >> k >> x;
insert(k+1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
栈
Acwing-828 模拟栈
思路
模板题。
参考代码
#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5+10;
int stk[maxn], tt; //tt表示栈顶。这里的栈的下标是从1开始的，也可以从0开始
int main(void)
{
int m;
cin >> m;
string op;
while(m--)
{
cin >> op;
if(op == "push") // 向栈顶插入一个数
{
int x;
cin >> x;
stk[++tt] = x;
}
else if(op == "pop") // 从栈顶弹出一个数
{
tt--;
}
else if(op == "empty") // 判断栈是否为空
{
if(tt > 0) cout << "NO" << endl;
else cout << "YES" << endl;
}
else // 栈顶的值
{
cout << stk[tt] << endl;
}
}
return 0;
}
队列
Acwing-829 模拟队列
思路
模板题。
参考代码
普通队列
#include <iostream>
#include <string>
using namespace std;
// hh 表示队头，tt表示队尾
// 这里的队列起始坐标是从0开始的
const int maxn = 1e5+10;
int q[maxn], hh, tt = -1;
int main(void)
{
int m;
cin >> m;
string op;
while(m--)
{
cin >> op;
if(op == "push") // 向队尾插入一个数
{
int x;
cin >> x;
q[++tt] = x;
}
else if(op == "pop") // 从队头弹出一个数
{
hh++;
}
else if(op == "empty") // 判断队列是否为空
{
if(hh <= tt) cout << "NO" << endl;
else cout << "YES" << endl;
}
else // 队头的值
{
cout << q[hh] << endl;
}
}
return 0;
}
循环队列
#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5+10;
int q[maxn], hh, tt; //hh表示队头，tt表示队尾的后一个位置
int main(void)
{
int m;
cin >> m;
string op;
while(m--)
{
cin >> op;
if(op == "push") // 向队尾插入一个数
{
int x;
cin >> x;
q[tt++] = x; //注意这里的tt表示的是队尾的后一个位置
if(tt == maxn) tt = 0;
}
else if(op == "pop") // 从队头弹出一个数
{
hh++;
if(hh == maxn) hh = 0;
}
else if(op == "empty") // 判断队列是否为空
{
if(hh != tt) cout << "NO" << endl;
else cout << "YES" << endl;
}
else // 队头的值
{
cout << q[hh] << endl;
}
}
return 0;
}
单调栈
Acwing-830 单调栈
思路
模板题。
参考代码
#include <iostream>
using namespace std;
const int maxn = 1e5+10;
int stk[maxn], tt;
int main(void)
{
int n;
cin >> n;
int x;
while(n--)
{
cin >> x;
//遍历单调栈寻找满足条件的数字，并且删除掉逆序对，维护栈的单调性（升序）
//注意while中的>=不能写为>，题目中描述的是“找到比它小的数”，并不包含小于等于的情况
while(tt && stk[tt] >= x) tt--;
//若存在最优解则输出，否则输出-1
if(tt) cout << stk[tt] << ' ';
else cout << "-1" << ' ';
//让待查找序列中的数字入栈
stk[++tt] = x;
}
return 0;
}
单调队列
Acwing-154 滑动窗口
思路
模板题。滑动窗口是用单调队列来维护下标（当然直接在队列里面存值也可以，但不便于理解）。因为涉及到窗口的移动，下标可以唯一对应到数组元素值并保使得维护窗口长度不超过k。而原序列中的数是储存在另一个数组a中。
参考代码
#include <iostream>
using namespace std;
const int maxn = 1e6+10;
int a[maxn], q[maxn];
int main(void)
{
//cin和cout关闭同步，使得在输入输出较多的情况下能有更快的速度
//这里一定要两句都写，只写第二句速度提升效果并不显著
cin.tie(0);
ios::sync_with_stdio(false);
int n, k;
cin >> n >> k;
//这里也可以把输入写到下面的循环里
for(int i = 0; i < n; i++) cin >> a[i];
int hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
//判断队头是否滑出窗口
while(hh <= tt && i-k+1 > q[hh]) hh++;
//对于这道题，这里的等号可有可无，最值可以不唯一，所以不必为严格单调
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
//注意是输出窗口内的最值,数字若不足3个则不构成窗口，不输出
if(i+1 >= k) cout << a[q[hh]] << ' ';
}
cout << endl;
hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
//判断队头是否滑出窗口
while(hh <= tt && i-k+1 > q[hh]) hh++;
//最大值同理，删除掉数组中的升序逆序对，维护为单调递增序列即可
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i+1 >= k) cout << a[q[hh]] << ' ';
}
return 0;
}
KMP
Acwing-831 KMP字符串
思路
模板题。
参考代码
#include <iostream>
using namespace std;
const int N = 1e5+10;
const int M = 1e6+10;
int n, m, ne[N]; // s[]是长文本，p[]是模式串，m是s的长度，n是p的长度
char p[N], s[M];
int main(void)
{
cin.tie(0), cout.tie(0);ios::sync_with_stdio(false);
//这里KMP算法的下标从1开始
cin >> n >> (p + 1) >> m >> (s + 1);
//得到next数组(双指针算法)
//next数组为模式串的子串中前缀和后缀相同的最大长度，即若有不匹配的情况时可以让模式串往后移动的最少次数
for(int i = 2, j = 0; i <= n; i++)
{
while(j && p[i] != p[j+1]) j = ne[j]; //这一步是j指针先回退后，模式串移动到j指针所指向的地方
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
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)
{
j = ne[j];
cout << i-n << ' ';
}
}
return 0;
}
Trie
Acwing-835
思路
模板题。
参考代码
#include <cstdio>
#include <cstring>
//下列写法适用于只包含小写字母的字符串
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点，第一维为节点总数，第二维为某节点的子节点最大数量，比如这里是26，因为小写字母只有26种情况，若为二进制串则只有两种情况。
// cnt[]存储以每个节点结尾的单词数量
const int maxn = 1e5 + 10;
int n, son[maxn][26], cnt[maxn], idx;
char str[maxn];
// 插入一个字符串
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(void)
{
scanf("%d", &n);
getchar();
while(n--)
{
char op;
memset(str, 0, sizeof(str));
scanf("%c %s", &op, str);
getchar();
if(op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
Acwing-143
思路
要使得异或和最大，从最高位开始遍历，两数二进制表示在高位不同的数的个数越多，异或和就越大。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010, maxm = 3100010;
int son[maxm][2], idx, a[maxn];
void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; i--) //从二进制最高位开始遍历存储到trie树中
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i--)
{
//求得二进制表示的第i位数字
int u = x >> i & 1;
if(son[p][!u])
{
p = son[p][!u];
res = res * 2 + !u;
}
else
{
p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
int main(void)
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
int ans = 0;
for(int i = 0; i < n; i++)
{
insert(a[i]);
int t = query(a[i]);
ans = max(ans, a[i] ^ t);
}
printf("%d\n", ans);
return 0;
}
并查集
Acwing-836
思路
参考代码
Acwing-837
思路
参考代码
Acwing-240
思路
参考代码
堆
Acwing-838
思路
参考代码
Acwing-839
思路
参考代码
哈希表
Acwing-840
思路
参考代码
Acwing-841
思路
参考代码