你的位置:首页 > Java教程

[Java教程]完美的代价



问题描述
  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如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;  

  }

}