快捷導航

基于Java解決華為機試實現(xiàn)密碼截取?

更新時間：2022年02月23日 08:45:40 作者：97的風

這篇文章主要介紹了基于Java解決華為機試實現(xiàn)密碼截取,文章圍繞主題相關(guān)資料展開詳細內(nèi)容，具有一的參考價值，需要的小伙伴可以參考一下，希望對你有所幫助

1.簡述

描述:

Catcher是MCA國的情報員，他工作時發(fā)現(xiàn)敵國會用一些對稱的密碼進行通信，比如像這些ABBA，ABA，A，123321，但是他們有時會在開始或結(jié)束時加入一些無關(guān)的字符以防止別國破解。比如進行下列變化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因為截獲的串太長了，而且存在多種可能的情況（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量實在是太大了，他只能向電腦高手求助，你能幫Catcher找出最長的有效密碼串嗎？

數(shù)據(jù)范圍：字符串長度滿足1 \le n \le 2500 \1≤n≤2500

輸入描述：

輸入一個字符串（字符串的長度不超過2500）

輸出描述：

返回有效密碼串的最大長度

示例1

輸入：

ABBA

輸出：

4

示例2

輸入：

ABBBA

輸出：

5

示例3

輸入：

12HHHHA

復制輸出：

4

2.代碼實現(xiàn)

?解題思路：

最長回文子串的中心擴散法，遍歷每個字符作為中間位，進行左右比較

算法流程：

從右到左，對每個字符進行遍歷處理，并且每個字符要處理兩次，因為回文子串有兩種情況：

ABA型：只需要從當前字符向兩邊擴散，比較左右字符是否相等，找出以當前字符為中心的最長回文子串長度

ABBA型：只需要從當前字符和下一個字符向兩邊擴散，比較左右字符是否相等，找出以當前字符和下一個字符為中心的最長回文子串長度

最后比對兩種類型的長度，取自較長的長度

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;
? ? }
}

方法二：動態(tài)規(guī)劃

解題思路：

對于最值問題，往往可以采用動態(tài)規(guī)劃思想降低時間復雜度和狀態(tài)壓縮，采用空間換時間的思想

算法流程：

確定狀態(tài)：對比的兩個字符索引起始和終止索引位置

定義 dp 數(shù)組：字符串s的 i 到 j 索引位置的字符組成的子串是否為回文子串

狀態(tài)轉(zhuǎn)移: 如果左右兩字符相等, 同時[l+1...r-1]范圍內(nèi)的字符是回文子串, 則[l...r] 也是回文子串

狀態(tài)轉(zhuǎn)移的同時，不斷更新對比的子串長度，最終確定最長回文子串的長度

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
? ? public static void main(String[] args) throws IOException {
? ? ? ? BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
? ? ? ? String s = "";
? ? ? ? while ((s = br.readLine()) != null) {
? ? ? ? ? ? System.out.println(validLen(s));
? ? ? ? }
? ? ? ? br.close();
? ? }

? ? public static int validLen(String s) {
? ? ? ? int len = s.length();
? ? ? ? // 狀態(tài)：對比的兩個字符索引起始和終止索引位置
? ? ? ? // 定義: 字符串s的i到j(luò)字符組成的子串是否為回文子串
? ? ? ? boolean[][] dp = new boolean[len][len];
? ? ? ? int res = 0;
? ? ? ? // base case
? ? ? ? for(int i = 0; i < len - 1; i++) {
? ? ? ? ? ? dp[i][i] = true;
? ? ? ? }

? ? ? ? for(int r = 1; r < len; r++) {
? ? ? ? ? ? for(int l = 0; l < r; l++) {
? ? ? ? ? ? ? ? // 狀態(tài)轉(zhuǎn)移：如果左右兩字符相等,同時[l+1...r-1]范圍內(nèi)的字符是回文子串
? ? ? ? ? ? ? ? // 則 [l...r] 也是回文子串
? ? ? ? ? ? ? ? if(s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp[l+1][r-1])) {
? ? ? ? ? ? ? ? ? ? dp[l][r] = true;
? ? ? ? ? ? ? ? ? ? // 不斷更新最大長度
? ? ? ? ? ? ? ? ? ? res = Math.max(res, r - l + 1);
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}

到此這篇關(guān)于基于Java解決華為機試實現(xiàn)密碼截取的文章就介紹到這了,更多相關(guān)Java密碼截取內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: