[数据结构与算法]【AC Saber】数据结构

单链表

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],head,idx,m;
void init()
{
    head=-1;
    idx=0;
}
void add_head(int k)
{
    e[idx]=k,ne[idx]=head,head=idx++;
}
void add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(int k)
{
    ne[k]=ne[ne[k]];
}
int main(void)
{
    cin>>m;
    init();
    while(m--)
    {
        string op; cin>>op;
        if(op=="H")
        {
            int x; cin>>x;
            add_head(x);
        }
        if(op=="D")
        {
            int k; cin>>k; 
            if(k) remove(k-1);
            else head=ne[head];//头结点的特殊情况
        }
        if(op=="I")
        {
            int k,x; cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
    return 0;    
}

双链表

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx,n;
void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}
void add(int k,int x)
{
    e[idx]=x,r[idx]=r[k],l[r[k]]=idx,l[idx]=k,r[k]=idx++;
}
void remove(int k)
{
    l[r[k]]=l[k];
    r[l[k]]=r[k];
}
int main(void)
{
    cin>>n;
    init();
    while(n--)
    {
        string op; cin>>op;
        if(op=="L")
        {
            int x;cin>>x;
            add(0,x);
        }
        if(op=="R")
        {
            int x; cin>>x;
            add(l[1],x);
        }
        if(op=="D")
        {
            int x; cin>>x;
            remove(x+1);
        }
        if(op=="IL")
        {
            int k,x; cin>>k>>x;
            add(l[k+1],x);
        }
        if(op=="IR")
        {
            int k,x; cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
    return 0;
}

栈

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],tt,n;
int main(void)
{
    cin>>n;
    while(n--)
    {
        string op; cin>>op;
        if(op=="push")
        {
            int x; cin>>x;
            a[tt++]=x;
        }
        if(op=="pop") tt--;
        if(op=="empty") 
        {
            if(tt) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        if(op=="query") cout<<a[tt-1]<<endl;
    }
    return 0;
}

队列

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],l,r,n;
int main(void)
{
    cin>>n;
    while(n--)
    {
        string op; cin>>op;
        if(op=="push")
        {
            int x; cin>>x;
            a[r++]=x;
        }
        if(op=="pop") l++;
        if(op=="empty")
        {
            if(r==l) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        if(op=="query") cout<<a[l]<<endl;
    }
    return 0;
}

单调栈

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
stack<int>st;
int main(void)
{
    int n; cin>>n;
    while(n--)
    {
        int x; cin>>x;
        while(st.size()&&st.top()>=x) st.pop();
        if(st.size()&&st.top()<x) cout<<st.top()<<" ";
        else cout<<"-1 ";
        st.push(x);
    }
}

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],tt,n;
int main(void)
{
    cin>>n;
    while(n--)
    {
        int x; cin>>x;
        while(a[tt]>=x) tt--;
        if(tt) cout<<a[tt]<<" ";
        else cout<<-1<<" ";
        a[++tt]=x;
    }
    return 0;
}

单调队列

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+10;
int a[N],n,k;
deque<int>qe,temp;
int main(void)
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(qe.size()&&i-k+1>qe.front()) qe.pop_front();
        while(qe.size()&&a[qe.back()]>=a[i]) qe.pop_back();
        qe.push_back(i);
        if(i>=k)  cout<<a[qe.front()]<<" ";
    }
    cout<<endl;
    qe=temp;
    for(int i=1;i<=n;i++)
    {
        if(qe.size()&&i-k+1>qe.front()) qe.pop_front();
        while(qe.size()&&a[qe.back()]<=a[i]) qe.pop_back();
        qe.push_back(i);
        if(i>=k)  cout<<a[qe.front()]<<" ";
    }
    return 0;
}

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],a[N],hh,tt=-1;
int main(void)
{
    int n,k; cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[i]<a[q[tt]]) tt--;
        q[++tt]=i;
        if(i+1>=k) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    
    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[i]>a[q[tt]]) tt--;
        q[++tt]=i;
        if(i+1>=k) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    return 0;
}

KMP

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10,M=1e6+10;
char p[N],s[M];
int ne[N];
int n,m;
int main(void)
{
	cin>>n>>p+1>>m>>s+1;
	
	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;
	}
	
	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)
		{
			j=ne[j];
			cout<<i-n<<" ";
		}
	}
	return 0;
}