【美团笔试】2022-09-11 题解

Debug完了,第一题找到一个O(n)时间复杂度的方法,满足能被11整除的条件是奇数位之和与偶数位之和做差的绝对值能被11整除。这样的话我们可以用末尾是偶数且能被11整除来计算有多少子串,从前往后扫一遍就可以。明天写一下。
第一题:判断一个字符串中能有多少被22整除的子串。【通过率82%】

#include <iostream>

char str[100005];

int get_sub_num(int start) {
    int cnt = 0;
    int sum = 0;

    for (int i = start; str[i]; i++) {
        sum += str[i] - '0';

        if (sum % 22 == 0) {
            cnt++;
        }
        sum %= 22;
        sum *= 10;
    }

    return cnt;
}

int main() {

    scanf("%s", str);

    int cnt = 0;

    for (int i = 0; str[i]; i++) {
        cnt += get_sub_num(i);
    }

    printf("%d", cnt);

    return 0;
}

由于第一题我们不知道测评里具体的输入和输出,没办法保证我们的答案是否是正确的,因此我写了一个对数器,correct函数穷举了字符串的所有子串,对每个子串进行了判断。新的方法将写在my_function中。

#include <iostream>
#include <ctime>
#include <cmath>

const int STRING_LENGTH = 100005;

void generate(char* str, int length) {
    srand(time(NULL));

    char num = rand() % 9 + 1 + '0';

    str[0] = num;

    for (int i = 1; i < length; i++) {
        str[i] = rand() % 10 + '0';
    }
    str[length] = 0;

}

int get_sub_num(char* str, int start) {
    int cnt = 0;
    int sum = 0;

    for (int i = start; str[i]; i++) {
        sum += str[i] - '0';

        if (sum % 22 == 0) {
            cnt++;
        }
        sum %= 22;
        sum *= 10;
    }

    return cnt;
}

int correct(char* str) {
    int cnt = 0;

    for (int i = 0; str[i]; i++) {
        cnt += get_sub_num(str, i);
    }

    return cnt;
}

int my_function(char* str) {
    int result =
    // input your code here.


    return 2;
}

int main() {
    char* str = (char*)malloc(sizeof(char) * STRING_LENGTH);
    generate(str, 100);

    printf("%s\n", str);

    int right = correct(str);
    int left = my_function(str);

    printf("left:%d right:%d\n", left, right);

    if (right == left) {
        printf("correct\n");
    }
    else {
        printf("failed\n");
    }

    return 0;
}

第二题:判断地铁中每一站有多少与其直接相连。【通过率100%】

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int near[100005];
int index[100005];

int main() {

    unordered_map<string, int> mp;

    int n = 0;
    int m = 0;
    int q = 0;

    scanf("%d%d%d", &n, &m, &q);

    for (int i = 0; i <= n; i++) {
        index[i] = i;
    }

    for (int i = 0; i < m; i++) {
        int u = 0;
        int v = 0;

        scanf("%d%d", &u, &v);

        if (u > v) {
            swap(u, v);
        }

        string s = to_string(u) + ',' + to_string(v);

        if (mp[s] == 1) {
            continue;
        }

        mp[s] = 1;
        near[u]++;
        near[v]++;
    }

    for (int i = 0; i < q; i++) {
        int x = 0;
        int y = 0;

        scanf("%d%d", &x, &y);

        swap(index[x], index[y]);

    }

    for (int i = 1; i <= n; i++) {
        printf("%d ", near[index[i]]);
    }

    return 0;
}

第三题:计算愉悦值。【通过率100%】

#include <iostream>
#include <cstring>

using namespace std;

int musicIndex[100005];

int main() {

    int n = 0;
    int K = 0;

    scanf("%d%d", &n, &K);

    for (int i = 0; i < 100005; i++) {
        musicIndex[i] = 1;
    }

    int result = 0;

    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);

        if (musicIndex[c] == d) {
            result += a;
            musicIndex[c]++;
            continue;
        }

        result += max(a - b, -K);

    }

    printf("%d", result);

    return 0;
}

