链表与邻接表：树与图的存储
单链表
画个图就很好理解了
例题
826. 单链表acwing——826. 单链表_awcing 826-CSDN博客
实现一个单链表，链表初始为空，支持三种操作：
(1) 向链表头插入一个数；
(2) 删除第k个插入的数后面的数；
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。
输入格式
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
(1) “H x”，表示向链表头插入一个数x。
(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。
(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int m, k, x;
char op;
//init初始化
int head=-1, e[N], ne[N], idx=1;
// head 表示头结点的下标
// e[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点
// 将x插入到头结点
void add_to_head(int x)
{
e[idx]=x, ne[idx]=head, head=idx, idx++;
}
// 将下标是k后面的点删掉
void erase(int k)
{
ne[k]=ne[ne[k]];
}
// 将x插入到下标为k的后面
void add(int k, int x)
{
e[idx]=x, ne[idx]=ne[k], ne[k]=idx, idx++;
}
int main()
{
scanf("%d", &m);
while (m--)
{
cin>>op;
if (op=='H')
{
scanf("%d", &x);
add_to_head(x);
}
else if (op=='D')
{
scanf("%d", &k);
if (k==0) head=ne[head];
else erase(k);
}
else
{
scanf("%d%d", &k, &x);
add(k, x);
}
}
for (int i=head; i!=-1; i=ne[i]) printf("%d ", e[i]);
return 0;
}
双链表
题目来源：AcWing 827. 双链表
一、题目描述
实现一个双链表，双链表初始为空，支持 5 55 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k kk 个插入的数删除；
在第 k kk 个插入的数左侧插入一个数；
在第 k kk 个插入的数右侧插入一个数
现在要对该链表进行 M MM 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k kk 个插入的数并不是指当前链表的第 k kk 个数。例如操作过程中一共插入了 n nn 个数，则按照插入的时间顺序，这 n nn 个数依次为：第 1 11 个插入的数，第 2 22 个插入的数，…第 n nn 个插入的数。
输入格式
第一行包含整数 M MM，表示操作次数。
接下来 M MM 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x xx。
R x，表示在链表的最右端插入数 x xx。
D k，表示将第 k kk 个插入的数删除。
IL k x，表示在第 k kk 个插入的数左侧插入一个数。
IR k x，表示在第 k kk 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1 ≤ M ≤ 100000 1≤M≤1000001≤M≤100000
所有操作保证合法。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
1
2
3
4
5
6
7
8
9
10
11
输出样例：
8 7 7 3 2 9
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int m, k, x;
string op;
int e[N], l[N], r[N], idx=0;
void init()
{
l[1]=0, r[0]=1;
idx=2;
}
void add(int k, int x)
{
e[idx]=x, l[idx]=k, r[idx]=r[k];
l[r[k]]=idx, r[k]=idx, idx++;
}
void erase(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
init();
scanf("%d", &m);
while (m--)
{
cin>>op;
if (op=="L")
{
scanf("%d", &x);
add(0, x);
}
else if (op=="R")
{
scanf("%d", &x);
add(l[1], x);
}
else if (op=="D")
{
scanf("%d", &k);
erase(k+1);
}
else if (op=="IL")
{
scanf("%d%d", &k, &x);
add(l[k+1], x);
}
else if (op=="IR")
{
scanf("%d%d", &k, &x);
add(k+1, x);
}
}
for (int i=r[0]; i!=1; i=r[i]) printf("%d ", e[i]);
return 0;
}
栈与队列：单调队列、单调栈
模拟栈
模拟队列
单调栈
用于找一个数左边或者右边离它最近的且比它小的数
例如3,4,2,7,5
输出-1,3,-1,2,2
栈里的元素一定是单调上升的
举例，刚开始数组8,7,4,8
8入栈，7再入栈，但是发现，这个8，不仅比7大，而且比7要往左。没用了，就不用管8了
题目信息
题目描述
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 -1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出 -1。
数据范围
1 ≤ N ≤ 1 0 5 10^510
5
1 ≤ 数列中元素 ≤ 1 0 9 10^910
9
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n, x, stk[N], tt=0;
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++)
{
scanf("%d", &x);
while (tt && stk[tt]>=x) tt--;
if (tt) printf("%d ", stk[tt]);
else printf("-1 ");
stk[++tt]=x;
}
return 0;
}
单调队列
一般用于滑动窗口
取窗口内最小值， 如果一个数比当前这个数要大，而且位置靠前，就没用了
整个队列在滑动的过程中，在任何时刻都要保证严格的单调递增，因此窗口中的最小值永远是队首。最大值同理
题目来源：AcWing 154. 滑动窗口
一、题目描述
给定一个大小为 n ≤ 1 0 6 n≤10^6n≤10
6
的数组。
有一个大小为 k kk 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k kk 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k kk 为 3 33。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n nn 和 k kk，分别代表数组长度和滑动窗口的长度。
第二行有 n nn 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
1
2
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n, k, a[N];
int hh=1, tt=0, q[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
for (int i=1; 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>=k) printf("%d ", a[q[hh]]);
}
printf("\n");
hh=1, tt=0;
for (int i=1; 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>=k) printf("%d ", a[q[hh]]);
}
return 0;
}
KMP
sz算法，搞那么复杂，我就直接铥了。
AcWing 831. KMP字符串_acwing的kmp字符串-CSDN博客
KMP算法详解-彻底清楚了(转载+部分原创) - sofu6 - 博客园 (cnblogs.com)
“这玩意像老鼠屎一样，万年难得一用，不用细节就忘，忘了又回来看，过半年又忘”
例题
P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
string s, p;
int n=0, m=0, ne[N];
int main()
{
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
cin>>s>>p;
s=' '+s, p=' '+p;
n=s.size()-1, m=p.size()-1;
//求模式串的Next数组：
for (int i=2, j=0; i<=m; 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<=n; i++)
{
while (j && s[i]!=p[j+1]) j=ne[j];
if (s[i]==p[j+1]) j++;
if (j==m) //匹配成功
{
printf("%d\n", i-m+1);
j=ne[j];
}
}
for (int i=1; i<=m; i++) printf("%d ", ne[i]);
return 0;
}
标签：idx,int,scanf,基础,ne,笔记,链表,插入,数据结构 From： https://www.cnblogs.com/didiao233/p/18014659