前言

最近一直搞面试，很多写好的代码都懒得去发博客，现在补上，但是注释可能比较少，大家如果有问题请联系我

试题 基础练习 完美的代价

资源限制
时间限制：1.0s 内存限制：512.0MB

问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible

样例输入
5
mamad

样例输出
3

本题代码（JAVA）

import java.util.Scanner;

public class ThePriceOfPerfection3 {
    private static int count = 0;
    private static boolean haveMiddle = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String str = sc.next();
        char[] charArr = str.toCharArray();//将输入字符串转换为char数组
        if (palindrome(charArr, 0, N - 1)) {
            System.out.println(count);
        } else {
            System.out.println("Impossible");
        }
    }

    private static boolean palindrome(char[] charArr, int a, int b) {
        if (b <= a) {
            return true;
        }
        // 从最后的位置开始遍历字符串
        for (int i = b; i > a; i--) {
            if (charArr[a] == charArr[i]) {
                exchangeTo(charArr, i, b);
                count += b - i;
                return palindrome(charArr, a + 1, b - 1);
            }
        }
        // 如果没有出现过中间字符
        if (!haveMiddle) {
            haveMiddle = true;
            count += charArr.length / 2 - a;
            return palindrome(charArr, a + 1, b);
        }
        return false;
    }

    private static void exchangeTo(char[] charArr, int a, int b) {
        //字符交换方法1
        for (int i = a; i < b; i++) {
            char tmp = charArr[i];
            charArr[i] = charArr[i + 1];
            charArr[i + 1] = tmp;
        }
        /*交换字母方法2
        char temp = charArr[a];
        for (int i = a; i < b; i++) {
            charArr[i] = charArr[i + 1];
        }
        // if (b - a >= 0) System.arraycopy(charArr, a + 1, charArr, a, b - a);
        charArr[b] = temp;*/
    }
}

本题代码（Python）

def move(l, a, b):
    buf = l[a]
    if b > a:
        l[a:b] = l[a + 1:b + 1]
    else:
        l[b + 1:a + 1] = l[b:a]
    l[b] = buf


n = eval(input())
s = input()
cl = []
side = []
for c in s:
    have = False
    for i in range(len(cl)):
        if cl[i] == c:
            side.append(c)
            del cl[i]
            have = True
            break
    if not have:
        cl.append(c)
if len(cl) > 1:
    print("Impossible")
else:
    s = list(s)
    num = 0
    mid = False
    for i in range(int(n / 2)):
        if mid:
            move(s, n - 1 - i, n - 2 - i)
            num += 1
        if s[i] != s[n - 1 - i]:
            omid = True
            for j in range(i + 1, n - i - 1):
                if s[j] == s[n - 1 - i]:
                    omid = False
                    move(s, j, i)
                    num += j - i
                    break
            if omid and not mid:
                mid = True
                move(s, n - 1 - i, n - 2 - i)
                num += 1
                for j in range(i + 1, n - i - 1):
                    if s[j] == s[n - 1 - i]:
                        move(s, j, i)
                        num += j - i
                        break
    print(num)