感觉贪心算法就是分析移动两个数后到底是远离了排位还是靠近了排位~这题还是要想想看才行~

[此贴子已经被作者于2017-3-23 12:57编辑过]

#include <stdio.h>
#include <string.h>
#include <assert.h>


/**

 *\brief 交换字符串中 字符的配置【可优化】

 *

 *    将 位置1 移动 位置2

 *\param[in,out] 字符串

 *\param[in] 位置1 字符串下标值

 *\param[in] 位置2 字符串下标值

 *\retval 交换的步数

 */
unsigned int exchange_chars(char *string, unsigned int pos1, unsigned int pos2)
{
    char tmp;
    unsigned int cnt = 0, i = 0;
    
    if (pos1 > pos2){
    
        for (i = pos1; i > pos2; --i){
        
            ++cnt;
            
            tmp = string[i];
            string[i] = string[i - 1];
            string[i - 1] = tmp;
        }
    }else{
    
        for (i = pos1; i < pos2; ++i){
        
            ++cnt;
            
            tmp = string[i];
            string[i] = string[i + 1];
            string[i + 1] = tmp;
        }    
    }
    
    return cnt;
}

int main(void)
{
    unsigned int i = 0, j = 0, cnt = 0;
    unsigned int len = 0;
    char string[8001];
    
    // 
    scanf("%u", &len);
    scanf("%s", string);
    
    for (i = 0; i < len/2; ++i){
    
        // 头部开始， 倒序搜索尾部
        for (j = len - i - 1; j > i; --j){
        
            if (string[i] == string[j]){
            
                // 交换计算 步数
                cnt += exchange_chars(string, j, len - i - 1);
                break;
            }
        }
        
        if (j > i){
            
            continue;        
        }
        
        // 尾部开始， 顺序搜索头部
        for (j = i; j < len - i - 1; ++j){
        
            if (string[len - i - 1] == string[j]){
            
                // 交换计算  步数
                cnt += exchange_chars(string, j, i);
                break;
            }
        }
        
        if (j >= len - i - 1){
        
            printf("Impossible[%s]\n", string);
            return 1;
        }
    }
    
    printf("string:[%s] cnt:%u\n", string, cnt);
    
    return 0;
}

[此贴子已经被作者于2017-3-23 20:53编辑过]

有bug

题目挖了个坑~还是以题目提供的样例来说~先把m连续移动两次到最后一位~然后再ad交换同样也是3次~试试按先排两边再排中间~这样两边的元素排好了便不会再发生移动了~这~大概就是所谓的贪心算法~

如果是字符串“daaaabbbbcccc”,还能先把d移到中间吗？其实真的还是要先对比“aabbccdccbbaa”来获取最少移动步数的。

./test
12
aaaabbbbcccc
string:[aabbccccbbaa] cnt:24


./test
13
daaaabbbbcccc
string:[ccbbaadaabbcc] cnt:30

策略 并没有问题

这样可否：
#include <stdio.h>
main()
{
    int i, n;
    char s[8000];
    printf("输入字符个数：");
    scanf("%d", &n);
    printf("输入字符串：");
    for (i=0; i<n; i++)
        scanf(" %c", &s[i]);
    s[i] = 0;   
    int count=0, odd=0;
    char ch[128]= {0};
    char *p, *p1, *p2;
    for (p=s; *p; p++)
    {
        if (*p < 128)
            ch[*p]++;
        else
            return;   //不考虑扩展码部分
    }
    for (i=0; i<128; i++)
    {
        if (ch[i]>0 && ch[i]%2!=0)
        {
            odd++;
            if ((n%2!=0 && odd>1) || (n%2==0 && odd>0))
            {
                printf("“%s”字串不能组成回文串\n", s);
                return;
            }
        }
    }
    p1 = s;     
    p2 = s+n-1;
    while (p1<p2)
    {
        //printf("%s\n", s);
        for (; p1<p2 && *p1==*p2; p1++,p2--) NULL;
        if (p1>=p2)   //是回文串结束
            break;
        for (p=p2-1; p>p1 && *p!=*p1; p--) NULL;
        *p ^= *(p+1); //交换的定义是：交换两个相邻的字符
        *(p+1) ^= *p;
        *p ^= *(p+1);
        count++;
        if (p>p1)
        {
            for (++p; p<p2; p++)   //向后滚动交换相邻的字符直到尾指针
            {
                *p ^= *(p+1);
                *(p+1) ^= *p;
                *p ^= *(p+1);
                count++;
            }
            p1++;
            p2--;
        }
    }
    printf("回文串：%s 交换次数：%d\n", s, count);
}

那就把d忽略~最后移动时d自然会被其它字符推动最后自然压在中间了~

楼上的算法都明白了，谢谢大神们！