蓝桥杯VIP试题 之 基础练习 完美的代价 - JAVA

蓝桥杯VIP试题 之 基础练习 完美的代价 - JAVA

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

交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)

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

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

样例输入
5
mamad

样例输出
3

import java.util.Scanner;

public class Main{	
	public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String str = sc.next(); //将输入字符串转换为char数组 char[] charArr = str.toCharArray(); //求出现的次数为奇数的字母个数  int[] num = new int[26]; //记录每个字母出现的个数 for(int i = 0; i < n; i++) { num[charArr[i] - 'a']++; } //出现次数为奇数的字母个数 int count = 0; for(int i = 0; i < 26; i++) { if(num[i] != 0) { if(num[i] % 2 != 0) { count++; } } } //若个数大于等于2个,则直接返回Impossible if(count >= 2) { System.out.println("Impossible"); }else{ System.out.println(getCount(str)); }
	} static int getCount(String str) {
		//1,2长度是无需交换 if(str.length()==1 || str.length()==2) return 0; //取字符串第一个字符最后一次出现的位置 int temp = str.lastIndexOf(str.charAt(0)); if(temp==0){ return str.length()/2 + getCount(str.substring(1,str.length())); } else { //0号位字符和已找到temp位置的字符都移除,然后进行递归  //String remoStr =  str.substring(1, temp) + str.substring(temp + 1,str.length()); //这么写不知道那组数据不对 StringBuilder strBuilder = new StringBuilder(str); strBuilder.deleteCharAt(temp); strBuilder.deleteCharAt(0); //System.out.println(temp +".."+ remoStr); return str.length()-temp-1 + getCount(strBuilder.toString()); } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/104642458