摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數(shù)值為或者字符串不是一個合法的數(shù)值則返回。

本文作者：wwwxmu

原文地址:https://www.weiweiblog.cn/13s...

作者的博客站點：https://www.weiweiblog.cn/ （推薦哦?。?/p>

考慮到篇幅問題，我會分兩次更新這個內(nèi)容。本篇文章只是原文的一部分，我在原文的基礎(chǔ)上增加了部分內(nèi)容以及修改了部分代碼和注釋。另外，我增加了愛奇藝 2018 秋招 Java：求給定合法括號序列的深度 這道題。所有代碼均編譯成功，并帶有注釋，歡迎各位享用！

談到字符串問題，不得不提的就是 KMP 算法，它是用來解決字符串查找的問題，可以在一個字符串（S）中查找一個子串（W）出現(xiàn)的位置。KMP 算法把字符匹配的時間復(fù)雜度縮小到 O(m+n) ,而空間復(fù)雜度也只有O(m)。因為“暴力搜索”的方法會反復(fù)回溯主串，導(dǎo)致效率低下，而KMP算法可以利用已經(jīng)部分匹配這個有效信息，保持主串上的指針不回溯，通過修改子串的指針，讓模式串盡量地移動到有效的位置。

具體算法細(xì)節(jié)請參考：

字符串匹配的KMP算法: http://www.ruanyifeng.com/blo...

從頭到尾徹底理解KMP: https://blog.csdn.net/v_july_...

如何更好的理解和掌握 KMP 算法?: https://www.zhihu.com/questio...

KMP 算法詳細(xì)解析: https://blog.sengxian.com/alg...

圖解 KMP 算法: http://blog.jobbole.com/76611/

汪都能聽懂的KMP字符串匹配算法【雙語字幕】: https://www.bilibili.com/vide...

KMP字符串匹配算法1: https://www.bilibili.com/vide...

除此之外，再來了解一下BM算法！

BM算法也是一種精確字符串匹配算法，它采用從右向左比較的方法，同時應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。基本思路就是從右往左進(jìn)行字符匹配，遇到不匹配的字符后從壞字符表和好后綴表找一個最大的右移值，將模式串右移繼續(xù)匹配。
《字符串匹配的KMP算法》:http://www.ruanyifeng.com/blo...

劍指offer：請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。

這里我提供了兩種方法：①常規(guī)方法；②利用 API 解決。

//https://www.weiweiblog.cn/replacespace/
public class Solution {

    /**
     * 第一種方法：常規(guī)方法。利用String.charAt(i)以及String.valueOf(char).equals(" "
     * )遍歷字符串并判斷元素是否為空格。是則替換為"%20",否則不替換
     */
    public static String replaceSpace(StringBuffer str) {

        int length = str.length();
        // System.out.println("length=" + length);
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < length; i++) {
            char b = str.charAt(i);
            if (String.valueOf(b).equals(" ")) {
                result.append("%20");
            } else {
                result.append(b);
            }
        }
        return result.toString();

    }

    /**
     * 第二種方法：利用API替換掉所用空格，一行代碼解決問題
     */
    public static String replaceSpace2(StringBuffer str) {

        return str.toString().replaceAll("s", "%20");
    }
}

Leetcode:  編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

思路很簡單！先利用Arrays.sort(strs)為數(shù)組排序，再將數(shù)組第一個元素和最后一個元素的字符從前往后對比即可！

//https://leetcode-cn.com/problems/longest-common-prefix/description/
public class Main {
    public static String replaceSpace(String[] strs) {

        // 數(shù)組長度
        int len = strs.length;
        // 用于保存結(jié)果
        StringBuffer res = new StringBuffer();
        // 注意：=是賦值，==是判斷
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 給字符串?dāng)?shù)組的元素按照升序排序(包含數(shù)字的話，數(shù)字會排在前面)
        Arrays.sort(strs);
        int m = strs[0].length();
        int n = strs[len - 1].length();
        int num = Math.min(m, n);
        for (int i = 0; i < num; i++) {
            if (strs[0].charAt(i) == strs[len - 1].charAt(i)) {
                res.append(strs[0].charAt(i));
            } else
                break;

        }
        return res.toString();

    } 
     //測試
    public static void main(String[] args) {
        String[] strs = { "customer", "car", "cat" };
        System.out.println(Main.replaceSpace(strs));//c
    }
}

