有哪些网站可以免费做外销,太原网站公司,网站建设竞争大吗,网站建设公司上海本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网
题目#xff1a;
样例1#xff1a; 输入 abba 输出 baab
样例2#xff1a; 输入 aba 输出 -1 思路#xff1a; 由题意#xff0c;题目保证给出的字符串是回文串的#xff0c;所以我们只需要获取两个不同的…本题链接登录—专业IT笔试面试备考平台_牛客网
题目
样例1
输入 abba 输出 baab
样例2
输入 aba 输出 -1 思路 由题意题目保证给出的字符串是回文串的所以我们只需要获取两个不同的字符的对应对称的两个坐标进行交换即可构造完毕。 这里有一个关键点就是我们如何知道当前的下标 i 的堆成下标是多少 关于 i 对称的下标肯定有一个规律关系其中对称又有两种方式。 其中奇数串对称
奇数串对称: dcabacd 偶数串对称dcabbacd1234567 12345678 观察对应的下标 i 就可以找出一定的规律为
当前的下标 i 的对称下标 j 一定为j (s.length() % 2 ? i (s.length() / 2 - i) * 2: i (s.length() / 2 - i) * 2 - 1);奇数串的时候 j i (s.length() / 2 - i) * 2偶数串的时候 j i (s.length() / 2 - i) * 2 - 1 所以结合以上规律即可构成出答案了。 这里也有个小细节就是我们只需要遍历回文串的一半即可。 否则会将奇数串中的对称点也作为第二个不同的字符。 代码详解如下
#include iostream
#include cstring
using namespace std;// 用于存储不同的字符
struct Char
{char now;int i; // 当前下标 iint j; // 对称下标 jinline Char():now(-),i(-1),j(-1){} // 默认构造函数
};
signed main()
{string s;getline(cin,s);int sz s.size(); // 获取字符串长度if(sz 3){cout -1 endl; // 特判如果 小于等 3 那么一定是无解return 0;}Char a,b; // 定义结构体用于存储两个不同的字符for(int i 0;i sz / 2;i) // 遍历对应回文串的一半即可{// 如果 a 还没存储好我们现在给它存储if(a.now -){a.now s[i];a.i i;// 存储对称下标 ja.j (sz % 2 ? i (sz / 2 - i) * 2 : i (sz / 2 - i) * 2 - 1); }else{if(b.now - and s[i] ! a.now) // 出现不同 a 的字符{b.now s[i];b.i i;// 存储对称下标 jb.j (sz % 2 ? i (sz / 2 - i) * 2 : i (sz / 2 - i) * 2 - 1); break; // 两个都存储完了推出循环}}}if(a.now - || b.now -){cout -1 endl; // 如果没有第二个不同的字符那么肯定无解return 0;}// 开始交换两个字符s[a.i] s[a.j] b.now;s[b.i] s[b.j] a.now;// 输出答案即为使其中任意一个解cout s endl;return 0;
}
最后提交
