单链表、双链表(循环)

// 单链表、邻接表(n 个链表)
# 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; // -1 表示空指针
    idx = 0;
}
void add_to_head(int x){
    e[idx] = x, ne[idx] = head; // head 的下一个为空
    head = idx, idx ++;
}
void add(int k, int x){
    // 将 x 插入到下标是 k 的点后面(idx 从 0 开始)
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++;
}
void remove(int k){
    // 将下标是 k 的点后面的点删除
    ne[k] = ne[ne[k]];
}

// 双链表
// 下标0:head；下标1:tail；
int e[N], l[N], r[N], idx;
void init(){
    r[0] = 1, l[1] = 0; // 分别是左右端点指针 // 0是左端点，1是右端点
    idx = 2;
}
void add(int k, int x){
    // 将 x 插入到下标是 k 的点右面(idx 从 0 开始)
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];// 插入
    l[r[k]] = idx, r[k] = idx;// 修改指针
    idx ++;
}// add(l[k], x); 表示将 x 插入到下标是 k 的点左面
void remove(int k){
    // 将下标是 k 的点删除(idx 从 0 开始)
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

栈与队列

#include <iostream>
using namespace std;
const int N = 100010;
// 栈顶
int stk[N], tt = 0;// tt 是栈顶下标
// 插入
stk[++tt] = x;
// 弹出
tt --;
// 判定栈是否为空(栈是从 0 开始存)
if(tt > 0) not empty;
else empty;
// 栈顶元素
stk[tt];

//******队列*****//
// 队尾插入，队头弹出
int q[N], hh, tt = -1;//队头，队尾
// 插入
q[++tt] = x;
// 弹出
hh ++;
//判断是否为空
if(hh <= tt) not empty;
else empty;
// 取队头队尾
q[hh], q[tt];

//******单调栈*****//
// 求序列中数左边(右边)离他最近且比他小(大)的数
int stk[N], tt;
int main(){
    int n; 
    // cin.tie(0);
    // ios::sync_with_stdio(false);读入优化
    cin >> n;  
    while(n--){
        int x; cin >> x;
    	while(tt && stk[tt] >= x) tt --;//tt > 0, 栈非空并且栈顶比当前输入大，直接可忽略栈顶
    	if(tt > 0) cout << stk[tt] <<" ";
    	else cout << -1 << " ";
    	stk[++tt] = x;
    }
}
//******单调队列*****//
// 求滑动窗口中的最小最大值
int a[N], q[N]; // 队列中存的是数组元素的下标
int main(){
    int n, k; cin>>n>>k;
    int hh = 0, tt = -1;
    for(int i=0; i<n; i++){
        cin >> a[i];
        if (hh <= tt && i - k + 1 > q[hh]) hh++;  // 保证队列中有 k 个元素，每次队首出，hh加1
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;    // 若队尾不单调，tt减1,即表示尾元素已经不可能成为最小值，
        q[++ tt] = i;                                  // 下标加到队尾
        if (i >= k-1) cout<< a[q[hh]];       // 输出结果
    }

}

kmp

原串 $s$， 模式串 $p$​

$next[i] = j$​ 的含义是对于模式串：$p[1,j]=p[i-j+1,i]$​

# include<iostream>
using namespace std;
const int N = 10010, M = 100010;
char p[N], s[M]; // 下标均从 1 开始
int ne[N];
int main(){
    cin >> n >> p+1 >> m >> s+1;
    // 求 next 数组，next[1] = 0;
    for(int i=2, j=0; i <= n; i++){
        while(j > 0 && p[i] != p[j+1]) j = ne[j]; // ne[j] 一定小于 j
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    // KMP 匹配过程
    for(int i=1, j=0; i <= m; i++){
        while(j > 0 && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j ++;
        if(j == n){
			// 匹配成功
            cout << i - m + 1 << " ";//输出匹配下标(下标是从 1 开始的)
            j = ne[j];
        }
    }
}

Q.E.D.