数据结构
单链表
cpp
// 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];
}栈
cpp
int stk[N], tt = 0; // tt表示栈顶
stk[ ++ tt] = x; // 向栈顶插入一个数
tt -- ; // 从栈顶弹出一个数
stk[tt]; // 栈顶的值
if (tt > 0) return false;
else return true;cpp
#include <iostream>
#include <string>
using namespace std;
const int N = 100010;
int skt[N],tt;
int main(){
tt = 0;
int m;
cin>>m;
while(m--){
string option;
cin>>option;
if(option == "push"){
int x;
cin>>x;
skt[++tt] = x;
}
else if(option == "pop"){
tt --;
}
else if(option == "empty"){
if (tt>0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else{
cout<<skt[tt]<<endl;
}
}
}双链表
cpp
// 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];
}单调队列
cpp
//常见模型：找出滑动窗口中的最大值/最小值
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;
}队列
- 普通队列：
cpp
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt) return false;
else return true;- 循环队列
cpp
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt) return false
else return true;Trie树
cpp
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];
}并查集
- 朴素并查集：
cpp
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);- 维护size的并查集：
cpp
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回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;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);- 维护到祖宗节点距离的并查集：
cpp
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x) {
if (p[x] != x) {
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) {
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量树与图的存储
树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 (1) 邻接矩阵：g[a][b] 存储边a->b (2) 邻接表：
cpp
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
cpp
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ) {
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}一般哈希模拟散列表
- 拉链法
cpp
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;
}- 开放寻址法
cpp
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;
}单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
cpp
int tt = 0;
for (int i = 1; i <= n; i ++ ) {
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}堆排序
cpp
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], sz;
void down(int u) {
int t = u;
if (u * 2 <= sz && h[t] > h[u * 2]) t = u * 2;
if (u * 2 + 1 <= sz && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
if (u != t) {
swap(h[t], h[u]);
down(t);
}
}
void deleteMin() {
h[1] = h[sz];
sz--;
down(1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
sz = n;
for (int i = n / 2; i; i--) down(i);
while (m--) {
cout << h[1] << " ";
deleteMin();
}
}表达式求值
cpp
#include <bits/stdc++.h>
#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();
if (c == '+') num.push(a + b);
else if (c == '-') num.push(a - b);
else if (c == '*') num.push(a * b);
else num.push(a / b);
}
int main() {
unordered_map<char, int> pr = { {'+',1},{'-',1},{'*',2},{'/',2} };
string str;
cin >> str;
for (int i = 0; i < str.size(); i++) {
auto 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';
i = j - 1;
num.push(x);
}
else if (c == '(') op.push(c);
else if (c == ')') {
while (op.top() != '(') eval();
op.pop();
}
else {
while (op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while (op.size()) eval();
cout << num.top() << endl;
}