网页模板怎么做网站,wordpress无法登录界面,济宁seo营销,自适应网站好建们前言
经过前期的数据结构和算法学习#xff0c;开始以OD机考题作为练习题#xff0c;继续加强下熟练程度。有需要的可以同步练习下。
描述
Catcher是MCA国的情报员#xff0c;他工作时发现敌国会用一些对称的密码进行通信#xff0c;比如像这些ABBA#xff0c;ABA…前言
经过前期的数据结构和算法学习开始以OD机考题作为练习题继续加强下熟练程度。有需要的可以同步练习下。
描述
Catcher是MCA国的情报员他工作时发现敌国会用一些对称的密码进行通信比如像这些ABBAABAA123321但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA-12ABBA,ABA-ABAKK,123321-51233214 。因为截获的串太长了而且存在多种可能的情况abaaab可看作是aba,或baaab的加密形式Cathcer的工作量实在是太大了他只能向电脑高手求助你能帮Catcher找出最长的有效密码串吗
数据范围字符串长度满足 1≤≤2500 1≤n≤2500
输入描述
输入一个字符串字符串的长度不超过2500
输出描述
返回有效密码串的最大长度
示例1 输入 12HHHHA输出 4 实现原理
根据题干分析该题是最长回文子串的判断。
1.采用滑动窗口的形式逐步判断滑动窗口内的字符串是否符合对应密码的要求。具体实现见如下。
实现代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别String input in.nextLine();int left 0;int right input.length();int res0;//System.out.println(input.length());for (int i 0; i input.length(); i) {for(int jinput.length()-1;ji1;j--){ int oneStepRescheck(input.substring(i,j1));if(oneStepRes0){resMath.max(res,oneStepRes);break;} } }System.out.println(res);}public static int check(String str) {//System.out.println(str);int left 0;int right str.length() - 1;boolean flagtrue;;while(leftright){if(str.charAt(left) str.charAt(right)){//System.out.println(left:str.charAt(left));left;right--;continue;}else{flagfalse;break;}}if(flag){//System.out.println(str.length());return str.length();}return 0;}}
动态规划法
从上述的算法来看存在较多的重复判断。大大增加算法执行时间。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws IOException {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别String input in.nextLine();int resvalidLen(input);System.out.println(res);in.close();}public static int validLen(String s) {int len s.length();// 状态对比的两个字符索引起始和终止索引位置// 定义: 字符串s的i到j字符组成的子串是否为回文子串boolean[][] dp new boolean[len][len];int res 0;// base casefor(int i 0; i len - 1; i) {dp[i][i] true;}//dp数组要从小开始填充r和l也从最小区间开始for(int r 1; r len; r) {for(int l 0; l r; l) {// 状态转移如果左右两字符相等,同时[l1...r-1]范围内的字符是回文子串// 则 [l...r] 也是回文子串if(s.charAt(l) s.charAt(r) (r-l 2 || dp[l1][r-1])) {dp[l][r] true;// 不断更新最大长度res Math.max(res, r - l 1);} }}return res;}
}中心扩散法
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);String s sc.nextLine();System.out.println(solution(s));}private static int solution(String s) {int res 0;for(int i 0; i s.length(); i) {// ABA型int len1 longest(s, i, i);// ABBA型int len2 longest(s, i, i 1);res Math.max(res, len1 len2 ? len1 : len2);}return res;}private static int longest(String s, int l, int r) {while(l 0 r s.length() s.charAt(l) s.charAt(r)) {l--;r;}return r - l - 1;}
}
