2 kid 0203 kid_0203 于 2016.03.13 14:10 提问

关于c语言回文串的问题

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

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

6个回答

xianfajushi
xianfajushi   2016.03.13 15:55

为何要交换3次?一次足矣d-m交换
按代码看
if(str[j]==str[i])
{
char c;
c=str[j];alpha[j]=str[j-i-1];str[j-i-1]=c;
num++;
break;
}
这样的位置字符相等为何要进行交换,交换意义何在?

xianfajushi
xianfajushi 回复kid_0203: 其他的且不论,假设str里面存储的是mamad,那么,你能说说你设计那样的交换的目的何在?你能自己说清楚?
接近 2 年之前 回复
kid_0203
kid_0203 必须交换3次,交换一次不是回文串啊 我这个交换是从右边查找和左边相等的字符,交换左边两个字符之后形成对称,我交换的不是str[i]和str[j]
接近 2 年之前 回复
renlong0829
renlong0829   2016.03.14 02:04

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

renlong0829
renlong0829   2016.03.14 04:30
#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");
    }

}

renlong0829
renlong0829   2016.03.14 11:14

纠正一点,应该是
for(i=0; i<26;i++)

xianfajushi
xianfajushi   2016.03.14 19:57

写算法前的分析:判断一个字符串是否可能是回文串,除了可以按定义的从前都和从后都都是一样外,还可以这样理解从头递增尾递减的字符都相等,无关其字符数量。
按照之上理解,则可从头尾比较中执行判断和交换,就用mamad为例,不用编译器就可以写个大概代码:
char 字符串[]={'m','a','m','a','d'},交换('-');
int 头(0),尾(4),标头(0),标尾(0);
while(头<尾)
if(字符串[头]!=字符串[尾])
{
标头=头;标尾=尾;
while(字符串[标头]!=字符串[标尾]&&标头<=标尾)++标头;
if(标头!=标尾)
{
交换=字符串[头];字符串[头]=字符串[标头];字符串[标头]=交换;
++头;--尾;
}
else
{
标头=头;
while(字符串[标头]!=字符串[标尾]&&标头<=标尾)--标尾;
if(标头!=标尾)
{
交换=字符串[尾];字符串[尾]=字符串[标尾];字符串[标尾]=交换;
++头;--尾;
}
else
{不是回文串;break;}
}
}
按照逻辑写个框架大概,接着就是上机调试,直到得到正确的算法为止,按之上写的代码的逻辑希望来说,就mamad这个字符串,确实只需要一次交换即可。当 标尾==2时,d被存储,m被交换到4,d被交换当2;接着外循环1和3相等,结束判断。

xianfajushi
xianfajushi 回复renlong0829: 交换就是指对2个数据进行位置交换,这算一次,难道算3次?给你个截图看就明白了。
一年多之前 回复
renlong0829
renlong0829 这得看怎么理解“交换次数”,如果每“交换两个相邻的字符”就算一次,那无论如何都不可能只用一次交换就成功的。
一年多之前 回复
xianfajushi
xianfajushi   2016.03.15 10:49

图片说明
如果还认为不能一次交换就完成任务的话,那我还不如去对牛弹琴更好,对牛弹琴牛还能挤出好奶,我也能喝到好牛奶,交换为什么只能是相邻的?明明能一次完成的为何要多次才完成?不同思路不同算法,哪个更合题意。

xianfajushi
xianfajushi 图中1,2,3只有一次交换,4才用2次交换就完成了。
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!