问题描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
#include<stdio.h>
int check(char str[],int n)
{
int i,j;
int flag=1;
for(i=0,j=n-1;i<=j;i++,j--)
{
if(str[i]!=str[j]) flag=0;
}
return flag;
}
int main()
{
int n,alpha[26]={0},num=0,i,j,d=0,s=0;
char str[8000]={0};
scanf("%d",&n);
scanf("%s",str);
for(i=0;i<n;i++)
alpha[str[i]-'a']++;
for(i=0;i<26;i++)
if(alpha[i]%2==0)s++;
else if(alpha[i]%2!=0) d++;
if(d==(n%2!=0?1:0)&&s==(n%2!=0?25:26))
{
for(i=0;i<n;i++)
{
if(check(str,n)) break;
for(j=n-1;j>=0;j--)
if(str[j]==str[i])
{
char c;
c=str[j];alpha[j]=str[j-i-1];str[j-i-1]=c;
num++;
break;
}
}
printf("%d",num);
}
else printf("Impossible");
return 0;
}
我写的代码为何不对呀。。。。蓝桥杯的题目
一点comments
1. s这个变量完全没有用处，d这个变量只需判断是否<=1就行了
if(alpha[i]%2==0)s++;
else if(alpha[i]%2!=0) d++;
if(d==(n%2!=0?1:0)&&s==(n%2!=0?25:26))
简化为
if(alpha[i]%2!=0) d++;
if(d==(n%2!=0?1:0)
3.呵呵，你的算法看上去只是为了mamad这个测试字符串准备的。如果是mmaad怎么办？
建议如下
1. 扫瞄字符串，得到d的值，同时最好标注alpha[i]为奇数的那个i，应该只有一个，或者没有。
2. d>1直接返回impossible；d=1, n为偶数时impossible；d=0, n为奇数时impossible
3. d＝1，n为奇数时，alpha[i]就应该是中心的那个值，就是说必须有str[1+n/2] = alpha[i]。先想办法做到这一点，然后从中间向两边扫瞄交换
4. d＝0，n为偶数时，中间开花比较快
以mamad为例
n＝5，d＝1，'d'字符是要放在中间的，就是--d--这个模式
mamad ->mamda ->madma（交换2次）
然后以'd'为中心（i＝2），左右开弓str[i-1]!=str[i+1]，str[i-2]<->str[i-1]或者str[i+2]<->str[i+1]都可以，分别可以得到amdma或者madam（交换1次）
一共交换3次
这个算法不适用于有连续相同字符的字符串，比如mmaad，mmaammd这样的-_-#
#include <stdio.h>
#include <string.h>
#define MAX_INPUT_LEN 8000
int main()
{
int alpha[26]={0}; // statistical bucket
int nLen = 0; // length of the input string
int nScanLen = 0;
int swap_num = 0; // count of swap
int odd_char = 0; // number of chars with odd appearance
int even_char = 0; // number of chars with even appearance
char str[MAX_INPUT_LEN]={0};
char* pcur = str;
int i,j,k;
scanf("%d", &nLen);
scanf("%s", str);
nScanLen = strlen(str);
if (nScanLen != nLen) return 0;
if (nLen == 0) return 0;
i=0;
do{
alpha[str[i++] -'a']++;
}while(str[i]!=0);
printf("\n");
for(i=0; i<=26;i++)
{
if(alpha[i]!=0)printf("DBG: [%c] = %d\n",i+'a', alpha[i]);
odd_char += alpha[i]%2;
even_char += alpha[i] && !(alpha[i]%2);
}
printf("DBG: odd_char = %d, even_char = %d\n",odd_char, even_char);
if( odd_char == (nLen%2 ? 1 : 0))
{
printf("DBG: swap[%4d], str = %s\n", swap_num, str);
i = 0;
j = nLen-1-i;
while(i<=j)
{
printf("DBG: i=%d, j=%d\n",i,j);
k = j;
while(k>i)
{
if (str[k]!=str[i]) k--;
else break;
}
while(k<j)
{
str[k] ^= str[k+1];
str[k+1] ^= str[k];
str[k] ^= str[k+1];
k++;
swap_num++;
printf("DBG: swap[%4d], str = %s\n", swap_num, str);
}
i++;
j = nLen-1-i;
}
printf("\nswap = %d\n",swap_num);
}
else
{
printf("\nImpossible\n");
}
}
纠正一点，应该是
for(i=0; i<26;i++)