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

简单题：数字颠倒

读入一个字符串，倒序输出就行了。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for(int i=n-1; i>=0; i--)
        cout << s[i];
    return 0;
}

中等题：密码截取

这道题本质就是求一个字符串的最长回文字串。

首先注意到题目范围是2500，那么暴力的O(N^3)做法（枚举所有字串然后判断是不是回文）就肯定不行了。

所以我们要找到一个O(N^2)以内的做法。

比较容易想到的一个做法是枚举回文中心，然后向外扩散到最长的回文子串，不断更新最大长度的值就好。

然后关于回文中心的选取其实一共有两种情况，一种情况中心是字母，对应奇数长度的字串；另一种中心是空，对应偶数长度的字串。我下面的代码就用一个循环，通过模2的奇偶性把两种位置一起枚举了。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int res = 0;
    for(int i=1; i<(n-1)*2; i++) {
        if(i % 2 == 0) {
            int j = i / 2;
            int tot = 1;
            for(int l=j-1, r=j+1; l>=0 && r < n; l--, r++) {
                if(s[l] == s[r]) tot += 2;
                else break;
            }
            res = max(res, tot);
        } else {
            int j = i / 2;
            int tot = 0;
            for(int l=j, r=j+1; l>=0 && r < n; l--, r++) {
                if(s[l] == s[r]) tot += 2;
                else break;
            }
            res = max(res, tot);
        }
    }
    cout << res << endl;
    return 0;
}

当然，这道题有个复杂度更低的算法，也就是马拉车算法。在算法竞赛里一般都会用这种写法，因为复杂度是 O(N)。

想要了解的小伙伴们可以自行学习一下，这里就不赘述了。下面是笔者的ACM板子，大家可以参考一下。

#include <iostream>
#include <vector>
using namespace std;
string Get_new(string &str) {
    string temp = "#";
    for (int i = 0; str[i]; ++i) {
        (temp += str[i]) += "#";
    }
    return temp;
}
vector<int> manacher(string &str) {
    vector<int> r(str.size()+5);
    int c = 0;
    for (int i = 1; str[i]; ++i) {
        if (c + r[c] > i)  r[i] = min(r[2 * c - i], c + r[c] - i);
        while (i - r[i] >= 0 && str[i - r[i]] == str[i + r[i]])  ++r[i];
        --r[i];
        if (i + r[i] > c + r[c])  c = i;
    }
    return r;
}
int main() {
    string s;
    cin >> s;
    s = Get_new(s);
    auto d = manacher(s);
    int res = 0;
    // d数组的最大值就是最长回文字串
    for(int x: d)
        res = max(res, x);
    cout << res << endl;
    return 0;
}

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

DP经典问题，编辑距离。

解释一下DP数组的含义吧，dp[i][j]就是代表a[0...i-1] (a的前i个字母组成的字符串) 和 b[0...j-1] (b的前j个字母组成的字符串) 之间的编辑距离。那么dp[n][m]其实就是我们要求的答案。

怎么转移呢？

不难想到，假如说 a[i-1] == b[j-1]（ps：a[i-1]是a串的第i位），dp[i][j]直接等于dp[i-1][j-1]就行了，因为这一对字母加上之后不需要耗费编辑次数。

但如果不相等，就对应了五种编辑的可能，把a[i-1]删除、把b[j-1]删除、把a[j-1]和b[j-1]改成一样的、a[i-2]之后插入b[j-1]或在b[i-2]之后插入a[i-1]。

再仔细想一下，其实插入和删除本质上是一样的。那我们不如就只做删除操作。

两种删除的情况分别对应dp[i-1][j]+1和dp[i][j-1]+1，而更改操作则对应dp[i-1][j-1]+1，把这三种情况的值取一个最小值就行了。

dp一遍后，输出dp[n][m]。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size();
    int m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1));
    for(int i=0; i<=n; i++)
        dp[i][0] = i;
    for(int j=0; j<=m; j++)
        dp[0][j] = j;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
            else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}