密码脱落

2019-12-30 142次浏览 已收录 7个评论

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。

例如,输入:
ABCBA
则程序应该输出:
0

再例如,输入:
ABDCDCBABC
则程序应该输出:
3

解题思路:
通过题意知道这种串的正序和逆序是相同的,所以咱们只需求出原串长度减去逆序串的最长子序列的结果,就是需要增加的字符.
需要注意的是最长子序列而不是最长子串,前者是不连续的,后者连续

package seven;
 
import java.util.Scanner;
public class 密码脱落 {
	static Scanner shu = new Scanner(System.in);
	static char[]s1=shu.next().toCharArray();
	static char[]s2=new char[s1.length];
static int dg(int l1,int l2) {
	/*
	 * 1串: ABDCDCBABC
	 * 2串: CBABCDCDBA
	 */
	if(l1>s1.length-1 || l2>s2.length-1)
		return 0;
	if(s1[l1]==s2[l2])
		//如果如果相同坐标的目标值相同,那么上方都进行下一轮的比对,并且步数+1;
		return dg(l1+1,l2+1)+1;
	else
		/*
		 * 如果上一个条件不满足,则对第二个目标l2进行下一轮比对
		 * 递归的参数里需要着重理解:
		 * 先由2串进行查找比对,1串不动;再由1串进行查找比对,2串不动.
		 * 具体比对过程请参考上面1串和2串进行理解
		 */
		return Math.max(dg(l1,l2+1),dg(l1+1,l2));
}
public static void main(String[] args) {
	for(int i=0;i<s2.length;i++) {
		s2[i]=s1[s1.length-i-1];
	}
	System.out.println(s1.length-dg(0,0));
 
}
}
 

渣渣龙, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:密码脱落
喜欢 (0)

您必须 登录 才能发表评论!

(7)个小伙伴在吐槽
  1. 以后多多交流
    渣渣辉2020-03-27 13:01
  2. 奥利给
    沥青2020-03-27 13:25
  3. 记住这个网站了
    hello2020-03-27 13:51
  4. 给你点赞
    沥青2020-03-28 16:41
  5. 以后多发点哦
    白云2020-03-28 17:07
  6. 最好再详细点
    靓妹2020-03-28 17:58
  7. 挺明白的
    我是你哥2020-05-26 10:07