java实现蓝桥杯密码脱落
2023-09-14 08:58:12 时间
一 问题描述
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。
例如,输入:
ABCBA
则程序应该输出:
0
再例如,输入:
ABDCDCBABC
则程序应该输出:
3
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 3000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。
二 解决方案
PS:第二个可能好理解一些
import java.util.Scanner;
public class Main {
public static String A;
public static String backA;
public int dfs(int lenA, int lenB) {
if(lenA == -1 || lenB == -1)
return 0;
if(A.charAt(lenA) == backA.charAt(lenB))
return dfs(lenA - 1, lenB - 1) + 1;
else
return Math.max(dfs(lenA - 1, lenB), dfs(lenA, lenB - 1));
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
A = in.nextLine();
backA = "";
for(int i = A.length() - 1;i >= 0;i--)
backA += A.charAt(i);
int result = A.length() - test.dfs(A.length() - 1, backA.length() - 1);
System.out.println(result);
}
}
import java.util.Scanner;
public class 密码脱落 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[] a = scanner.nextLine().toCharArray();
code(a);
}
//左右坐标往中间走,直到i==j
private static void code(char a[]) {
int num = 0;
int i = 0;//左面的坐标
int n = 0;
int m = 0;
int j = a.length - 1;//右面的坐标
while (i <= j) {
n = 0;
m = 0;
//相等
if (a[i] == a[j]) {
i++;
j--;
} else {
//不相等
//循环的终止条件就是左面坐标的值和右面坐标的值相等
int tj = j;//找个临时变量
while (a[i] != a[tj]) {
tj--;//右面的往左走
n++;//记录走的步数
}
int ti = i;//找个临时变量
while (a[ti] != a[j]) {
ti++;//左面的往右走
m++;//记录走了几步
}
if (n < m) {//看看哪个步数少,就用哪个
//n<m说明左面走的步数多
j -= n;
} else {
//相反
i += m;
}
//num为总的修改数,经过上面的比较,哪个修改数少就采用哪一个
num += n < m ? n : m;
}
}
System.out.println(num);
}
}
相关文章
- Java maven依赖的jar中的类,无法导入
- JAVA学习(五):Java面向对象编程基础
- Java实现 洛谷 P1914 小书童——密码
- java实现Playfair 密码
- java实现Playfair 密码
- java实现蓝桥杯密码脱落
- Java实现最近点问题
- Java实现 蓝桥杯VIP 算法提高 种树
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- java 11 Java Flight Recorder
- 【JAVA】Java循环语句中的continue跳转进入下一次循环是否判断循环条件
- Java面向对象编程篇1——类与对象
- Atitit.Java exe bat 作为windows系统服务程序运行
- Interview:Java岗位面试—面试求职攻略之一个JAVA程序员面试心得(非常值得收藏)
- 【java】Java教程
- 【java】Java 枚举(enum)如何使用以及原理
- Java中的参数传递,到底是值传递还是引用传递?
- JAVA字符串怎么转换成整数
- JAVA学习第十九课(java程序的异常处理 (二))
- 分享一波中高级测试面试题(偏Java)
- 在线EXCEL绝配:SpreadJS 16.0.3 + GcExcel Java 6.0.3
- 【java】Java 接口(Interface)
- 【java】Java 多态
- 【java】Java线程池实现原理及业务中的实践