关于c语言回文串的问题

Question

问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如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;
} 

我写的代码为何不对呀。。。。蓝桥杯的题目

Answer 1

一点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)

1. 逻辑条件有误，应该是不等才交换吧：if(str[j]==str[i])

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这样的-_-#