单链表:
// 1、单链表:
#include<iostream>
using namespace std;
const int N = 100010;
// 定义头结点head,e[N]用来储存结点的值,ne[N]用来储存结点的next指针,idx用来记录当前记录到哪个点
int head, e[N], ne[N], idx;
// 初始化函数
void init()
{
head = -1;
// 下标从0开始
idx = 0;
}
// 插入到头结点的后面
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++ ;
}
// 插入到k下标结点的后面
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++ ;
}
// 删除k下标后面的结点
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
// 记得要初始化
init();
while(m -- )
{
int k, x;
char c;
cin >> c;
if(c == 'H')
{
cin >> x;
add_to_head(x);
}
else if(c == 'I')
{
cin >> k >> x;
// 第k个点,下标为k - 1;
add(k - 1, x);
}
else
{
cin >> k;
// 删除头结点后面的结点,需要特判一下
if(!k) head = ne[head];
remove(k - 1);
}
}
// 从头结点开始循环,i = ne[i]表示更新 i 为 i 的下一个
for(int i = head; i != -1; i = ne[i])
{
cout << e[i] << ' ';
}
return 0;
}
双链表:
// 2、双链表
#include<iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
r[0] = 1; // 0是左端点
l[1] = 0; // 1是右端点
idx = 2; // 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;
idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
int main()
{
int m;
cin >> m;
// 初始化
init();
while(m -- )
{
int a, x;
string s;
cin >> s;
if(s == "L")
{
cin >> x;
insert(0, x);
}
else if(s == "R")
{
cin >> x;
insert(l[1], x);
}
else if(s == "IL")
{
cin >> a >> x;
// 这里的a需要加1是因为idx的下标是从2开始的
insert(l[a + 1], x);
}
else if(s == "IR")
{
cin >> a >> x;
// 这里的a需要加1是因为idx的下标是从2开始的
insert(a + 1, x);
}
else
{
cin >> a;
// 这里的a需要加1是因为idx的下标是从2开始的
remove(a + 1);
}
}
for(int i = r[0]; i != 1; i = r[i])
{
cout << e[i] << ' ';
}
return 0;
}
模拟栈
// 3、模拟栈
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
模拟队列
// 4、模拟队列
// (1)普通队列
// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}
// (2)循坏队列
// 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)
{
}
单调栈
// 5、单调栈
#include<iostream>
using namespace std;
const int N = 100010;
// 栈顶元素tt = 0
int stk[N], tt;
int main()
{
int n;
cin >> n;
while(n -- )
{
int x;
cin >> x;
// 如果栈顶元素tt不为0且stk[tt]大于等于输入的x,则t --
while(tt && stk[tt] >= x) tt -- ;
// 如果tt == 0
if(!tt) cout << -1 << ' ';
// 否则还是输出stk[tt]
else cout << stk[tt] << ' ';
// 将x存入stk
stk[ ++ tt] = x;
}
return 0;
}
单调队列
// 6、单调队列
#include<iostream>
using namespace std;
const int N = 1000010;
int n, k;
// a[N]用来储存数,q[N]用来储存下标
int a[N], q[N];
int main()
{
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 ++ )
{
// 判断队头是否已经滑出窗口
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]] << ' ';
}
puts("");
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]] << ' ';
}
puts("");
return 0;
}
KMP算法
// 7、KMP算法
#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{
// p和s的下标从1开始,容易理解,好做
cin >> n >> p + 1 >> m >> s + 1;
// next数组寻找过程
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;
}
// KMP匹配过程
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 - j + 1);
j = ne[j];
}
}
// 输出next数组
for(int i = 1; i <= n; i ++ )
{
printf("%d ", ne[i]);
}
return 0;
}
Trie
// 8、Trie
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
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 ;
cout << "###########" << idx << endl;
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()
{
int n;
cin >> n;
while(n -- )
{
char op[2];
cin >> op >> str;
if(op[0] == 'l') insert(str);
else cout << query(str) << endl;
}
return 0;
}
并查集
// 9、并查集
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x) // 返回x的祖宗节点 + 路径压缩
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) p[i] = i;
while(m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
tql