单链表

静态链表-数组实现

 #include<iostream>

using namespace std;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
const int N=1e5+9;
int head,e[N],nex[N],idex;

void initial(){
    head=-1;
    idex=0;
}

void to_head(int val){//先右后左
    e[idex]=val;    nex[idex]=head;    head=idex;  idex++;
}
// 将下标是k的点后面的点删掉
void del(int k){
     nex[k]=nex[nex[k]];
}
// 将x插到下标是k的点后面
void in(int k,int val){
    e[idex]=val;nex[idex]=nex[k];nex[k]=idex;idex++;
}
int main(){
    int n;
    cin>>n;
    initial();
    while(n--){
        char x;
        cin>>x;

        int k,val;
        if(x=='H'){
            cin>>val;
            to_head(val);
        }
        else if(x=='D'){
            cin>>k;
            if(!k)head =nex[head];//特判删除节点为头节点
            else del(k-1);
        }
        else if(x=='I'){
            cin>>k>>val;
            in(k-1,val);
        }
    }
    //遍历数组式链表
    for(int i=head;i!=-1;i=nex[i])cout<<e[i]<<' ';
    return 0;
}

双链表

头节点idx为0；尾节点idx为1；

#include<iostream>
#include<string>
using namespace std;
const int N=1e5+9;

int le[N],ri[N],e[N],idx;

// 在节点k的右边插入一个数val
//先本身，再右边，后左边(k)
void in(int k,int val){
    e[idx]=val;ri[idx]=ri[k];le[idx]=k;
    le[ri[k]]=idx;
    ri[k]=idx++;
}
//删除节点k
void del(int k){
    le[ri[k]]=le[k];
    ri[le[k]]=ri[k];
}
int main(){
    idx=2;
    ri[0]=1;le[1]=0;

    int m;cin>>m;
    int val,k;
    string s;
    while(m--){
        cin>>s;
        if(s=="L"){
            cin>>val;
            in(0,val);
        }
        else if(s=="R"){
            cin>>val;
            in(le[1],val);
        }
        else if(s=="D"){
            cin>>k;
            del(k+1);
        }
        else if(s=="IL"){
            cin>>k>>val;
            in(le[k+1],val);
        }
        else if(s=="IR"){
            cin>>k>>val;
            in(k+1,val);
        }
    }
    for(int i=ri[0];i!=1;i=ri[i])cout<<e[i]<<' ';
}

栈

子弹匣 -先进后出
pop push empty query

#include<iostream>
using namespace std;

const int N=1e5+9;

int tt,e[N],top;

int main(){
    int m;cin>>m;
    string a="push",b="pop" ,c="empty",d="query";
    int val;
    string s;
    while(m--){
        cin>>s;
        if(s==a){
            cin>>val;
           e[tt++]=val;
        }
        else if(s==b){
            tt--;
        }
        else if(s==c){
            if(tt==0)cout<<"YES\n";
            else cout<<"NO\n";
        }
        else if(s==d){
            cout<<e[tt-1]<<'\n';
        }
    }
    return 0;
}

单调栈

题：输出每个数左边第一个比它小的数，如果不存在则输出 −1。
思：每次输入新的数，先判断其与原栈的关系 -> 原栈形成单增栈

#include<iostream>
using namespace std;
const int N=1e5+9;

int stk[N],tt;

int main(){
    int m,val;
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>val;
        while(tt && val<=stk[tt])tt--;
        if(!tt)printf("-1 ");
        else printf("%d ",stk[tt]);
        stk[++tt]=val;
    }
    return 0;
}

队列

排队-先进后出

#include<iostream>
using namespace std;

const int N=1e5+9;
int e[N],tt=-1,hh=0;
int main(){
    int m;
    cin>>m;
    string op;
    int k;
    while(m--){
        cin >> op;
        if (op == "push")
        {
          cin>>k;e[++tt]=k;
        }
        else if (op == "pop")hh++; 
        else if (op == "empty") cout<<(hh<=tt?"NO":"YES")<<'\n';
        else cout<<e[hh]<<'\n';
    }
    return 0;
}

单调队列

题：你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

 #include<iostream>

using namespace std;
const int N=1e6+9;
//yuan[N]记录原数组(值)  que[N]记录单调队列（下标）
int yuan[N],que[N],front,endd=-1;
int main(){
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",&yuan[i]);

   for(int i=0;i<n;i++){
        if(front <=endd &&i-k+1>que[front])front++; //当单调队列头下标已出区间，将头下标移动
        while(front <= endd && yuan[que[endd]]>=yuan[i])endd--; //根据新的数，更新单调队列
        que[++endd]=i;  //入队
        if(i>=k-1)printf("%d ",yuan[que[front]]);
    }puts("");

    front =0;endd=-1;
    for(int i=0;i<n;i++){
        if(front <=endd &&i-k+1>que[front])front++;
        while(front <= endd && yuan[que[endd]]<=yuan[i])endd--;
        que[++endd]=i;
        if(i>=k-1)printf("%d ",yuan[que[front]]);
    }puts("");

}

KMP字符串

