密码脱落

首页 » 算法 » 密码脱落

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));
 
}
}
 
分享到:
赞(0) 打赏

评论 7

评论前必须登录!

 

  1. #1

    以后多多交流

    渣渣辉8个月前 (03-27)
  2. #2

    奥利给

    沥青8个月前 (03-27)
  3. #3

    记住这个网站了

    hello8个月前 (03-27)
  4. #4

    给你点赞

    沥青8个月前 (03-28)
  5. #5

    以后多发点哦

    白云8个月前 (03-28)
  6. #6

    最好再详细点

    靓妹8个月前 (03-28)
  7. #7

    挺明白的

    我是你哥6个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00