hmmm~~一个C语言编程题~~

Renee

稍微说明下自己的算法罢~~

thody

先判断能否回文。

将所有字符一边放一半。

然后从正中间选取左右两边字符的最相近的替换。

asddsfaf 成asdfdsaf成asfddsaf成afsddsaf成afsddsfa。

不过怎么看都不象最简的。

看来人工是才最快的。

hyp

话说猪头那算法有交换吗

amp34

当然有交换，只是不符合题意。
题意是“相邻”的两个字符，而他是“相对”的两个字符。

thody

“相对”的两个字符交换步骤为（两字符间隔）*2-1

zhuzeitou

555555发现看错题目了………………
重做去了

amp34

对啊。上次那天然呆给我加的渣WW居然还没扣掉。都过这么久了。效率有问题啊。

amp34

事实上，请看清楚题目，题目的要求是最少的交换次数，并没有要求最快的执行时间。

amp34

光顾着回帖了，面都差点煮糊。

thody

1. test(int *s)
2. {
3.     int len = sizeof(s)-1;
4.     int count = 0;
5.     char c = ' ';
6.     int i=0,j=0;
7.     //先判断能否回文，略
8.     for(i = 0 ;i<len/2;i++)
9.     {
10.         c = s[i];
11.         for(j=len;j=i;j--)
12.         {
13.             if(c==s[j])
14.         {
15.                    //将j位置和len-i的位置交换，略
16.             count = count + abs(len - j - i)*2 -1;
17.         }
18.         if i==j
19.         {          //将j位置和s中间位置字符交换，略
20.                 count = count + (len/2-i)*2 - 1;
21.         }
22.     }
23.     return count;
24. }

复制代码

thody

n久没写过c了，好难写。

amp34

楼上都略完鸟。

以下素偶的算法：

1. 略

复制代码

thody

哈哈，没编辑器，写了也测试不了，所以写个思路。

o(＞_＜)o

好象误入了不得了的地方

amp34

不得了的草莓。

zhuzeitou

55555555于是还是java………………

[codes=java]int PalindromeIt(char[] s){
    int count = 0;
    int l = s.length;
    int odd = 0;
    for (int i = 0; i < l / 2; i++){
        if (s != s[l - 1 - i]){
            for (int j = l - 1 - i , k = 0; j > i && k == 0; j--){
                if (s == s[j]){
                    for (int m = j; m < l - 1 - i; m++){
                        s[m] = (char)(s[m] + s[m + 1]);
                        s[m + 1] = (char)(s[m] - s[m + 1]);
                        s[m] = (char)(s[m] - s[m + 1]);
                        count++;
                    }
                    k++;
                }
                if (j == i + 1 && k == 0){
                    odd++;
                    if (odd > l - l / 2 * 2){
                        return -1;
                    }
                    for (int m = i; m < l / 2; m++){
                        s[m] = (char)(s[m] + s[m + 1]);
                        s[m + 1] = (char)(s[m] - s[m + 1]);
                        s[m] = (char)(s[m] - s[m + 1]);
                        count++;
                    }
                    i--;
                }
            }
        }
    }
    System.out.println(s);
    return count;
}[/codes]

算法就是从数组头开始一直到中间项，判断该项与对称项是否相同，如果不同，那么从对称项开始往前寻找最近的一个相同的项，将其一步一步往后交换直道对称，每交换一次计数器加1
如果找不到，那么将奇数项计数器加1，判断是否仍然可能为回文字符串，如果满足则将此项移到中间，不满足直接返回-1
正常结束返回计数器的值

白银の式神

判斷是否能回文的話，只要滿足最多有一個char的個數是奇數就行了。
從兩邊向中間或者從中間向兩邊都是可行的。
只要順序一致，步數是相等的。

amp34

嗯嗯。因为条件是只能相邻的交换，所以只要路径是最短的，不管从什么方向开始交换，得出来的结果都是一样的。