滴滴笔试 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;
}
#笔经##滴滴##Java#

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-14 18:10
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-31 20:32
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
3 14 评论
分享

全站热榜

正在热议