帆软笔试（后台开发工程师 2023/8/10）

编程题目两道（动态规划+数据库查询）

1、假设可以用一个字符串表示某植物的DNA，对该植物进行不同剂量辐射可以修改他的DNA值，从而培育出新的品种。

#其中:

插入一个DNA字符的时间消耗为x天

删除一个DNA字符的时间消耗为y天

替换一个DNA字符的时间消耗为z天

那么请设计一个函数，计算该植物品种A培育成品种B最快需要多少天,输入参数依次为：

字符串A，字符串B，正整数X，正整数y，正整数z

注意：用例中替换的代价有可能会高于插入删除之和，也可能小于插入删除之和。

样例1：

输入数据: virusA =“finereport”,virusB =“fanruan666”

x=2,y=4,z=5

期望输出: 36

ac代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int min(int a, int b, int c) {
    return min(a, min(b, c));
}

int solution(string virusA, string virusB, int x, int y, int z) {
    int m = virusA.size();
    int n = virusB.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0)
                dp[i][j] = j * x;
            else if (j == 0)
                dp[i][j] = i * y;
            else if (virusA[i - 1] == virusB[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min(dp[i - 1][j - 1] + z,
                               min(dp[i][j - 1] + x, dp[i - 1][j] + y));
        }
    }

    return dp[m][n];
}

int main() {
    string virusA = "finereport";
    string virusB = "fanruan666";
    int x = 2;
    int y = 4;
    int z = 5;

    int result = solution(virusA, virusB, x, y, z);
    cout << "Minimum days needed: " << result << endl;

    return 0;
}

2、编写一条 SQL，查找 test 表中重复 2 次及以上的车牌

id car

1 苏412345

2 苏A12346

3 苏412346

4 苏A12347

5 苏A12347

输出：

car

苏A12346

苏A12347

SELECT car
FROM test
GROUP BY car
HAVING COUNT(*) >= 2;