【美团笔试】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最大为多少
感觉单调栈可以做。