数据结构
链表
1 单链表
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 将x插到头结点
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
// 将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]];
}
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];
else 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;
}
2 双链表
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
// 在节点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];
}
int main()
{
cin >> m;
// 0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
while (m -- )
{
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);
}
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;
}
栈
先进后出
后缀表达式(洛谷)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int stk[N], tt, x;
string str;
bool is;
void push(int x) { stk[++tt] = x; }
int pop() { return stk[tt--]; }
int top() { return stk[tt]; }
// void out()
// {
// for(int i=1;i<=tt;i++) cout<<stk[i]<<' ';
// puts("");
// }
int main()
{
cin >> str;
for (int i = 0; i < str.length() && str[i] != '@'; i++)
{
if (str[i] >= '0' && str[i] <= '9')
x = x * 10 + str[i] - '0';
if (str[i] == '.')
{
push(x);
x = 0;
}
if (str[i] == '+')
push(pop() + pop());
if (str[i] == '-')
{
int last1 = pop();
int last2 = pop();
push(last2 - last1);
}
if (str[i] == '*')
push(pop() * pop());
if (str[i] == '/')
{
int last1 = pop();
int last2 = pop();
push(last2 / last1);
}
}
cout << top() << endl;
//system("pause");
return 0;
}
队列
先进先出
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int q[N], hh, tt = -1;
int main()
{
cin >> m;
while (m -- )
{
string op;
int x;
cin >> op;
if (op == "push")
{
cin >> x;
q[ ++ tt] = x;
}
else if (op == "pop") hh ++ ;
else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
else cout << q[hh] << endl;
}
return 0;
}
// 队列
// 先进先出
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt = -1;
int n, m, ans;
void push(int x)
{
q[++tt] = x;
}
void pop()
{
hh++;
}
bool empty()
{
if (hh <= tt)
return false;
return true;
}
// void out()
// {
// for (int i = hh; i <= tt; i++)
// cout << q[i] << ' ';
// puts("");
// }
bool find(int x)
{
for (int i = hh; i <= tt; i++)
if (x == q[i])
return true;
return false;
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (empty())
{
ans++;
push(x);
}
else if (!find(x))
{
ans++;
if (tt - hh >= m - 1)
pop();
push(x);
}
}
cout << ans << endl;
//system("pause");
return 0;
}
单调队列
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int q[N], hh, tt = -1;
int n, k;
int 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;
while (hh <= tt && a[i] <= a[q[tt]])
--tt;
q[++tt] = i;
if (i + 1 >= k)
printf("%d ", a[q[hh]]);
}
puts("");
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]]);
}
//system("pause");
return 0;
}
单调栈
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 3e6 + 10;
int stk[N], tt, n;
int a[N], ans[N];
void push(int x) { stk[++tt] = x; }
int pop() { return stk[tt--]; }
int top() { return stk[tt]; }
int empty()
{
if (tt > 0)
return false;
return true;
}
void out()
{
for (int i = 1; i <= tt; i++)
cout << stk[i] << ' ';
cout << endl;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n; i > 0; i--)
{
while (!empty() && a[top()] <= a[i]) pop();
ans[i] = empty() ? 0 : top();
push(i);
}
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
//system("pause");
return 0;
}
KMP
// KMP
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
char p[N] = "0", s[N] = "0";
int ne[N];
int main()
{
cin >> s + 1 >> p + 1;
n = strlen(p) - 1;
m = strlen(s) - 1;
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;
}
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\n", i - n + 1);
j = ne[j];
}
}
for (int i = 1; i <= n; i++)
printf("%d ", ne[i]);
system("pause");
return 0;
}
Trie 树
const int M = 1e6 + 10;
int son[M][26], cnt[M], idx;
// 插入
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];
}
并查集
void init(int n)
{
for (int i = 1; i <= n; i ++) fa[i] = i;
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
堆
#include<iostream>
using namespace std;
constexpr int N = 1e+5 + 10;
int n,m,h[N], s;
// h[N] 一维数组用于存储完全二叉树上的节点的值，其下标判断各个节点之间的关系
// 例如 h[x] 的 左孩子节点的值为 h[2 * x] . 右孩子节点的值为 h[2 * x + 1], 其父节点为 h[x / 2];
// 假定都存在, 2 * x <= 节点总数 2 * x + 1 <= 节点总数， 父节点 x / 2 >= 1
// s 用来表示当前堆中的节点的总数
// 代码down操作实现
auto down(int x) -> int
{
int t = x;
if(2 * x <= n && h[t] > h[2 * x]) t = 2 * x; // 与左孩子节点值比较
if(2 * x + 1 <= n && h[t] > h[2 * x + 1]) t = 2 * x + 1; // 与右孩子节点值比较
if(t != x) swap(h[t], h[x]), down(t); // 若t != x，说明此时节点并不不符合堆，故与其中较小的孩子进行交互
// 交换完后，此时被交互到孩子位置的节点与其新左右孩子的节点值是否满足小顶堆，故这里我们就需要递归.
}
// 代码up操作的实现
auto up(int x) -> void
{
while(x / 2 && h[x / 2] > h[x]) // 若此时父节点存在，且父节点值大于自己，不满足条件需要进行交换
{
swap(h[x / 2] , h[x]);
x /= 2;
}
}
// 设要交换的位置为 x
swap(h[x], h[s]); // 交换要删除的元素和最后一个叶子节点的位置
--s; // 表示删除了一个元素，因为如果对于堆，直接删堆中元素操作复杂，但在一维数组中直接删除最后一个元素很方便
down(x), up(x); //执行其中一个操作，具体的操作由此时被交换叶子节点的值与新父子节点和孩子节点值的关系决定
// 如果是删除堆顶元素
swap(h[1], h[s--]);
down(1); // 此时只有下沉操作
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int h[N], cnt, n;
void up(int k)
{
while (k >> 1 && h[k >> 1] > h[k])
{
swap(h[k], h[k >> 1]);
k >>= 1;
}
}
void insert(int x)
{
h[++cnt] = x;
up(cnt);
}
void down(int x)
{
int t = x;
if (x * 2 <= cnt && h[t] > h[x * 2]) t = 2 * x;
if (2 * x + 1 <= cnt && h[t] > h[2 * x + 1]) t = 2 * x + 1;
if (t != x) swap(h[t], h[x]), down(t);
}
void remove()
{
swap(h[1], h[cnt--]);
down(1);
}
int main()
{
scanf("%d", &n);
int op, x;
while (n --)
{
scanf("%d", &op);
if (op == 1)
{
scanf("%d", &x);
insert(x);
}
else if (op == 2) printf("%d\n", h[1]);
else if (op == 3) remove();
}
return 0;
}
堆排序
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int h[N], cnt, n, m, x;
void up(int k)
{
while (k >> 1 && h[k >> 1] > h[k])
{
swap(h[k], h[k >> 1]);
k >>= 1;
}
}
void insert(int x)
{
h[++cnt] = x;
up(cnt);
}
void down(int x)
{
int t = x;
if (x * 2 <= cnt && h[t] > h[x * 2]) t = 2 * x;
if (2 * x + 1 <= cnt && h[t] > h[2 * x + 1]) t = 2 * x + 1;
if (t != x) swap(h[t], h[x]), down(t);
}
void remove()
{
swap(h[1], h[cnt--]);
down(1);
}
int main()
{
scanf("%d%d", &n, &m);
while (n --) {
scanf("%d", &x);
insert(x);
}
while (m --) {
printf("%d ", h[1]);
remove();
}
return 0;
}
hash表
1.开放寻址法
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N];
int find(int x) {
int t = (x % N + N) % N;
while (h[t] != INF && h[t] != x) {
t ++;
if (t == N) t = 0;
}
return t;
}
int main() {
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while (n --) {
char op[2]; int x;
scanf("%s%d", op, &x);
int k = find(x);
if (op[0] == 'I') h[k] = x;
else {
if (h[k] == INF) puts("No");
else puts("Yes");
}
}
}
2.拉链法
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 3;
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;
}
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[0] == 'I') insert(x);
else {
if (find(x)) puts("Yes");
else puts("No");
}
}
}
3.字符串哈希
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, P = 131;
#define u unsigned long long
u n, m, h[N], p[N];
char str[N];
u f(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
cin >> n >> m >> str + 1;p[0] = 1;
for(int i = 1; i <= n; i ++)
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while(m --)
{
u a, b,c, d;
cin >> a >> b >> c >> d;
if(f(a, b) == f(c, d)) puts("Yes");
else puts("No");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10000 + 10, M_MAX = 1500 + 10;
typedef unsigned long long ULL;
vector<ULL> a;
char str[M_MAX];
int n, prime = 233317;
ULL mod = 212370440130137957ll, base = 131;
ULL hashe(char s[]) {
int l = strlen(s);
ULL res = 0;
for (int i = 0; i < l; ++ i) res = (res * base + (ULL)s[i]) % mod + prime;
return res;
}
int main() {
scanf("%d", &n);
while (n --) {
scanf("%s", str);
a.push_back(hashe(str));
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
printf("%d", a.size());
return 0;
}
C++ STL
unique, 将数组中重复的元素放到了最后
sort, 将数组中的元素排序
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
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
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
