用C++实现:完美的代价
2020-04-15 16:00:38来源:博客园 阅读 ()
用C++实现:完美的代价
问题描述 回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!) 输入格式 第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串,长度为N.只包含小写字母 输出格式 如果可能,输出最少的交换次数。
否则输出Impossible 样例输入 5
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 }
注意:题目中的交换的意思和一般的交换意思不一样,这里只能挨个地进行交换,而一般所说的交换是直接将两个字符进行对调,所以计算交换次数的时候不能只算一次。
原文链接:https://www.cnblogs.com/guanrongda-KaguraSakura/p/12703948.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash