牛客春招刷题训练营-2025.3.17题解

n 活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 数字颠倒

输入看作字符串，直接反转输出。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}

中等题 密码截取

回文串的长度可以为奇数或偶数。
对于奇数，枚举最中间的一个字符；对于偶数，枚举最中间的两个字符。
枚举的过程中向两边扩展，扩展的过程中更新最大回文串长度，不是回文串时退出。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int ans = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) { // 奇数长度 以i为中心
        int l = i, r = i;
        while (l >= 0 && r < n && s[l] == s[r]) {
            ans = max(ans, r - l + 1);
            l--;
            r++;
        }
    }
    for (int i = 0; i + 1 < n; i++) { // 偶数长度 以i和i+1为中心
        int l = i, r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r]) {
            ans = max(ans, r - l + 1);
            l--;
            r++;
        }
    }
    cout << ans << '\n';
    return 0;
}

困难题 计算字符串的编辑距离

动态规划问题。
设 为原字符串， 为修改后的字符串。
设 为 中前 个字符变成 中前 个字符的编辑次数。
先讨论特殊情况：，因为可以向 中插入 个字符，，因为可以从 中删除 个字符。
然后可以得到其他情况：当 时：

• 当 时，无需修改，。
• 当 时，可以有三种操作：
  1. 修改 。对应转移方程为 。
  2. 插入 。对应转移方程为 。
  3. 删除 。对应转移方程为 。
  三种操作取最小值。

最终答案为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    s = ' ' + s;
    t = ' ' + t;
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i++)dp[i][0] = i;
    for (int i = 0; i <= m; i++)dp[0][i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
            }
        }
    }
    cout << dp[n][m] << '\n';
    return 0;
}