问题 1467: [蓝桥杯][基础练习VIP]完美的代价

题目描述

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

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

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam (回文！完美！)

输入

第一行是一个整数N，表示接下来的字符串的长度(N < = 8000)

第二行是一个字符串，长度为N.只包含小写字母

输出

如果可能，输出最少的交换次数。

否则输出Impossible

样例输入

5 

mamad 

样例输出

3

【分析】对于字符串第一个字符，从字符串的最后一个字符开始匹配，如果找到第一个匹配的位置，将它换到倒数第二的位置，并记录这一次转换所需的次数；如果没有找到匹配的位置，这个字符可能就会是最中间的那个字符，用一个布尔变量记录是否需要将这个可能是中间的字符是否存在。题目的关键就是这个可能是中间的字符需不需要换到中间位置的这种情况，如果将这个字符换到中间，那么以后的字符每次变换都会改变这个中间字符的位置。这个中间字符的左边是已经变换好的，只需要将中间字符的右边作变换就可以了，所以可以将中间字符在最后做变换（下面的代码没有在最后实际作变换，只是统计了它变换需要的次数），最后将右边的字符作回文处理就可以了，如果处理的过程中再次出现可能是中间的字符，那么这种情况就是不可能的了。
————————————————
版权声明：本文为CSDN博主「柳婼」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liuchuo/article/details/56677012

import java.util.Scanner;
public class 完美的代价 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str = sc.next();
        char arr[] = str.toCharArray();
        sc.close();
        //回文
        if (palindrome(arr, 0, n - 1)) {
            System.out.println(cnt);
        } else {
            System.out.println("Impossible");
        }
    }

    //交换次数
    private static int cnt = 0;
    private static boolean haveMiddle = false;

    /**
     * @param arr 数组
     * @param i   0
     * @param i1  最后索引
     * @param oe  true为偶数 false 为基数
     *            1. 先判断奇偶，奇数有中间字母，偶数没有。
     *            2. odd-even 奇偶
     * @return false不是回文
     */
    private static boolean palindrome(char[] arr, int a, int b) {
        if (b <= a)
            return true;
        for (int i = b; i > a; i--) {
            //从右往左遍历，如果有一样的则调换，如果没有则判断是否可能为中间字母。
            if (arr[a] == arr[i]) {
                exchange(arr, i, b);
                cnt += exchangeTimes(i, b);
                return palindrome(arr, a + 1, b - 1);
            }
        }
        // 遍历了一遍，没有找到一样的
        if (!haveMiddle) {
            haveMiddle = true;
            cnt += exchangeTimes(a, arr.length / 2);
            return palindrome(arr, a + 1, b);
        }
        return false;
    }

    private static int exchangeTimes(int a, int b) {
        return b - a;
    }

    //一个字符顺序交换
    private static void exchange(char[] arr, int a, int b) {
        char temp = arr[a];
        for (int i = a; i < b; i++) {
            arr[i] = arr[i + 1];
        }
        arr[b] = temp;
    }
}