头像

struggle


访客:2322

离线:1小时前



#include<iostream>
using namespace std;
const int min1=1e5+10,max1=1e6+10;
char s[max1],p[min1];
int nex[max1];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>p+1>>m>>s+1;
    //最长前后缀长度
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[j+1]!=p[i]) j=nex[j];
        if(p[j+1]==p[i]) j++;
        nex[i]=j;
    }
    //字符串匹配
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && p[j+1]!=s[i]) j=nex[j];
        if(p[j+1]==s[i]) j++;
        if(j==n)
        {
            cout<<i-n<<' ';
            j=nex[j];
        }
    }
    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

#include<iostream>
using namespace std;
const int P=1e5+10,S=1e6+10;
char s[S],p[P];
int next1[S];
int main()
{
    int n,m;//n为p的长度 m为s的长度
    cin>> n >> p + 1 >> m >> s + 1;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[j+1]!=p[i]) j=next1[j];
        if(p[j+1]==p[i]) j++;
        next1[i]=j;
    }
    //匹配过程
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && p[j+1]!=s[i]) j=next1[j];
        if(p[j+1]==s[i]) j++;
        if(j==n)
        {
            //匹配成功
            cout<<i-n<<' ';
            //继续匹配
            j=next1[j];
        }
    }

    return 0;
}



#include<iostream>
using namespace std;
int settle(int n)//当阶梯数为n时,共有几种走法
{
    //当阶梯数只有1的时候,只能走1阶
    if(n==1) return 1;
    //当阶梯数为2的时候,可以先走1阶再走1阶,也可以直接走2阶.所以2种
    else if(n==2) return 2;
    //递归处理
    return settle(n-1)+settle(n-2);
}
int main()
{
    int n;
    cin>>n;
    cout<<settle(n);
    return 0;
}



1.快速排序 quick_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void quick(int *a,int l,int r)
{
    if(l>=r) return;
    int l1=l-1,r1=r+1;
    int x=a[(l+r)>>1];
    while(l1<r1)
    {
        do l1++;while(a[l1]<x);
        do r1--;while(a[r1]>x);
        if(l1<r1) swap(a[l1],a[r1]);
    }
    quick(a,l,r1),quick(a,r1+1,r);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    quick(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

2.希尔排序 shell_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void shell(int *a,int l,int r)
{
    int step=1;
    if(step<(r-l+1)/3) step=3*(r-l+1)+1;
    while(step>=1)
    {
        for(int i=l+step;i<=r;i++)
        {
            for (int ii = i; ii - step >= l && a[ii-step]>a[ii]; ii -= step)
                swap(a[ii-step],a[ii]);
        }
        step/=2;
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    quick(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}



#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
//利用next_permutation()进行元素全排列时,想要得到区间内容的所有排列组合,应从最初的顺序开始
    vector<int> a;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) a.push_back(i);
    do
    {
        for(int i=0;i<n;i++) cout<<a[i]<<' ';
        cout<<endl;
    }while(next_permutation(a.begin(),a.end()));

    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];
int main()
{
    int tt = -1, hh=0;//hh队列头 tt队列尾
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 0; i <n; i ++) cin>>a[i];
    for(int i = 0; i < n; i ++)
    {
        //维持滑动窗口的大小
        //当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
        //滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
        while(hh <= tt && k < i - q[hh] + 1) hh ++;
        //构造单调递增队列
        //当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
        //就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    puts("");
    hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k ) printf("%d ", a[q[hh]]);
    }
    return 0;
}




#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
    int tt = -1, hh=0;//hh队列头 tt队列尾
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 0; i <n; i ++) cin>>a[i];
    for(int i = 0; i < n; i ++)
    {
        //维持滑动窗口的大小
        //当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
        //滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
        while(hh <= tt && k < i - q[hh] + 1) hh ++;
        //构造单调递增队列
        //当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
        //就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    puts("");
    hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k ) printf("%d ", a[q[hh]]);
    }
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

#include<iostream>
using namespace std;
const int N=1e5+10;
int stack[N],t;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        while(t && stack[t]>=x) t--;
        if(t) cout<<stack[t]<<' ';
        else cout<<-1<<' ';
        stack[++t]=x;
    }
    return 0;
}



#include<iostream>
using namespace std;
const int N=1e5+10;
int stack[N],t;
int main()
{
    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        //如果stack不为空且栈顶元素>=x,那么此时栈顶元素一定不可能是x左边第一个比它小的数
        //这样一直pop这样的栈顶元素,直到栈顶元素<x位置
        while(t && stack[t] >=x) t--;
        //此时stack中的元素严格单调递增且stack中的数均<X恒成立,当栈不为空时,x左边第一个比它小的数就是
        //栈顶元素
        if(t) cout<<stack[t]<<' ';
        else cout<<-1<<' ';
        stack[++t] =x;
    }
    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

#include<iostream>
using namespace std;
const int N=100010;
int queue[N],t=-1,head;
int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        string opration;
        int x;
        cin>>opration;
        if(opration=="push")
        {
            cin>>x;
            queue[++t] = x;
        }
        else if(opration=="pop")
            head++;
        else if(opration=="empty")
          if(t-head+1!=0) cout<<"NO"<<endl;
          else cout<<"YES"<<endl;
        else cout<<queue[head]<<endl;
    }
    return 0;
}