滴滴笔试 21年3月20日

没想到选择题 一个三分占60分 编程两道才 40分

选择

感觉选择好多不会啊
有java基础
操作系统线程相关
然后有Linux命令选择
别的记不太清了

编程

第一题 A了

把 26个字母 从后往前 第一次出现的顺序 记住
然后 把第一个 不是a 的换成 他前面的字母
反正就是这个意思 一下就过了

#include<iostream>
using namespace std;
int num[300];
int main(){
    string s;
    cin>>s;
    for(int i= s.size()-1;i>=0;i--){
        if(num[s[i]]==0)num[s[i]]=i;
    }
//    for(int i='a';i<='z';i++){
//        cout<<num[i]<<" "<<i<<endl;
//    }
    int flag=0;
    for(int i=0;i<s.size();i++){
        if(flag==1){
            break;
        }
        if(s[i]=='a')continue;
        else{
            for(int j='a';j<s[i];j++){

                if(num[j]>i){
                //cout<<num[j]<<": "<<i<<endl;
                    flag=1;
                    s[num[j]]=s[i];
                    s[i]=j;
                    cout<<s<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<s;
    return 0;
}

第二题 过了63%

我觉得是连通图的题但是我不会
我对并查集有点印象 就用并查集暴力做的
过了百分之27 然后优化了许多 vector 之类的内存和 findfather 调用的次数（因为我忘了并查集是啥了 所以写的 不优雅）
最后显示 超时超限 过了百分之63

我发现全部输出NO 能拿百分之9

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int vv[1005];
int path[100005][2];
int findfa(int a){
    if(a!=vv[a]){
        vv[a]=findfa(vv[a]);
    }return vv[a];
}
int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n,m;
        cin>>n>>m;
        //vector<vector<int> >node(n,vector<int>(n));
        //vector<vector<int> >path(m,vector<int>(2));
        //set<int>st;
        int flag=1;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            //node[a-1][b-1]=1;
            //node[b-1][a-1]=1;
            path[i][0]=a-1;
            path[i][1]=b-1;
        }
        for(int i=0;i<m;i++){
            int a,b;
            //vector<int>vv(n,999);
            for(int j=0;j<n;j++){
                vv[j]=j;
            }
            for(int j=0;j<m;j++){
                if(flag==0){
                    break;
                }
                if(j==i){
                    continue;
                }
                a=path[j][0];
                b=path[j][1];
                int fa = findfa(a);
                int fb = findfa(b);
                if(fa<fb){
                    vv[fb]=fa;
                    //findfa(fb,vv);
                }else {
                    vv[fa]=fb;
                    //findfa(fa,vv);
                }
                //cout<<a<<vv[a]<<" "<<b<<vv[b]<<endl; 

            }
            for(int i=0;i<n;i++){
                //cout<<findfa(i,vv)<<"  "<<i<<endl;
                if(findfa(i)!=0){
                    flag=0;
                }
            }
        }
        if(flag==0){
            cout<<"No"<<endl;
        }else{
            cout<<"Yes"<<endl;
        }

    }
    return 0;
}