小红的回文串构造

原创于 2024-01-29 15:34:16 发布 · 粉丝可见 · 749 阅读 · 4 · 9 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135912970

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例1：

`undefined<br/>abba<br/>`

baab

样例2：

`undefined<br/>aba<br/>`

-1

思路：

由题意，题目保证给出的字符串是回文串的，所以我们只需要获取两个不同的字符的对应对称的两个坐标进行交换即可构造完毕。

这里有一个关键点，就是我们如何知道当前的下标 i 的堆成下标是多少？

关于 i 对称的下标，肯定有一个规律关系，其中对称又有两种方式。

其中奇数串对称：

1 2	`奇数串对称: dcabacd 偶数串对称：dcabbacd 1234567 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;    // 当前下标 i
    int j;    // 对称下标 j
    inline 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;
            // 存储对称下标 j
            a.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;
                // 存储对称下标 j
                b.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;
}