数据结构练习

Matrix练习

week1

T1:输出螺旋数组

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[10][10]={};
    int i=1,left=1,up=1,right=n,down=n;
    while(i<=n*n){
        for(int j=left;j<=right&&i<=n*n;j++){
            a[up][j]=i;
            i++;
        }
        up++;
        for(int j=up;j<=down&&i<=n*n;j++){
            a[j][right]=i++;
        }
        right--;
        for(int j=right;j>=left&&i<=n*n;j--)
            a[down][j]=i++;
        down--;
        for(int j=down;j>=up&&i<=n*n;j--)
            a[j][left]=i++;
        left++;
    }
    for(i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%3d",a[i][j]);
        printf("\n");
    }
    return 0;
}

T2:压缩技术续集

#include<iostream>

using namespace std;
int n;
int main(){
    string s;
    string ts;
    while(cin>>s)
        ts+=s;
    cout<<s.size()<<" ";
    if(ts[0]=='1') cout<<'0'<<" ";
    int t=1;
    for(int i=1;i<ts.size();i++){
        if(ts[i]==ts[i-1]){
            t++;
        }else{
            cout<<t<<" ";
            t=1;
        }
    }
    cout<<t;
    return 0;
}

T3:丑数

Matrix对应力扣题目：丑数2
洛谷有进阶版，自定义素数集合的丑数：丑数

week2

T4:奶牛转向

差分数组翻转区间，用一个差分数组记录翻转状态，读到对应位置就读取对应位置的翻转状态然后进行翻转。

此题希望快速对“牛的翻转次数”数组进行加减，故对此数组进行差分操作。
随后在遍历的过程中不断对差分数组累加，相当于计算第i头牛的翻转次数。

注意改变差分数组的值时，末尾元素的坐标是第一个不受影响的元素。

#include<iostream>
#include<vector>

using namespace std;
bool cows[5005];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        if(c=='F') cows[i]=1;
        else cows[i]=0;
    }
    //贪心策略，往前不回头，对于给定的序列和K值，可以算出其所需要的操作数
    //Q：那么是不是有一些K值是注定不行的呢？这些K值多还是少呢
    //对于每个K值，计算其操作数的时间复杂度最好是O(N): 快速区间反转，差分思路

    //尝试记录flag:是否需要翻转，顺序遍历即可
    int min_k=1,min_times=n;
    for(int k=1;k<=n;k++){
        int d[5005]={};
        int sum = 0,times=0,possible = 1;
        for(int i=1;i<=n;i++){
            sum+=d[i];
            bool cow = cows[i];
            cow ^= (sum%2);
            if(cow==1) continue;
            else{
                if(i+k-1>n){ 
                    possible = 0;
                    break; 
                }
                sum++;
                d[i+k]--;//翻转从i到i+k-1,翻转效果在i+k处结束
                times++;
            }
        }
        if(times<min_times&&possible){
            min_times = times;
            min_k = k;
        }
    }
    cout<<min_k<<" "<<min_times;
}

week5

T3:移除K位数字

402.移除k位数字

class Solution {
public:
    string removeKdigits(string num, int k) {
        //维护左侧单调递增性
        vector<int>a;
        a.push_back(0);
        for(auto&c:num){
            while(c-'0'<a.back()&&k){
                k--;
                a.pop_back();
            }
            a.push_back(c-'0');
        }
        while(k--){
            a.pop_back();
        }
        string res;
        int flag=0;
        for(auto& n:a){
            if(n!=0) flag=1;
            if(flag){
                res+=n+'0';
            }
        }
        if(res == "")
            return "0";
        return res;
    }
};

T4:合法的出栈序列

类似题目：洛谷【深基15.习9】验证栈序列

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int ru_zhan[100005];
int chu_zhan[100005];

int main(){
    int q;cin>>q;
    while(q--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)
            cin>>ru_zhan[i];
        for(int i=1;i<=n;i++)
            cin>>chu_zhan[i];
        vector<int> s;
        for(int i=1,j=1;i<=n;i++){
            while(s.size()==0||(s.back()!=chu_zhan[i]&&j<=n)){
                s.push_back(ru_zhan[j]);
                j++;
            }
            if(s.back()==chu_zhan[i]){
                s.pop_back();
            }
        }
        if(s.size()){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

week6

T4:滑动窗口

P1886 【模板】单调队列 / 滑动窗口

#include<iostream>
#include<deque>
using namespace std;
int a[1000005]={};
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    deque<int>q;
    for(int i=1;i<=n;i++){
        if(q.size()&&i-q.front()>=k)
            q.pop_front();
        while(q.size()&&a[i]<=a[q.back()]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k)
            cout<<a[q.front()]<<" ";
    }
    cout<<endl;
    q.clear();
    for(int i=1;i<=n;i++){
        if(q.size()&&i-q.front()>=k)
            q.pop_front();
        while(q.size()&&a[i]>=a[q.back()]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k)
            cout<<a[q.front()]<<" ";
    }
    return 0; 
}

week8

T1:KMP

KMP模板