基於Java解決華為機試實現密碼截取 

Posted on by

1.簡述

描述:

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

數據范圍：字符串長度滿足1 \le n \le 2500 \1≤n≤2500 

輸入描述：

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

輸出描述：

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

示例1

輸入：

ABBA

輸出：

4

示例2

輸入：

ABBBA

輸出：

5

示例3

輸入：

12HHHHA

復制輸出：

4

2.代碼實現

​解題思路：

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

算法流程：

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

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

方法二：動態規劃

解題思路：

對於最值問題，往往可以采用動態規劃思想降低時間復雜度和狀態壓縮，采用空間換時間的思想

算法流程：

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

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

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

狀態轉移的同時，不斷更新對比的子串長度，最終確定最長回文子串的長度

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();
        // 狀態：對比的兩個字符索引起始和終止索引位置
        // 定義: 字符串s的i到j字符組成的子串是否為回文子串
        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++) {
                // 狀態轉移：如果左右兩字符相等,同時[l+1...r-1]范圍內的字符是回文子串
                // 則 [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;
    }
}

到此這篇關於基於Java解決華為機試實現密碼截取 的文章就介紹到這瞭,更多相關Java密碼截取 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：