哪家公司做企业网站,网站添加手机站,网站建设如何交税,免费公网网站建设大厂笔试真题网址#xff1a;https://codefun2000.com/
塔子哥刷题网站博客#xff1a;https://blog.codefun2000.com/
最多修改两个字符#xff0c;生成字典序最小的回文串
提交网址#xff1a;https://codefun2000.com/p/P1089 由于字符串经过修改一定为回文串#x…大厂笔试真题网址https://codefun2000.com/
塔子哥刷题网站博客https://blog.codefun2000.com/
最多修改两个字符生成字典序最小的回文串
提交网址https://codefun2000.com/p/P1089 由于字符串经过修改一定为回文串且最多修改两次所以原字符串位置i与对称位置n-i-1不一样的个数最多为2。所以统计一下需要改的位置个数记为cnt
cnt0即原字符串就是回文串找到第一个不为a的位置i将i与对称位置n-i-1都改为a
aca --- aaa
acca --- aaaa
acbca --- aabaa cnt1只有一个位置需要修改此时分两种情况 如果 i与对称位置n-i-1都不是a将这俩位置都改为a即可如果 i与对称位置n-i-1只有一个为a将另一个不是a的改为a。此时只改了一个字母还可以改一个。当字符串长度为奇数时将中间字符改为a
abcdba --- abaaba
abcea --- aacaa
cbcac --- caaac cnt2两个对称位置需要修改 i与对称位置n-i-1谁小就改为谁
abcde --- abcbaint main() {string s;cin s;int n s.size();vectorint idxs;for (int i 0; i n / 2; i) {if (s[i] ! s[n - 1 - i]) {idxs.push_back(i);}}int cnt idxs.size();if (cnt 0) {// 本身就是回文串需要找到第一个不是a的地方修改for (int i 0; i n / 2; i) {if (s[i] ! a) {s[i] a;s[n - 1 - i] a;break;}}}else if (cnt 1) {// 只有一个需要修改的地方if (s[idxs[0]] ! a s[n - 1 - idxs[0]] ! a) {// 如果对称位置都不是a则两个都改为as[idxs[0]] a;s[n - 1 - idxs[0]] a;}else {// 如果只有一个为a则修改不是a的那个// 如果当前串为奇数还要修改中间位置的为as[idxs[0]] a;s[n - 1 - idxs[0]] a;if (n 1) {s[n / 2] a;}}}else {// 有两个需要修改的地方当前位置idxs[i]和对称位置n - 1 - idxs[i]谁小就改为谁for (int i 0; i cnt; i) {char c min(s[idxs[i]], s[n - 1 - idxs[i]]);s[idxs[i]] c;s[n - 1 - idxs[i]] c;}}cout s endl;return 0;
}