LeetCode:  給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構(gòu)造成的最長的回文串。在構(gòu)造過程中，請注意區(qū)分大小寫。比如"Aa"不能當(dāng)做一個回文字符串。注
意:假設(shè)字符串的長度不會超過 1010。

回文串：“回文串”是一個正讀和反讀都一樣的字符串，比如“l(fā)evel”或者“noon”等等就是回文串。——百度百科  地址：https://baike.baidu.com/item/...

示例 1:

輸入:
"abccccdd"

輸出:
7

解釋:
我們可以構(gòu)造的最長的回文串是"dccaccd", 它的長度是 7。

我們上面已經(jīng)知道了什么是回文串？現(xiàn)在我們考慮一下可以構(gòu)成回文串的兩種情況：

字符出現(xiàn)次數(shù)為雙數(shù)的組合

字符出現(xiàn)次數(shù)為雙數(shù)的組合+一個只出現(xiàn)一次的字符

統(tǒng)計字符出現(xiàn)的次數(shù)即可，雙數(shù)才能構(gòu)成回文。因為允許中間一個數(shù)多帶帶出現(xiàn)，比如“abcba”，所以如果最后有字母落單，總長度可以加 1。首先將字符串轉(zhuǎn)變?yōu)樽址麛?shù)組。然后遍歷該數(shù)組，判斷對應(yīng)字符是否在hashset中，如果不在就加進(jìn)去，如果在就讓count++，然后移除該字符！這樣就能找到出現(xiàn)次數(shù)為雙數(shù)的字符個數(shù)。

//https://leetcode-cn.com/problems/longest-palindrome/description/
class Solution {
    public  int longestPalindrome(String s) {
        if (s.length() == 0)
            return 0;
        // 用于存放字符
        HashSet hashset = new HashSet();
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (!hashset.contains(chars[i])) {// 如果hashset沒有該字符就保存進(jìn)去
                hashset.add(chars[i]);
            } else {// 如果有,就讓count++（說明找到了一個成對的字符），然后把該字符移除
                hashset.remove(chars[i]);
                count++;
            }
        }
        return hashset.isEmpty() ? count * 2 : count * 2 + 1;
    }
}

LeetCode: 給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。 說明：本題中，我們將空字符串定義為有效的回文串。

示例 1:

輸入: "A man, a plan, a canal: Panama"
輸出: true

示例 2:

輸入: "race a car"
輸出: false

//https://leetcode-cn.com/problems/valid-palindrome/description/
class Solution {
    public  boolean isPalindrome(String s) {
        if (s.length() == 0)
            return true;
        int l = 0, r = s.length() - 1;
        while (l < r) {
            // 從頭和尾開始向中間遍歷
            if (!Character.isLetterOrDigit(s.charAt(l))) {// 字符不是字母和數(shù)字的情況
                l++;
            } else if (!Character.isLetterOrDigit(s.charAt(r))) {// 字符不是字母和數(shù)字的情況
                r--;
            } else {
                // 判斷二者是否相等
                if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
                    return false;
                l++;
                r--;
            }
        }
        return true;
    }
}

Leetcode: LeetCode: 最長回文子串 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba"也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

以某個元素為中心，分別計算偶數(shù)長度的回文最大長度和奇數(shù)長度的回文最大長度。給大家大致花了個草圖，不要嫌棄！

//https://leetcode-cn.com/problems/longest-palindromic-substring/description/
class Solution {
    private int index, len;

    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        for (int i = 0; i < s.length() - 1; i++) {
            PalindromeHelper(s, i, i);
            PalindromeHelper(s, i, i + 1);
        }
        return s.substring(index, index + len);
    }

    public void PalindromeHelper(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        if (len < r - l - 1) {
            index = l + 1;
            len = r - l - 1;
        }
    }
}

