问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
输入格式
第一行是一个整数n,表示接下来的字符串的长度(n <= 8000)
第二行是一个字符串,长度为n.只包含小写字母
第二行是一个字符串,长度为n.只包含小写字母
输出格式
如果可能,输出最少的交换次数。
否则输出impossible
否则输出impossible
样例输入
5
mamad
mamad
样例输出
3
思路:先判断这个字符串是否可以组成一个回文字符串,然后按照每一个字母出现的次数为偶数还是奇数进行讨论。每一次都是从第一个字母开始往后进行检测,要是遇到了出现次数为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