王道代码题

1

#include<iostream>

using namespace std;

const int N=100010;
int a[N];

int del(int a[],int &n){
    int min=a[0];
    int pos=0;

    for(int i=0;i<n;i++){
        if(a[i]<min){
        swap(min,a[i]);
        pos=i;
        }
    }

    a[pos]=a[n-1];
    n--;

    return min;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    if(n==0) cout<<"error"<<endl;
    else{
        int min=del(a,n);
        cout<<min;
        for(int i=0;i<n;i++) cout<<a[i];
        cout<<endl;
    }

    return 0;
}

2

//逆置顺序表
#include<iostream>

using namespace std;

const int N=100010;
int a[N];

void reverse(int a[],int n){
    for(int i=0;i<n/2;i++)//i的范围是0～n/2-1
        swap(a[i],a[n-i-1]);
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    reverse(a,n);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;

    return 0;
}

3

//时间复杂度O(n),空间复杂度O(1)
#include<iostream>

using namespace std;

const int N=100010;
int a[N];

void del(int a[],int &n,int x){
    for(int i=0,j=0;i<n;i++){
        if(a[i]!=x){//不等于x的时候才需要复制，等于时直接跳过
            a[j]=a[i];
            j++;
        }
    }
    n=j;
}

int main(){
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++) cin>>a[i];

    del(a,n,x);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;

    return 0;
}

4

#include<iostream>

using namespace std;

const int N=100010;
int a[N];

void del(int a[],int &n,int s,int t){
    for(int i=0;j=0;i<n;i++){
        if(a[i]<s&&a[i]>t){
            a[j]=a[i];
            j++;
        }
    }
    n=j;
}

int main(){
    int n,s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++) cin>>a[i];

    if(s>=t||n==0) cout<<"error"<<endl;
    else del(a,n,s,t);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;

    return 0;
}

6

#include<iostream>

using namespace std;

const int N;
int a[N];

void del(int a[],int &n){
    for(int i=1;j=0;i<n;i++){
        if(a[i]!=a[j]){
            j++;
            a[j]=a[i];
        }
    }
    n=j+1;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    del(a,n);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;

    return 0;
}

7

#include<iostream>

using namespace std;

const int N;
int n[N];
int k;

void merge(int a[],int n,int b[],int m){
    int i=0,j=0;
    while(i<n&&j<m){
        if(a[i]<b[j]){
            n[k]=a[i];
            i++;
        }
        else{
            n[k]=b[j];
            j++;
        }
        k++;
    }

    while(i<n){
        n[k]=a[i];
        i++;
        k++;
    }
    while(j<m){
        n[k]=b[j];
        j++;
        k++;
    }
}

int main(){
    int n,m;
    cin>>n>>m;

    int a[n],b[m];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];

    merge(a,n,b,m);

    for(int i=0;i<k;i++) cout<<n[i]<<' ';
    cout<<endl;

    return 0;
}

#include<iostream>
#include<vector>

using namespace std;

vector<int> merge(vector<int> &a,vector<int> &b){
    vector<int> res;

    int i=0,j=0;
    while(i<a.size()&&j<b.size()){
        if(a[i]<b[j]){
            res.push_back(a[i]);
            i++;
        }
        else{
            res.push_back(b[j]);
            j++;
        }
    }

    while(i<a.size()){
        res.push_back(a[i]);
        i++;
    }
    while(j<b.size()){
        res.push_back(b[j]);
        j++;
    }

    return res;
}

int main(){
    vector<int> a={1,3,5,7,8,9};
    vector<int> b={2,3,4,6,8};

    vector<int> res=merge(a,b);

    for(int i=0;i<res.size();i++) cout<<res[i]<<' ';
    cout<<endl;

    return 0;
}

8

#include<iostream>
#include<vector>

using namespace std;

vector<int> exchange(vector<int> &a,int m,int n){
    vector<int> res;

    for(int i=0;i<n;i++) res.push_back(a[i+m]);
    for(int j=0;j<m;j++) res.push_back(a[j]);

    return res;
}

int main(){
    vector<int> a={1,3,5,7,8,9,0,4,6,7,3,8};
    int m=5,n=7;

    vector<int> res=exchange(a,m,n);
    for(int i=0;i<res.size();i++) cout<<res[i]<<' ';
    cout<<endl;

    return 0;
}

9 该题应用到了二分

10
时间复杂度O(p):p个元素出队再入队while(p–)
空间复杂度O(n):队长为n

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int n,p;
    cin>>n>>p;
    queue<int> q;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        q.push(x);//输入元素依次入队
    }

    while(p--){
        int y=q.front();//读取队首元素
        q.pop();//出队
        q.push(y);//原对首元素再从队尾入队
    }

    for(int i=0;i<n;i++){
        cout<<q.front()<<' ';
        q.pop();
    }

    return 0;
}

11.

12