完美的代价

来源:互联网 时间:1970-01-01


问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
输入格式
第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串,长度为N.只包含小写字母
输出格式
如果可能,输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

public class Main {

 public static void main(String[] args) throws Exception {  

  int n, i;  

 //文件流输出   Scanner sc = new Scanner(new File("test.in"));   

while (sc.hasNext())

{   

  n = Integer.parseInt(sc.nextLine());  

   // 用数组arr[]保留输入的数,  

  String str = sc.nextLine();   

 char arr[] = str.toCharArray();  

   // 用ch来保留出现的出现一次的不同的字母    

char ch = '0';   

 // 用ch1来记录出现不同字母的次数   

 int ch1 = 0;    

// 用count[]数组来记录每个字母出现的次数

   int index;    

int count[] = new int[26];  

   for (i = 0; i < arr.length; i++)

{   

   index = arr[i] - 'a';   

   count[index]++;   

  }   

 show(count, ch, ch1, arr, n);

   }

 }

 private static void show(int[] count, char ch, int ch1, char arr[], int n)

{

   // TODO Auto-generated method stub   

// 开始计算出现不同字母出现一次的个数并把它记录下来

   for (int j = 0; j < count.length; j++)

{

    if (count[j] % 2 != 0)

{     ch1++;   

  ch = (char) (j + 'a');

  }   

}   

// 如果超过了两个或着以上,那么这样肯定不能构成回文数组   

if (ch1 > 1)

{

    System.out.println("Impossible");  

 }

// 只有一个不同字母的时候,进行冒泡法的查找。调用find(),并返回结果;

   else

{  

  int result = find(arr, ch, n);    

System.out.println(result);  

 }

}

private static int find(char[] arr, char ch, int n)

{  

 // TODO Auto-generated method stub  

 // 查找的思想是利用冒泡法的思维,同时从左右两段开始扫描,找到相同的就break,记录下来它的位置  

  // 确定循环的范围   

int i, count = 0, j, k;   

for (i = 0; i < n / 2; i++)

{    

// 从左边向右边扫描,第一个就是唯一不同的字母,遍历比较   

 if (arr[i] == ch)

{    

 for (j = 0; j < n - 1 - i; j++)

{     

 // 构造回文数,当第一个字母和最后一个相同(arr[n-i-1]是固定)并吧它的位置记录下来为进行交换准备,没遇到继续,下一个扫描     

 if (arr[j] == arr[n - i - 1])       break;    

 }     

count += j - i;     

// 记录下位置后,开始交换其他位置的数,从右边开始往左扫描去,    

 // 假如dmmaa--->(找到了第三个位置的a和最后一个相同,所以a到d位置)dmmma---->ddmma结束,   

  for (k = j; k > i; k--)

{     

 arr[k] = arr[k - 1];   

  }    

 // 这里就是构造回文数,既是和最后一个字母相同的字母到第一个的位置,找到了,就进行下一个的扫描     

arr[i] = arr[n - i - 1];

    }    

// 从右边开始扫描,    

else

{   

  for (j = n - 1 - i; j >= i; j--)

{      

if (arr[j] == arr[i])       break;     

}     

count += n - 1 - i - j;   

  // 从右边n-1-i开始,到j结束,所以从左开始往回扫描,从j开始扫描     

for (k = j; k < n - 1 - i; k++)

{   

 arr[k] = arr[k + 1];    

 }     

arr[n - i - 1] = arr[i];    

}

   }

   return count;  

}

}

 



相关阅读:
Top