链表操作的最后一步通常为idx++(idx为每个节点的唯一坐标，不随节点的删除而消失，只是不在链上了)
单链表
#include <iostream>
using namespace std;
const int N = 100010;
int e[N], ne[N], head, idx;
void init() {
idx = 0;
head = -1;
}
//在表头添加
void add_to_head(int x) {
e[idx] = x, ne[idx] = head, head = idx++;
}
//删除第k个节点后面的节点
void remove(int k) {
ne[k] = ne[ne[k]];
}
//在第k个节点后添加
void add(int k, int x) {
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
int main() {
int m;
cin >> m;
init();
while (m--) {
char op;
int k, x;
cin >> op;
if (op == 'H') {
cin >> x;
add_to_head(x);
}
else if (op == 'D') {
cin >> k;
//注意检查k为0的情况，此时应直接修改表头，否则会造成表头丢失
if (!k) head = ne[head];
//注意偏移量，第k个插入的数的坐标(idx)是k - 1, 故应传入k - 1
remove(k - 1);
}
else {
cin >> k >> x;
//同样注意偏移量
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
cout << endl;
return 0;
}
双链表
#include <iostream>
#include <string>
using namespace std;
const int N = 100010;
//双链表以0,1为头尾，不需要head
int e[N], l[N], r[N], idx;
void insert(int a, int x) {
e[idx] = x;
l[idx] = a, r[idx] = r[a];
//对于a 和 r[a] 的修改要放在最后一步，以防更新idx造成混乱
l[r[a]] = idx, r[a] = idx++;
}
void remove(int a) {
l[r[a]] = l[a];
r[l[a]] = r[a];
}
int main() {
//这里0的右节点是1,1的左节点是0，故idx从2开始(0,1已占用两个)
r[0] = 1, l[1] = 0;
idx = 2;
int m;
cin >> m;
while (m--) {
string op;
int k, x;
cin >> op;
if (op == "L") {
cin >> x;
//头部插入在0后插
insert(0, x);
}
else if (op == "R") {
cin >> x;
//尾部插入在l[1](原先的尾结点)之后插
insert(l[1], x);
}
else if (op == "D") {
cin >> k;
//注意偏移量，idx从2开始，故传入k + 1(相对于idx从零开始的单链表基础上加2:k - 1 + 2)
remove(k + 1);
}
else if (op == "IL") {
cin >> k >> x;
//第k个节点左边插入即l[k+1]
insert(l[k + 1], x);
}
else if (op == "IR") {
cin >> k >> x;
//第k个节点右边插入即k+1
insert(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
cout << endl;
return 0;
}
手写栈模版
//栈顶入，栈顶出
#include <iostream>
#include <string>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main() {
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") cout << (tt ? "NO" : "YES") << endl;
else cout << stk[tt] << endl;
}
return 0;
}
表达式求值
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <unordered_map>
using namespace std;
//开一个数据栈，一个操作符栈
stack<int> num;
stack<char> op;
//计算裸露表达式(无括号)
void eval() {
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else if (c == '/') x = a / b;
//记得将结果放回数据栈
num.push(x);
}
int main() {
//用哈希表存操作符优先级
unordered_map<char, int> pr{ {'+',1},{'-',1},{'*',2},{'/',2} };
string str;
cin >> str;
for (int i = 0; i < str.size(); i++) {
char c = str[i];
if (isdigit(c)) {
//读取数据(逐字读取将字符串转化为数字)
int x = 0;
int j = i;
while (j < str.size() && isdigit(str[j]))
x = x * 10 + str[j++] - '0';
num.push(x);
i = j - 1;
}
//左括号直接压栈(表明开始)
else if (c == '(') op.push(c);
//右括号说明结束，开始进行表达式计算
else if (c == ')') {
//条件：遇到左括号停止计算，并弹出左括号以进行后续操作
while (op.top() != '(') eval();
op.pop();
}
//遇到操作符
else {
//条件：操作符栈不空、未遇到左括号，当前栈顶操作符优先级更高
while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c])
eval();
//处理完毕后压入新操作符
op.push(c);
}
}
//处理剩下可能有的裸露表达式直至耗尽操作符
while (op.size()) eval();
cout << num.top() << endl;
return 0;
}
手写队列模版
//队尾入，队头出
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int m;
int q[N];
//tt初始化为-1
int tt = -1, hh;
int main() {
cin >> m;
while (m--) {
string op;
cin >> op;
if (op == "push") {
int x;
cin >> x;
//注意这里是++tt(和tt初始化为-1结合记忆)
q[++tt] = x;
}
else if (op == "pop") hh++;
else if (op == "empty")
cout << (hh <= tt ? "NO" : "YES") << endl;
else cout << q[hh] << endl;
}
}
单调栈
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int stk[N], tt;
int main() {
cin >> n;
//注意这种动态读入，处理而非一次性读入的方法
while (n--) {
int x;
cin >> x;
//从栈顶弹出逆序对
while (tt && stk[tt] >= x) tt--;
if (!tt) cout << "-1" << " ";
else cout << stk[tt] << " ";
//新数入栈(不要忘了这一步！)
stk[++tt] = x;
}
return 0;
}
单调队列(滑动窗口)
#include <iostream>
using namespace std;
const int N = 1000010;
//队列存的是下标，不是数组元素！
int a[N], q[N], hh, tt = -1;
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
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;
//当窗口至少有k个数才可以输出
if (i >= k - 1) cout << a[q[hh]] << " ";
}
cout << endl;
//最大值同理，将 >= 改成 <= 即可
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) cout << a[q[hh]] << " ";
}
return 0;
}
模板
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m, ne[N];
char p[N], s[M];
int main() {
//注意这里是1-indexed 故读入p + 1 和 s + 1
cin >> n >> p + 1 >> m >> s + 1;
//next数组，存放前后缀相同(不是对称)的最大长度
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[j + 1] != p[i]) j = ne[j];
if (p[j + 1] == p[i]) j++;
ne[i] = j;
}
//利用next数组，不匹配就回退j
for (int i = 1, j = 0; i <= m; i++) {
while (j && p[j + 1] != s[i]) j = ne[j];
if (p[j + 1] == s[i]) j++;
if (j == n) {
//由于答案要求0-indexed输出，故输出i - n + 1 - 1 = i - n
cout << i - n << " ";
j = ne[j];
}
}
return 0;
}
#include <iostream>
#include <string>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char 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';
//若无该节点，则说明不含该字符串，直接返回0
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main() {
int n;
cin >> n;
while (n--) {
string op;
cin >> op >> str;
if (op == "I") {
insert(str);
}
else {
cout << query(str) << endl;
}
}
return 0;
}
最大异或对
#include <iostream>
using namespace std;
// M开这么大是因为每个数最多31位二进制，又有100000个数
const int N = 100010, M = 3100010;
int son[M][2], idx;
int a[N];
void insert(int x) {
int p = 0;
//逐位抽出二进制数，判断节点是否存在
for (int i = 30; i >= 0; i--) {
int& s = son[p][x >> i & 1];
if (!s) s = ++idx;
p = s;
}
}
int search(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int u = x >> i & 1;
//若!u(与该位不同)有数，则沿这条路走
if (son[p][!u]) {
//注意加上的是1 << i 而非 i
res += 1 << i;
p = son[p][!u];
}
//否则按原路走
else p = son[p][u];
}
return res;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) insert(a[i]);
int res = 0;
//逐个计算并更新最大值
for (int i = 0; i < n; i++) res = max(res, search(a[i]));
cout << res << endl;
return 0;
}
并查集模版
#include <string>
using namespace std;
const int N = 100010;
int p[N];
// find 函数(路径压缩优化)
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
while (m--) {
string op;
int a, b;
cin >> op >> a >> b;
if (op == "M") p[find(a)] = find(b); // 将a的根并为b的子树
else {
if (find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}
有计数功能的并查集
加权并查集
#include <iostream>
using namespace std;
const int N = 100010;
int p[N], d[N];
int find(int x) {
if (x != p[x]) {
// 调用find函数递归，此步完成时p[x]已经是祖宗节点
int t = find(p[x]);
// d[x] 本来是x到其父节点的距离，现在变为到其祖宗节点的距离 (d[p[x]] 是x的父节点到祖宗节点的距离)
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) p[i] = i;
int res = 0;
while (k--) {
int op, x, y;
cin >> op >> x >> y;
if (x > n || y > n) res++;
else {
int px = find(x), py = find(y);
if (op == 1) {
// 若为同级，则x,y到共同祖宗节点py距离(mod3)相同，即d[x]==d[y]
if (px == py && (d[x] - d[y]) % 3) res++;
else if (px != py) {
// 合并集合，且d[x] + d[px] = d[y]
p[px] = py;
d[px] = d[y] - d[x];
}
}
else {
// 若x吃y，则d[x] = d[y] + 1
if (px == py && (d[x] - d[y] - 1) % 3) res++;
else if (px != py) {
// 合并集合， d[x] + d[px] = d[y] + 1
p[px] = py;
d[px] = d[y] - d[x] + 1;
}
}
}
}
cout << res << endl;
return 0;
}
堆排序模版
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], cnt;
// down函数
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);
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
cnt = n;
// 优化： 叶节点不需要down，从 n / 2 到 1 进行 down操作
for (int i = n / 2; i; i--) down(i);
while (m--) {
cout << h[1] << " ";
swap(h[1], h[cnt--]);
down(1);
}
cout << endl;
return 0;
}
模拟堆(支持改写第k个入堆的数)
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 100010;
// ph: point_to_heap; hp: heap_to_point
int h[N], ph[N], hp[N], cnt;
// 堆交换专用函数
void heap_swap(int a, int b) {
// 先交换“电话簿地址”
swap(ph[hp[a]], ph[hp[b]]);
// 再交换“门牌号”
swap(hp[a], hp[b]);
// 最后交换值
swap(h[a], h[b]);
}
// down函数
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) {
heap_swap(u, t);
down(t);
}
}
// up函数
void up(int u) {
while (u / 2 && h[u] < h[u / 2]) {
heap_swap(u, u / 2);
u >>= 1;
}
}
int main() {
int n, m = 0;
cin >> n;
while (n--) {
string op;
int k, x;
cin >> op;
if (op == "I") {
cin >> x;
// 先分配新“门牌号”和“地址”
m++, cnt++;
ph[m] = cnt;
hp[cnt] = m;
h[cnt] = x;
// 此时在堆底，要up
up(cnt);
}
else if (op == "PM") cout << h[1] << endl;
else if (op == "DM") {
heap_swap(1, cnt);
cnt--;
down(1);
}
else if (op == "D") {
cin >> k;
// 涉及第k个入堆的数，输入的k要转换为ph[k]
k = ph[k];
heap_swap(cnt, k);
cnt--;
// up 和 down 都做一下
up(k);
down(k);
}
else {
cin >> k >> x;
// 涉及第k个入堆的数，输入的k要转换为ph[k]
k = ph[k];
h[k] = x;
// up 和 down 都做一下
up(k);
down(k);
}
}
return 0;
}
模拟散列表
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
// N取数据范围的2~3倍的质数， null 为规定的无穷大，作为“空位”的标志
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
// find 函数同时承担查找和分配新位置两个任务
int find(int x) {
// 哈希映射坐标
int t = (x % N + N) % N;
// 循环条件；非空位或空位不是x则t++ , 当 t 到 N 时 t 回到 0
while (h[t] != null && h[t] != x) {
t++;
if (t == N) t = 0;
}
return t;
}
int main() {
int n;
cin >> n;
// 初始化所有位置为null
memset(h, 0x3f, sizeof h);
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
h[find(x)] = x;
}
else {
// 调用 h[find(x)] 会给x自动分配一个地址并自动赋值为null(因为memset过)，但若之前未赋值，则该位置值仍为初始的null
if (h[find(x)] == null) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
return 0;
}
字符串哈希
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
// 经验数值，取 P 为 131 或13331 为权
const int N = 100010, P = 131;
// ULL 的妙用， 当超过 2^64 自动溢出，相当于对 2^64 取模
ULL h[N], p[N];
char str[N];
ULL get(int l, int r) {
// 获取子串哈希值，* p[r - l + 1] 起到“对齐”作用(类比整数)
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
int n, m;
cin >> n >> m >> str + 1;
p[0] = 1;
// 预处理，计算各位哈希值(0~该位字符哈希值)
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}