kid_0203
kid_0203
采纳率85.1%
2016-03-13 06:10 阅读 3.3k

关于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 智者知已应修善业 2016-03-13 07: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;
    }
    这样的位置字符相等为何要进行交换,交换意义何在?

    点赞 评论 复制链接分享
  • renlong0829 renlong0829 2016-03-13 18: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-13 20: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 03:14

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

    点赞 评论 复制链接分享
  • xianfajushi 智者知已应修善业 2016-03-14 11: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 智者知已应修善业 2016-03-15 02:49

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

    点赞 评论 复制链接分享

相关推荐