帆软笔试（后台开发工程师 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;
查看4道真题和解析