/*
字符串的前缀：符号串左部的任意子串（或者说是字符串的任意首部）
字符串的后缀：符号串右部的任意子串（或者说是字符串的任意尾部）

引用了百度的内容, 举例子, “abcde”,前缀包括但不限于: {a},{ab},{abc}..{abcde},后缀同理{e},{de},{cde}.
当我们限定 j为最后一个字母的下标,也就是变成 [1~j]的前缀和后缀的问题.

*/

#include<iostream>

using namespace std;

const int N=1e5+9,M=1e6+9;

char zi[N],mu[M];
int nex[N];

int main(){
    //KMP 下标从1开始
    int n,m;cin>>n>>zi+1>>m>>mu+1;

    //求nex[N]数组
    for(int i=2,j=0;i<=n;i++)
    {
        while( j &&zi[i]!=zi[j+1])j=nex[j];
        if(zi[i]==zi[j+1])j++;
        nex[i]=j;
    }
    //for(int i=0;i<=n;i++)cout<<nex[i]<<" \n"[i==n];
    //KMP匹配

    for(int i=0,j=0;i<=m;i++)
    {
        while(j && mu[i]!=zi[j+1] )j=nex[j];//不匹配->回退->匹配
        if(mu[i]==zi[j+1])j++;
        if(j==n){
            printf("%d ",i-n );
            j=nex[j];
        }
    }
}

Trie树

Trie 本质上是一颗多叉树(摘录)

idx 辅助构建前后节点的链式关系
son[N][26] 数组的理解：
第一维是当前节点所在行数
第二维是当前节点携带的哪个字母
其值作为指针 表示下一个节点所在行数

son[N][26] 相当于把一维的单链表升维了
把 ne[N] 和 e[26] 混合到一起
因此 son[N][26] 可以看做多个单链表(树中每个叶节点到根节点的路径均可看成一个单链表)
每次 insert 时, 其实是在对其中某个单链表进行后插操作(0 为空)(这里后插可以看成一种暴力占据)

注：1.之所以单链表不这么做，是因为空间浪费
而 Trie 本质上是一个多叉树, 可以使得二维数组得到充分的利用
2. 当 son[p] 有非 0 值时, 其实已经将 p 一整行占据(不能通过其他前缀的字符串到达)
因此 cnt[p] 是该前缀的出现的次数

#include<iostream>

using namespace std;

const int N=2e4+9;
//类似链表
int sun[N][26],cnt[N],idx;
char aa[N];
void insert(char str[]){
    int p =0;
    for(int i=0; str[i]; i++){
        int u=str[i] - 'a';
        if(! sun[p][u] )sun[p][u]=++idx;//无路开路
        p=sun[p][u];
    }
    //记录以该字母结尾的单词数量
    cnt[p]++;
}

int query(char str[]){
    int p=0;
    for(int i=0;str[i];i++){
        int u=str[i]- 'a';
        if(! sun[p][u] )return 0;//无路返回
        p=sun[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    cin>>n;
    char op[2];
    while(n--){
        cin>>op>>aa;
        if(op[0]=='I')insert(aa);
        else cout<<query(aa)<<'\n';
    }
    return 0;
}

并查集

并查集：
1.将两个集合合并
2.询问两个元素是否在一个集合当中
时间复杂度近乎O(1)

基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点储存它的父节点，p[x]表示x的父节点。
问题1：如何判断树根：if(p[x] == x)
问题2：如何求x的集合编号：while(p[x] != x) x = p[x];(常用优化方法：路径压缩)
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y;

#include<iostream>

using namespace std;

const int N=1e5+9;

int p[N];
int find (int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)p[i]=i;

    char op[2];int a,b;
    while(m--){
        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");
        }
    }
}

现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；

#include<iostream>

using namespace std;

const int N=1e5+9;

int p[N],cnt[N];

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n ,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)p[i]=i,cnt[i]=1;

    char op[2];int a,s;

    while(m--){
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d",&a,&s);
            if(find(a)==find (s))continue;
            cnt[find(a)]+=cnt[find(s)];
            p[find(s)]=find(a);
        }
        else if(op[1]=='1'){
            scanf("%d%d",&a,&s);
            puts(find(a)==find(s)?"Yes":"No");
        }
        else {
            scanf("%d",&a);
            printf("%d\n",cnt[find(a)]);
        }
    }
}

堆

如何手写一个堆？
1.插入一个数 2.求集合当中的最小值3.删除最小值
4.删除任意一个元素 5.修改任意一个元素

插入/删除 log(n) 求最小值O(1)
小根堆 根最小 左儿子 2^n 右儿子 1 + 2^n

#include<iostream>

using namespace std;

const int N=1e5+9;

int dui[N],count;
int down(int i){
    int u=i;
    //将要下沉下标的值与左右儿子比较，找出最小的
    if(u*2 <= count && dui[u*2]<dui[i])i=u*2;
    if(u*2 +1 <=count && dui[u*2+1]<dui[i] )i=u*2+1;
    if(i!=u){//如果下标i非最小，交换并继续下沉
        swap(dui[i],dui[u]);
        down(u);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&dui[i]);

    count=n;
    for(int i=n/2;i>0;i--)down(i);

    while(m--){
        printf("%d ",dui[1]);
        dui[1]=dui[count];//输出一次，弹出一个最小值
        count--;
        down(1);//下沉头下标
    }
    return 0;
}