蓝桥杯: 完美的代价

问题描述 　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

　　交换的定义是：交换两个相邻的字符

　　例如mamad

　　第一次交换 ad : mamda

　　第二次交换 md : madma

　　第三次交换 ma : madam (回文！完美！) 输入格式 　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)

　　第二行是一个字符串，长度为N.只包含小写字母 输出格式 　　如果可能，输出最少的交换次数。

　　否则输出Impossible 样例输入 5

mamad 样例输出 3

分析:

贪心思想，从左向右遍历，对于当前字符，从最右边向左遍历，找到与当前字符相同的，把它移动到正确位置，累加步数。

如果字符串长度为偶数，只要有一个无法配对的字符，就不能变成回文串，若为奇数，只要出现两个无法配对的字符，也不能。

import java.util.Scanner;

public class tanxin {
    public static int sum = 0;
    public static void exchange(char[] arr, int x, int y) {	//把arr字符数组中x下标和y下标对应的值交换位置
        char item;
        item = arr[x];
        arr[x] = arr[y];
        arr[y] = item;

        sum ++;		//移动次数加一
    }
    public static void main(String[] args) {
        Scanner readerIn = new Scanner(System.in);
        int n = readerIn.nextInt();
        String str = readerIn.next();
        char[] arr = str.toCharArray();
        int flag = 0;	//当字符串长度为奇数时非成对字符的个数
        boolean isHuiwen = true;	//标示此字符串是否为回文
        int i, j, l = arr.length;

        for(i = 0; i < arr.length/2; i ++) {
            for(j = l - 1; j >= i; j -- ) {	//从最右边开始查找,看有无与当前字符相同的
                if(0 == arr.length % 2 && i == arr.length - 1 && j == arr.length) {
		    //如果当前字符串长度为偶数,且中间两个字符不相同,则该字符不是回文字符
                    if(arr[i] != arr[j]) {
                        isHuiwen = false;
                        break;
                    }
                }
                if(i == j) {	//没有找到与当前字符相同的字符
                    if(0 == arr.length % 2) {	//如果字符长度为偶数则不是回文字符串
                        isHuiwen = false;
                        break;
                    } else {	//如果当前字符长度为奇数,且未匹配的字符超过一个,则也不是回文字符
                        flag ++;
                        if(flag <= 1) {	//有一个字符未匹配,则把此字符移动到中间
                            for(int m = 0; m < arr.length/2 - 1; m ++) {
                                exchange(arr, m, m + 1);
                            }
                            i = 0;	//重新开始遍历
		            break;
                        }
                        if(flag == 2) {		//如果有两个字符为匹配,则该字符不是回文字符
                            isHuiwen = false;
                            break;
                        }
                    }
                }
                if(arr[i] == arr[j]) {
                    for(int k = j; k <= l - 1 - 1; k ++){
                        exchange(arr, k, k + 1);
                        //System.out.println(arr);
                    }
                    l --;
                    break;
                }
            }
        }
        if(!isHuiwen)
            System.out.println("Impossible");
        else
            System.out.printf("%d\n", sum);
    }
}