首页 > 2020.09.13滴滴秋招笔试(2简单编程题 AK)
头像
joshua0509
编辑于 2020-09-14 11:34
+ 关注

2020.09.13滴滴秋招笔试(2简单编程题 AK)

第一部分:选择题20个,每个3分,一共60分;(选择题有几个不会选,难道专门卡100分吗?)
第二部分:2道编程题,每个20分;(AK)
总分:100分;

编程题 AK:
第一题:签到题,给一个字符串,给一个整数k, 每k个进行翻转,最后剩下的不足k个也翻转
思路:直接模拟,一开始不知道输入哪里出问题,总是90%,后来我直接读入两行串,
第一行转换成整数,第二行就是要操作的字符串,详细看代码:
别着急,先看一下截图的一直卡90%,有点泪奔,虽然AC了,但是这个串的输入处理有点闹腾啊!!!

代码:
#include<bits/stdc++.h>
using namespace std;

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif

    int k;
    string s;
    while(getline(cin, s)) {
        stringstream ss(s);
        ss >> k;
        getline(cin, s);
        int n = s.size();

        int l = 0;
        int r = k - 1;
        int i;
        int j;
        while(r < n) {
            i = l;
            j = r;
            while(i < j) swap(s[i++], s[j--]);
            l = r + 1;
            r = l + k - 1;
        }
        if(l < n) {
            i = l;
            j = n-1;
            while(i < j) swap(s[i++], s[j--]);
        }
        cout << s << endl;
    }
    return 0;
}


第二题:n个岛屿,m个桥进行连接,桥超过k长度的就不能连接,问最后n个岛屿是否能连通
思路:简单题,最小生成树树 + 并查集,本质就是最小生成树,直接把所有的边存起来,然后一个sort,然后依次检查就行,满足n-1条边就结束
最后根据建成的数量是否等于n-1 直接得出是否能成功
代码:
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false),cin.tie(0);
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
ll qpow(ll x, ll y)   { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
ll qpow(int x, int y) { int a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
template <typename T>
inline void read(T &x) {
    char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} 
    while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;
}

const int maxn = 1005;
int f[maxn];
struct Node {
    int u;
    int v;
    int w;
    Node(){u = 0; v = 0;}
    Node(int u, int v, int w):u(u),v(v),w(w){}
};
Node edge[maxn];
int n;
int m;
int k;

int find(int x) {
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
void merge(int u, int v) {
    int fu = find(u);
    int fv = find(v);
    f[u] = min(fu, fv);
    f[v] = min(fu, fv);
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif

    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m >> k;
        for(int i = 0; i < m; ++i) cin >> edge[i].u >> edge[i].v >> edge[i].w;
        sort(edge, edge + m, [](const Node& l, const Node& r){return l.w < r.w;});

        if(edge[0].w > k) {
            cout << "No" << endl;
            continue;
        }
        for(int i = 1; i <= n; ++i) f[i] = i;
        int cnt = 0;
        for(int i = 0; i < m; ++i) {
            if(edge[i].w > k) break;
            int fu = find(edge[i].u);
            int fv = find(edge[i].v);
            if(fu == fv) continue;

            merge(fu, fv);
            cnt++;
            if(cnt == n-1) break;
        }
        if(cnt == n-1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    
    return 0;
}

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