密码脱落
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。
例如,输入:
ABCBA
则程序应该输出:
0
再例如,输入:
ABDCDCBABC
则程序应该输出:
3
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 3000ms
首先,这道题的思路其实和39节台阶的想法是类似滴 我给大家举一个小例子
1231 有两种加法
先判断第一位1,和最后一位1 相等 继续下两个数
判断第二位2,和倒数第二位3 不相等
这时候有两种方法
one 复制第二位,生成123(2)1;这样就可以继续读1231的第三位和倒数二位 即判断3
two 复制倒数第二位,生成1(3)231;这样就可以继续读1231的第二位和倒数三位 即判断2
1 import java.util.Scanner; 2 3 public class T12 { 4 5 private static int count; 6 7 public static void main(String[] args) { 8 Scanner sc=new Scanner(System.in); 9 String temp=sc.next(); 10 count=temp.length(); 11 int num=0; 12 check(0,temp.length()-1,temp,num); 13 System.out.println("最终结果"+count); 14 15 } 16 17 private static void check(int left, int right, String temp, int num) { 18 // TODO 自动生成的方法存根 19 if(left>=right) 20 { 21 if(num<count) 22 { 23 count=num; 24 } 25 }else { 26 //判断相等 继续下两个数 27 if(temp.charAt(left)==temp.charAt(right)) 28 { 29 check(left+1,right-1,temp,num); 30 }else { 31 //one 复制第二位,生成123(2)1;这样就可以继续读1231的第三位和倒数二位 即判断3 因为添加了数字2所以num+1 32 check(left+1,right,temp,num+1); 33 //two 复制倒数第二位,生成1(3)231;这样就可以继续读1231的第二位和倒数三位 即判断2 因为添加了数字3所以num+1 34 check(left,right-1,temp,num+1); 35 } 36 } 37 38 } 39 40 41 }
高级 可以查看每一步的结果
其实我本来想实现输出最优解法,和输出所有产生的结果的(>_<)但是没有成功,希望来探讨。
1 import java.util.Scanner; 2 3 public class T12a { 4 private static int count; 5 static boolean add=true; 6 public static void main(String[] args) { 7 //num 为每一次结果所添加的字母的个数 count是最小个数 8 Scanner sc=new Scanner(System.in); 9 String temp=sc.next(); 10 StringBuffer varchar=new StringBuffer(); 11 count=temp.length(); 12 int num=0; 13 check(0,temp.length()-1,temp,varchar,num); 14 System.out.println("最终结果"+count); 15 16 } 17 18 private static void check(int left, int right,String varchar, StringBuffer answer, int num) { 19 // TODO 自动生成的方法存根 20 21 if(left>=right) 22 { 23 //例如12321,当left=3,right=3的时候,将中间的字符串3插入到StringBuffer里 24 if(left==right) 25 { 26 int temp=answer.length()/2; 27 answer.insert(temp,varchar.charAt(left)); 28 } 29 if(num<count) 30 { 31 count=num; 32 for(int i=0;i<answer.length();i++) 33 { 34 System.out.print(answer.charAt(i)); 35 36 } 37 System.out.println(); 38 } 39 //(移除)例如12321,当left=3,right=3的时候,将中间的字符串3移除 40 int temp=answer.length()/2; 41 answer.deleteCharAt(temp); 42 //设置开始还原 43 add=false; 44 return; 45 }else { 46 if(varchar.charAt(left)==varchar.charAt(right)) 47 { 48 add(answer,varchar,left); 49 check(left+1,right-1,varchar,answer,num); 50 remove(answer,varchar); 51 }else { 52 add(answer,varchar,left); 53 check(left+1,right,varchar,answer,num+1); 54 remove(answer,varchar); 55 56 add(answer,varchar,right); 57 check(left,right-1,varchar,answer,num+1); 58 remove(answer,varchar); 59 } 60 } 61 62 } 63 public static void add(StringBuffer answer,String varchar,int num) 64 { 65 //例如1231 第一个数和最后一个数相等,将11插入到Stringbuffer里 66 int temp=answer.length()/2; 67 answer.insert(temp,varchar.charAt(num)); 68 answer.insert(temp,varchar.charAt(num)); 69 } 70 public static void remove(StringBuffer answer,String varchar) 71 { 72 if(!add) 73 { 74 int temps=answer.length()/2-1; 75 answer.deleteCharAt(temps); 76 answer.deleteCharAt(temps); 77 //还原结束后设置为开始添加 78 add=true; 79 } 80 } 81 }