LeetCode: 最長回文子序列
給定一個字符串s，找到其中最長的回文子序列?？梢约僭O(shè)s的最大長度為1000。
最長回文子序列和上一題最長回文子串的區(qū)別是，子串是字符串中連續(xù)的一個序列，而子序列是字符串中保持相對位置的字符序列，例如，"bbbb"可以是字符串"bbbab"的子序列但不是子串。

給定一個字符串s，找到其中最長的回文子序列。可以假設(shè)s的最大長度為1000。

示例 1:

輸入:
"bbbab"
輸出:
4

一個可能的最長回文子序列為 "bbbb"。

示例 2:

輸入:
"cbbd"
輸出:
2

一個可能的最長回文子序列為 "bb"。

動態(tài)規(guī)劃： dpi = dpi+1 + 2 if s.charAt(i) == s.charAt(j) otherwise, dpi = Math.max(dpi+1, dpi)

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int [][] dp = new int[len][len];
        for(int i = len - 1; i>=0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < len; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
}

愛奇藝 2018 秋招 Java：
一個合法的括號匹配序列有以下定義:

空串""是一個合法的括號匹配序列
如果"X"和"Y"都是合法的括號匹配序列,"XY"也是一個合法的括號匹配序列
如果"X"是一個合法的括號匹配序列,那么"(X)"也是一個合法的括號匹配序列
每個合法的括號序列都可以由以上規(guī)則生成。

例如: "","()","()()","((()))"都是合法的括號序列
對于一個合法的括號序列我們又有以下定義它的深度:

空串""的深度是0
如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度為max(x,y)
如果"X"的深度是x,那么字符串"(X)"的深度是x+1

例如: "()()()"的深度是1,"((()))"的深度是3。牛?，F(xiàn)在給你一個合法的括號序列,需要你計算出其深度。

輸入描述:
輸入包括一個合法的括號序列s,s長度length(2 ≤ length ≤ 50),序列中只包含"("和")"。

輸出描述:
輸出一個正整數(shù),即這個序列的深度。

示例：

輸入:
(())
輸出:
2

思路草圖：

代碼如下：

import java.util.Scanner;

/**
 * https://www.nowcoder.com/test/8246651/summary
 * 
 * @author Snailclimb
 * @date 2018年9月6日
 * @Description: TODO 求給定合法括號序列的深度
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int cnt = 0, max = 0, i;
        for (i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == "(")
                cnt++;
            else
                cnt--;
            max = Math.max(max, cnt);
        }
        sc.close();
        System.out.println(max);
    }
}

劍指offer:  將一個字符串轉(zhuǎn)換成一個整數(shù)(實現(xiàn)Integer.valueOf(string)的功能，但是string不符合數(shù)字要求時返回0)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)。 數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0。

//https://www.weiweiblog.cn/strtoint/
public class Main {

    public static int StrToInt(String str) {
        if (str.length() == 0)
            return 0;
        char[] chars = str.toCharArray();
        // 判斷是否存在符號位
        int flag = 0;
        if (chars[0] == "+")
            flag = 1;
        else if (chars[0] == "-")
            flag = 2;
        int start = flag > 0 ? 1 : 0;
        int res = 0;// 保存結(jié)果
        for (int i = start; i < chars.length; i++) {
            if (Character.isDigit(chars[i])) {// 調(diào)用Character.isDigit(char)方法判斷是否是數(shù)字，是返回True，否則False
                int temp = chars[i] - "0";
                res = res * 10 + temp;
            } else {
                return 0;
            }
        }
        return flag == 1 ? res : -res;

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String s = "-12312312";
        System.out.println("使用庫函數(shù)轉(zhuǎn)換：" + Integer.valueOf(s));
        int res = Main.StrToInt(s);
        System.out.println("使用自己寫的方法轉(zhuǎn)換：" + res);

    }

}

你若盛開，清風(fēng)自來。 歡迎關(guān)注我的微信公眾號：“Java面試通關(guān)手冊”，一個有溫度的微信公眾號。公眾號后臺回復(fù)關(guān)鍵字“1”，你可能看到想要的東西哦！