第四题:字符串的第k小周期。【通过率100%】

#include <iostream>
#include <cstring>

using namespace std;

char str[100005];

bool isCycle[100005];

int require(int u, int v){
    memset(isCycle, 0, sizeof(isCycle));

    for(int i = 1; i <= u; i++){

        if(isCycle[i]){
            continue;
        }

        bool flag = true;

        for(int j = 0; j < u - i; j++){
            if(str[j] != str[j + i]){
                flag = false;
                break;
            }
        }

        if(!flag){
            continue;
        }

        for(int j = 1; j * i <= u; j++){
            isCycle[j * i] = true;
        }

    }

    int cnt = 0;
    int result = -1;

    for(int i = 1; i <= u; i++){

        if(!isCycle[i]){
            continue;
        }

        cnt++;
        if(cnt == v){
            result = i;
            break;
        }

    }

    return result;

}

int main(){

    scanf("%s", str);

    int n = 0;

    scanf("%d", &n);

    int u = 0;
    int v = 0;

    while(n--){
        scanf("%d%d", &u, &v);

        printf("%d\n", require(u, v));

    }

    return 0;
}

第五题:给一串数字,分割为k段后分别进行排序,可得到一升序有序序列,问k最大为多少
感觉单调栈可以做。

全部评论
这第四题做法也太暴力了吧,,,,
点赞 回复 分享
发布于 2021-09-12 07:07

相关推荐

落叶随风呀:学校不好就放两栏,专业能力往前移, 政治面貌不是党员不如不写,籍贯湖南衡阳,或者湖南,浅尝辄止 基本信息排版不够美观,没有对齐 简历上花里胡哨的东西去掉 项目我不评价,因为我能力有限,且对mcu了解不足 但是这份简历掌握的水平,你可以海投试试,工作没问题但是工资应该不会高,因为搞mcu的小公司多
点赞 评论 收藏
分享
生命诚可贵:先不说内容怎么样 排版就已经太差劲了 第一眼看不到重点,第二眼已经没有再看的耐心了, 篇幅占的太满了 字体不要用灰色 观感不好 想重点突出的黑色加粗就可以了 多列要点 少些大段的句子 项目经历把项目用的技术要点列出来,光写个python plc什么的太宽泛了 自我评价也有点偏多
点赞 评论 收藏
分享
03-16 11:19
已编辑
门头沟学院 Java
已经一年没发牛客了,为什么呢,因为没脸发...&nbsp;一年前的我自认为在25届中技术一流,八股无敌,项目出色,但是一年校招的蹉跎让我差点转行。24年春招收割了十几个实习&nbsp;offer&nbsp;之后我去了某家大厂实习到9月份转正失败,那时候的我还没有意识到噩梦将来,7月因为投秋招提前批没反馈,于是开始投了几个实习转正岗位练手又拿了3个中大厂&nbsp;offer,这时的我沉浸在我自以为是的骄傲里。9月秋招正式批开始后我几乎把我能找到的所有的岗位都投了一遍,只收获了大厂海笔,0面试。10月份第一家给我面试的公司是数字马力(蚂蚁的内包),诚恳的说,当时收到这家面试是嚣张的,觉得我拿这个&nbsp;offer&nbsp;如探囊取物,就当个保底吧。...
中街牛奶提子:是啊,不应该在秋招的时候继续投实习岗。也劝26届的,八月末后,实习岗就不应该投,给人错误的行情认知。佬是学院本,觉得约面难,双非何尝不是一样呢,秋招战场的激烈和实习完全不同。当时我秋招的时候也是边面实习,当时面实习面一个过一个觉得自己很优越,觉得能收获一堆实习offer那秋招肯定也行。为什么要在秋招拿一堆实习offer增强自己所谓的虚荣心,当时就是贱,为了所谓的攀比虚荣心
点赞 评论 收藏
分享
评论
2
25
分享

创作者周榜

更多
牛客网
牛客企业服务