問題 1467: [藍橋杯][基礎(chǔ)練習(xí)VIP]完美的代價

題目描述

回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。小龍龍認為回文串才是完美的?，F(xiàn)在給你一個串，它不一定是回文的，請你計算最少的交換次數(shù)使得該串變成一個完美的回文串。

交換的定義是：交換兩個相鄰的字符

例如mamad

第一次交換 ad : mamda

第二次交換 md : madma

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

輸入

第一行是一個整數(shù)N，表示接下來的字符串的長度(N < = 8000)

第二行是一個字符串，長度為N.只包含小寫字母

輸出

如果可能，輸出最少的交換次數(shù)。

否則輸出Impossible

樣例輸入

5 

mamad 

樣例輸出

3

【分析】對于字符串第一個字符，從字符串的最后一個字符開始匹配，如果找到第一個匹配的位置，將它換到倒數(shù)第二的位置，并記錄這一次轉(zhuǎn)換所需的次數(shù)；如果沒有找到匹配的位置，這個字符可能就會是最中間的那個字符，用一個布爾變量記錄是否需要將這個可能是中間的字符是否存在。題目的關(guān)鍵就是這個可能是中間的字符需不需要換到中間位置的這種情況，如果將這個字符換到中間，那么以后的字符每次變換都會改變這個中間字符的位置。這個中間字符的左邊是已經(jīng)變換好的，只需要將中間字符的右邊作變換就可以了，所以可以將中間字符在最后做變換（下面的代碼沒有在最后實際作變換，只是統(tǒng)計了它變換需要的次數(shù)），最后將右邊的字符作回文處理就可以了，如果處理的過程中再次出現(xiàn)可能是中間的字符，那么這種情況就是不可能的了。
————————————————
版權(quán)聲明：本文為CSDN博主「柳婼」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：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");
        }
    }

    //交換次數(shù)
    private static int cnt = 0;
    private static boolean haveMiddle = false;

    /**
     * @param arr 數(shù)組
     * @param i   0
     * @param i1  最后索引
     * @param oe  true為偶數(shù) false 為基數(shù)
     *            1. 先判斷奇偶，奇數(shù)有中間字母，偶數(shù)沒有。
     *            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--) {
            //從右往左遍歷，如果有一樣的則調(diào)換，如果沒有則判斷是否可能為中間字母。
            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;
    }
}