【便利蜂】2022-09-15 题解

AK了，但是代码的时间复杂度不低。而且因为笔试错过了阿里的面试电话。。妈蛋。。而且便利蜂这个真的是，感觉考的不是算法，是解析数据QAQ。
第一题，DP。【100%】

#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using namespace std;

int a[1000];
int dp[10000005];
int target = 0;


int main() {

    int length = 0;

    scanf("%d", a);
    memset(dp, -1, sizeof(dp));

    length++;

    char ch = 0;

    while (~scanf("%c", &ch) && ch == ',') {
        scanf("%d", a + length);
        length++;
    }

    scanf("%d", &target);

    dp[0] = 0;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j <= target - a[i]; j++) {
            if (dp[j] >= 0) {

                if (dp[j + a[i]] == -1) {
                    dp[j + a[i]] = dp[j] + 1;
                }
                else {
                    dp[j + a[i]] = min(dp[j] + 1, dp[j + a[i]]);
                }
            }
        }
    }

    printf("%d", dp[target]);

    return 0;
}

第二题其实应该算是有序链表合并，读数据还是一如既往的难受。【100%】

#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using namespace std;

int flag = 0;

int a[2][4];
int length[2];

int read_next_int() {

    char ch = 0;
    int res = 0;

    scanf("%c", &ch);

    if (ch == 0) {
        flag++;
        return -1;
    }

    if (ch == '\n') {
        flag++;
        return -1;
    }

    if (ch == ',') {
        return -1;
    }

    if (ch == ' ') {
        return -1;
    }

    if (ch == ';') {
        flag++;
        return -1;
    }

    res += ch - '0';

    int next = read_next_int();

    if (next == -1) {
        return res;
    }

    return res * 10 + next;

}

int main() {

    int x = 0;
    int nextFlag = 0;

    while (flag < 2) {
        x = read_next_int();
        if (x == -1) {
            nextFlag = flag;
            continue;
        }
        if (length[nextFlag] < 4) {
            a[nextFlag][length[nextFlag]] = x;
            length[nextFlag]++;
            nextFlag = flag;
        }
    }


    /*
        这样我们就得到了两个有序数组。
        a[4]
        b[4]
    */

    int idxA = 0;
    int idxB = 0;
    int cnt = 0;

    while (idxA < length[0] && idxB < length[1]) {

        if (a[0][idxA] < a[1][idxB]) {
            if (cnt == 3) {
                printf("%d", a[0][idxA]);
                return 0;
            }
            idxA++;
        }
        else {
            if (cnt == 3) {
                printf("%d", a[1][idxB]);
                return 0;
            }
            idxB++;
        }
        cnt++;
    }

    if (idxA < length[0]) {
        printf("%d", a[0][idxA + 3 - cnt]);
    }
    if (idxB < length[1]) {
        printf("%d", a[1][idxB + 3 - cnt]);
    }

    return 0;
}

第三题我直接暴力搜索了，因为字符串长度均小于1000，所以时间是OK的，空间也OK。【100%】

#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using namespace std;

char s1[1005];
char s2[1005];

int lenA = 0;
int lenB = 0;


int getRes(int a, int b) {

    if (b == lenB) {
        return 0;
    }

    if (a == lenA) {
        return -1;
    }

    if (s1[a] == s2[b]) {
        return getRes(a + 1, b + 1);
    }
    else {
        // 跳过
        int next1 = getRes(a + 1, b);
        // 交换
        int next2 = getRes(a + 1, b + 1);

        if (next1 >= 0 && next2 >= 0) {
            // 如果均有解
            return min(next1, next2 + 1);
        }
        else if (next1 >= 0) {
            return next1;
        }
        else if (next2 >= 0) {
            // 因为交换，所以要+1
            return next2 + 1;
        }
        else {
            return -1;
        }
    }

}

int main() {

    scanf("%s%s", s1, s2);

    lenA = strlen(s1);
    lenB = strlen(s2);

    int res = getRes(0, 0);

    printf("%d", res);

    return 0;
}