c/c++语言开发共享用C++实现：完美的代价-计算机技术网

c/c++语言开发共享用C++实现：完美的代价

2021年5月9日上午5:03 • C/C++开发 • 阅读 0

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数n，表示接下来的字符串的长度(n <= 8000)
　　第二行是一个字符串，长度为n.只包含小写字母

输出格式

　　如果可能，输出最少的交换次数。
　　否则输出impossible

样例输入

5
mamad

样例输出

思路：先判断这个字符串是否可以组成一个回文字符串，然后按照每一个字母出现的次数为偶数还是奇数进行讨论。每一次都是从第一个字母开始往后进行检测，要是遇到了出现次数为1的字母，先不要动它，等到其他的字母都排完了，再直接将其放到字符串的中间即可；如果所有的字母出现次数都为偶数个，那么从字符串的最后开始往前检测，直到遇到和当前字母相同的字母，再进行位置交换。

  1 #include<iostream>   2 using namespace std;   3    4 class huiwen   5 {   6 public:   7     int get_n()   8     {   9         cin>>n;  10         return n;  11     }  12     void get_putin()  13     {  14         cin>>putin;  15     }  16     void exchange()  17     {  18         for(int i=0;i<n;i++)  19         {  20             num[putin[i]-'a']++;  21         }  22         for(int i=0;i<26;i++)  23         {  24             if(num[i]%2!=0)  25             {  26                 t++;  27             }  28         }  29         if(t>=2)  //要是有两个或两个以上的字母出现次数为奇数，那么这个字符串不可能为回文字符串  30         {  31             cout<<"impossible";  32             return;  33         }  34         else if(t==0)    //说明所有字母的出现次数都是偶数  35         {  36             for(int i=0;i<n/2-1;i++)  37             {  38                 flag=-1;  39                 for(int j=n-a-1;j>i;j--)  40                 {  41                     if(putin[i]==putin[j])  42                     {  43                         flag=j;  44                         break;  45                     }  46                 }  47                 char temp=putin[flag];  48                 for(int m=flag;m<n-1-a;m++)  49                 {  50                     putin[m]=putin[m+1];  51                 }  52                 putin[n-1-a]=temp;  53                 time=time+(n-1-a-flag);   //计算移动次数  54                 a++;  55             }  56         }  57         else if(t==1)  58         {  59             for(int i=0;i<=n/2;i++)  60             {  61                 flag=-1;  62                 for(int j=n-a-1;j>i;j--)  63                 {  64                     if(putin[i]==putin[j])  65                     {  66                         flag=j;  67                         break;  68                     }  69                 }  70                 if(flag==-1)   //遇到出现次数为1次的字母了  71                 {  72                     time=time+(n/2-i);  73                 }  74                 else  75                 {  76                     char temp=putin[flag];  77                     for (int m = flag; m < n - 1 - a; m++)  78                     {  79                         putin[m] = putin[m + 1];  80                     }  81                     putin[n - 1 - a] = temp;  82                     time = time + (n - 1 - a - flag);   //计算移动次数  83                     a++;  84                 }  85             }  86         }  87         cout<<time;  88         return;  89     }  90 private:  91     int n;    //输入字符串所含字母个数  92     char putin[8001];   //输入字符串  93     int num[26]={0};   //一共有26个字母，判断每一个字母的出现次数  94     int t=0;   //整个字符串里面有多少个出现次数为奇数的字母  95     int a=0;   //表示已经处理到第a个字母  96     int flag;  //用flag来记录后一半字符串匹配的最近的字母下标  97     int time=0;  //用来计算移动字母的次数  98 };  99  100 int main(void) 101 { 102     huiwen string; 103     string.get_n(); 104     string.get_putin(); 105     string.exchange(); 106     return 0; 107 }

注意：题目中的交换的意思和一般的交换意思不一样，这里只能挨个地进行交换，而一般所说的交换是直接将两个字符进行对调，所以计算交换次数的时候不能只算一次。

本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址：https://www.ctvol.com/c-cdevelopment/599806.html

c/c++语言开发共享用C++实现：完美的代价

精彩推荐