密码脱落
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：
ABCBA
则程序应该输出：
0
再例如，输入：
ABDCDCBABC
则程序应该输出：
3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
解析：
方案一：
（1）比较第一个和最后一个字符是否相等，不相等则在左边补字符或者在右边补字符保证两端相等。
（2）比较第二个和倒数第二个是否相等，不相等则在左边补字符或者在右边补字符保证两端相等。
（3）依次进行下去。。。
13.PNG
static int min = 1000; //假设最小值为1000
private static void pwd(String s,int left,int right,int count)
{
if(left >= right)
{
if(count < min)
min = count;
return;
}
//如果不想等需要左或右进行补字符(不需要真把字符插入，直接递归即可)
//左补字符right-1即可，右补left+1即可
if(s.charAt(left) != s.charAt(right))
{
pwd(s,left,right-1,count+1);
pwd(s,left+1,right,count+1);
}
else //当连个字符相等时，直接left+1和right-1同时进行
pwd(s,left+1,right-1,count);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.next();
pwd(s,0,s.length()-1,0);
System.out.println(min);
}
由于字符串长度最长为1000，所以此递归深度会很深，效率较低。
方案二：
（1）将原始字符串和倒序之后的字符串进行对比，如下：
ABDCDCBABC
CBABCDCDBA
（2）找出其最长公共子序列字符串的长度，即如下这种情况是最长情况，结果为7。
14.PNG
（3）最少补位数量 = 字符串总长度 - 最长公共子序列长度 = 10 - 7 = 3。
（4）最长公共子序列求解，将两个字符串进行横轴和纵轴摆放比对；
第一行：交叉字符相等为1；交叉字符不相等第一个数字为0，其它数字为左边的数字。
第一列：交叉字符相等为1；交叉字符不相等第一个数字为0，其它数字为上面的数字。
两者交叉字符相等：取左上角+1。
两者交叉字符不相等：取上和左两个数字中的最大值。
A B D C D C B A B C
C 0 0 0 1 1 1 1 1 1 1
B 0 1 1 1 1 1 2 2 2 2
A 1 1 1 1 1 1 1 3 3 3
B 1 2 2 2 2 2 2 3 4 4
C 1 2 2 3 3 3 3 3 4 5
D 1 2 3 3 4 4 4 4 4 5
C 1 2 3 4 4 5 5 5 5 5
D 1 2 3 4 5 5 5 5 5 5
B 1 2 3 4 5 5 6 6 6 6
A 1 2 3 4 5 5 5 7 7 7
取右下角即为最大公共子序列长度 = 7。
private static String reserve(String s)
{
char[] arr1 = s.toCharArray(); //原始字符串
char[] arr2 = new char[arr1.length]; //反转之后字符串
int j = arr1.length-1; //记录原值字符串的下标（依次递减赋值到反转字符串上去）
for (int i = 0; i < arr2.length; i++) {
arr2[i] = arr1[j];
j--;
}
return new String(arr2);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s1 = input.next(); //原始字符串
String s2 = reserve(s1); //反转之后字符串
int[][] arr = new int[s1.length()][s2.length()]; //数组保存子序列数量矩阵
//处理矩阵第一行数据
//第一行：交叉字符相等为1；交叉字符不相等第一个数字为0，其它数字为左边的数字。
for (int j = 0; j < s1.length(); j++) {
if(s1.charAt(j) == s2.charAt(0))
arr[0][j] = 1;
else
arr[0][j] = j == 0 ? 0 : arr[0][j-1] ;
}
//处理矩阵第一列数据
//第一列：交叉字符相等为1；交叉字符不相等第一个数字为0，其它数字为上面的数字。
for (int i = 0; i < s2.length(); i++) {
if(s2.charAt(i) == s1.charAt(0))
arr[i][0] = 1;
else
arr[i][0] = i == 0 ? 0 : arr[i-1][0] ;
}
//处理矩阵其它位置
//两者交叉字符相等：取左上角+1；两者交叉字符不相等：取上和左两个数字中的最大值。
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j < arr.length; j++) {
if(s1.charAt(j) == s2.charAt(i))
arr[i][j] = arr[i-1][j-1] + 1;
else
arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
}
}
int ans = s1.length() - arr[s2.length()-1][s1.length()-1];
System.out.println(ans);
}
网友评论