基础练习完美的代价

阳光穿透心脏的1/2处 2022-06-01 09:59 148阅读 0赞

基础练习 完美的代价

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

问题描述

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

输入格式

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

输出格式

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

样例输入

5  
mamad

样例输出

1.从左往右获取charArray\[i\],对于每一个charArray\[i\]从右往左遍历找到charArray\[j\]与之相匹配。

2.若没有匹配，（1）字符串长度为奇数则可能是最中间的字符:

记录charArray\[i\]（全程序只记录一次），与前一位置交换，交换次数记一次，  
                           即： charArray\[i\]=charArray\[i+1\]；  
                         对于此时的charArray\[i\]继续执行1

若还有不能匹配且不等于charArray\[i\]的，说明不能匹配成回文，输出Impossible

（2）字符串长度为偶数 则不能形成回文，输出Impossible

3.若匹配，则将charArray\[j\]交换到相匹配的位置（与charArray\[j\]对称的位置）。并记录交换次数。输出次数

import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) { 
    		boolean b=true; //是否匹配
    		char x1 = 0 ;//x1记录字符串长度为奇数且第一次未匹配，x2记录第二次未匹配。
    		int sum = 0;//交换次数
            Scanner sc=new Scanner(System.in);
            int n = sc.nextInt();
            char[] charArray = new char[n];
            charArray = sc.next().toCharArray();//输入的字符串转化为字符数组
            //i表示从左往右未匹配字符的下标
            //j表示从右往左未匹配的字符下标
            for (int i = 0; i < charArray.length/2; i++) {
            	//如果不能能匹配（字符串长度为奇数）
            		//从右向左找与左边下标为i的字符相匹配的
            		for (int j = i; j < charArray.length-1-i; j++) {
            			//如果匹配
    	        		if(charArray[i] == charArray[charArray.length-1-j]){
    	        			
    	        			b=true;
    	        			//如果左右不对称则交换
    		        			if(i!=j){
    		        				char a = charArray[charArray.length-1-j];
    			        				for (int k = j; k > i; k--) {
    			        					sum++;
    			        					charArray[charArray.length-1-k] = 
    			        						charArray[charArray.length-k];
    			        				}
    		        				charArray[charArray.length-1-i] = a;
    		        				
    		        			}
    		        			break;//匹配完成就跳出j的循环
    	        		}else{
    	        			 b=false;
    	        			 //若最后一次未匹配到，则保存charArray[i]
    	        			 if(j==charArray.length-i-2&&charArray[i] != 
    	        					 charArray[charArray.length-1-j]){
    	        				  if(x1 ==charArray[i]||x1==0)
    	        					  x1 = charArray[i];
    	        			 }
    	        		}
            		}
            		if(b==false){
                		if(charArray.length%2==1&&charArray[i]==x1){
                			sum++;
    		        		char g = charArray[i+1];
    		        		charArray[i+1]=charArray[i];
    		        		charArray[i]=g;
    		        		b=true;
        	        		i--;//重新匹配charArray[i]；
                		}else
                			break;
                	}
    		}
            if(b)
            	System.out.println(sum);
            else
            	System.out.println("Impossible");
        } 
    }

不对之处请多指教！

<table style="margin-right:0px;margin-bottom:0px;margin-left:0px;padding:0px;font-family:'宋体', 'Times New Roman';color:rgb(0,0,0);font-size:13px;"> 
 <tbody style="margin:0px;padding:0px;"> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:0px;font-family:'宋体', 'Times New Roman';"><a href="http://lx.lanqiao.cn/problem.page?gpid=T60" style="margin:0px;padding:0px;color:rgb(149,174,234);" rel="nofollow">完美的代价</a></td> 
  </tr> 
 </tbody> 
</table>