年輕即出發(fā)...

簡書：http://www.itdecent.cn/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源碼：https://github.com/zqtao2332

個人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容）

QQ交流群：606939954

? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時間，盡你自己最大的努力。努力做成你最想做的那件事，成為你最想成為的那種人，過著你最想過的那種生活。也許我們始終都只是一個小人物，但這并不妨礙我們選擇用什么樣的方式活下去，這個世界永遠(yuǎn)比你想的要更精彩。

最后：喜歡編程，對生活充滿激情

本節(jié)內(nèi)容預(yù)告

實例1：數(shù)字序列

實例2：神奇數(shù)

實例3：兩個連續(xù)str作為子串的最短字符串

實例4：合法括號序列拆分方案

實例5：最短回文長度

實例1：數(shù)字序列

東東從京京那里了解到有一個無限長的數(shù)字序列: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...(數(shù)字k在該序列中正好出現(xiàn)k次)。

東東想知道這個數(shù)字序列的第n項是多少,你能幫幫他么輸入描述:

輸入包括一個整數(shù)n(1 <=n<=10^18)

輸出描述：

輸出一個整數(shù)，即數(shù)字序列的第n 項

示例1

輸入169

輸出18

/**
 * 1 22 333 4444 5555
 *
 * 每個連續(xù)數(shù)字的結(jié)尾
 * 1:1
 * 2:3
 * 3:6
 * 4:10
 * 5:15
 *
 * 每一個結(jié)尾，在這里可以看做是等差數(shù)列的求和
 * 例如
 * 6：是1+2+3
 * 15:是1+2+3+4+5
 * 即每個連續(xù)數(shù)的結(jié)尾數(shù)，是這個連續(xù)數(shù)的單數(shù)等差數(shù)列的和
 * 等差數(shù)列求和公式 S(n)= n*(n+1)/2
 *
 * 現(xiàn)在知道了這個 S(n) --> K 來反推這個連續(xù)數(shù)
 */
public class Code_34_NNum {

    public static int getNum(long n) {
        return (int) Math.ceil((Math.sqrt(1 + 8 * ((double) n)) - 1) / 2);
    }
}

實例2：神奇數(shù)

東東在一本古籍上看到有一種神奇數(shù),如果能夠?qū)⒁粋€數(shù)的數(shù)字分成兩組,其中一組數(shù)字的和等于另一組數(shù)字的和,我們就將這個數(shù)稱為神奇數(shù)。例如242就是一個神奇數(shù),我們能夠?qū)⑦@個數(shù)的數(shù)字分成兩組,分別是12,2}以及[4),而且這兩組數(shù)的和都是4.東東現(xiàn)在需要統(tǒng)計給定區(qū)間中有多少個神奇數(shù),即給定區(qū)間[1, r],統(tǒng)計這個區(qū)間中有多少個神奇數(shù),請你來幫助他。

輸入描述：

輸入包括一行，一行中有兩個整數(shù)L和R

輸出描述:

輸出一個整數(shù),即區(qū)間內(nèi)的神奇數(shù)個數(shù)

示例1輸入1 50

輸出4

import java.util.ArrayList;

/**
 * 思路：背包問題
 * 背包問題就是行是可選擇的數(shù)，列是能組合成的各種可能結(jié)果
 */
public class Code_35_SplitNumberToTwoParts {
    /**
     * 將num 分解為獨立的數(shù)
     * 求和，然后求是否能夠組合成 sum/2
     * <p>
     * dp[][]
     */
    public static boolean isMagic(int num) {
        int sum = 0;
        ArrayList<Integer> nums = new ArrayList<>();
        while (num != 0) {
            int n = num % 10;
            nums.add(n);
            sum += n;
            num /= 10;
        }

        if ((sum & 1) == 1) return false; // 和是奇數(shù)無法加出 sum / 2
        sum = sum / 2;
        boolean[][] dp = new boolean[nums.size()][sum + 1];
        dp[0][0] = true;
        if (nums.get(0) <= sum) dp[0][nums.get(0)] = true; // 初始化第一行，只有第一個數(shù)時，這個數(shù)不能超過 sum
        for (int i = 1; i < nums.size(); i++) {
            for (int j = sum; j >= 0; j--) {
                dp[i][j] = dp[i - 1][j] || (j - nums.get(i) >= 0 ? dp[i - 1][j - nums.get(i)] : false);
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (dp[i][sum]) {
                return true;
            }
        }
        return false;
    }

    /**
     * dp[]
     * 降維處理，節(jié)約空間資源
     *
     * 從右往左進(jìn)行填充，不要從左往右進(jìn)行填充，
     * i 表示第 i 行，那么從左往右填充時，它依賴的上一行的數(shù)已經(jīng)改變
     * 例如
     *
     * 224
     *      0 1 2 3 4 5 6 7 8
     * 2    T F F T F F F F F
     * 2
     * 4
     *
     * 如上從左往右進(jìn)行遍歷時，i=1,arr[i]=2,那么j=5號位置的填充，
     * 需要依賴的是上一行i=0時的 j-arr[i]=3 和 5 兩個位置，
     * 由于從左往右進(jìn)行更新，那么 3 號位置的信息已經(jīng)被修改，不再是原來上一行的信息了
     */
    public static boolean isMagic2(int num) {
        int sum = 0;
        int tmp = num;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }

        if ((sum & 1) == 1) return false;// 奇數(shù)
        sum = sum / 2;

        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        num = tmp;
        int cur = 0;
        while (num != 0) {
            cur = num % 10;
            for (int i = sum; i >= 0; i--) { // 從右往左進(jìn)行填表
                dp[i] = dp[i] || (i - cur >= 0 ? dp[i - cur] : false);
            }
            if (dp[sum]) return true; // 只要加出sum 立即結(jié)束
            num /= 10;
        }
        return false;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100000; i++) {
            int num = (int) (Math.random() * 100000 + 1);
            try {
                if (num != 0 && isMagic(num) != isMagic2(num)) {
                    System.out.println(num);
                    System.out.println(isMagic(num));
                    System.out.println(isMagic2(num));
                }
            } catch (Exception e) {
                System.out.println(num + "\t\t" + e.toString());
            }
        }
    }
}

實例3：兩個連續(xù)str作為子串的最短字符串

給定一個字符串s,請計算輸出含有連續(xù)兩個s作為子串的最短字符串。注意兩個s可能有重疊部分。例如, "ababa"含有兩個"aba"輸入描述:輸入包括一個字符串s,字符串長度length (1 <=ength <= 50), s中每個字符都是小寫字母.輸出描述:輸出一個字符串,即含有連續(xù)兩個s作為子串的最短字符串。

示例1輸入abracadabra

輸出abracadabracadabra

具體意思就是給定一個字符串Str=“abcdd" 輸出含有兩個Str的字符串

KMP算法

字符串查找算法，簡稱為 “KMP算法”，常用于在一個文本串S內(nèi)查找一個模式串P 的出現(xiàn)位置

KMP算法 解決 str1 中是否包含 str2
包含返回 str2 開始位置，不包含返回 -1

1、暴力方法：以str1 的每一個字符去 匹配str2 的每一個字符，str1長N, str2長M,時間復(fù)雜度 O(M*N)
2、KMP算法 str1長N, str2長M 可以優(yōu)化到 O(N) N > M

開始了解KMP算法前，先了解最長前綴和最長后綴匹配

注意：最長前綴和最長后綴匹配不是針對 str1 的，是針對str2的

一個例子理解：最長前綴和最長后綴匹配

aaaab 求 其中 b 的最長前綴和最長后綴匹配

aaaab

長度  前綴  后綴
1   a   a
2   aa  aa
3   aaa aaa
那么字符串a(chǎn)aaab 中 b 的最長前綴和最長后綴匹配就是 aaa ，長度為3
其中前綴不能沖到 aaaa 長度為4位置，同理后綴

人為規(guī)定
前綴不能包含最后一個字符
后綴不能包含第一個字符

求一個字符串中每一個字符的最長前綴和最長后綴匹配，用next[] 記錄

str:    a   a   a   a   a
next[]  -1  0   1   2   3

時間復(fù)雜度分析

1、未斷掉，Str1直接匹配出Str2

2、斷掉

未斷掉，走的就是 Str2 的長度 ，時間復(fù)雜度 O(N)

斷掉，一旦斷掉Str2 的開始指針就前移一位，知道結(jié)束，時間復(fù)雜度也是 O(N)

next[] 怎么求？

人為規(guī)定 0 位置：-1；1位置：0

其他位置 ，當(dāng)求解 i 位置的時候，可以認(rèn)為 0~i 位置的已經(jīng)求解完畢。

import java.util.Arrays;

/**
 * @description: 連續(xù)Str子串的最短字符串
 * @version: 1.0
 */
public class Code_36_ShortestHaveTwice {

    public static String answer(String str) {
        if (str == null || str.length() == 0) return "";
        char[] chars = str.toCharArray();
        if (chars.length == 1) return str + str;
        if (chars.length == 2) // ab -->  aba是最短的
            return chars[0] == chars[1] ? (str + String.valueOf(chars[0])) : str + str;
        int endNext = endNextLength(chars);
        return str + str.substring(endNext);
    }

    // 求next[]
    private static int endNextLength(char[] chars) {

        int[] next = new int[chars.length + 1];
        next[0] = -1;
        next[1] = 0; // 人為規(guī)定0：-1 ，1:0
        int position = 2; // 指向chars[] 的第position位置的元素
        int cn = 0; // 指向next[] 最長前綴和后綴匹配位置
        while (position < next.length) {
            if (chars[position - 1] == chars[cn]){
                next[position++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[position++] = 0;
            }
        }

        System.out.println(Arrays.toString(next));
        return next[next.length - 1];
    }


    /**
     * KMP算法
     * KMP算法 解決 str1 中是否包含 str2
     * 包含返回 str2 開始位置，不包含返回 -1
     *
     * 1、暴力方法：以str1 的每一個字符去 匹配str2 的每一個字符，str1長N, str2長M,時間復(fù)雜度 O(M*N)
     * 2、KMP算法 str1長N, str2長M 可以優(yōu)化到 O(N) N > M
     *
     * 此題僅僅使用了KMP 算法中的 next[] 的應(yīng)用
     */
    public static void main(String[] args) {
        String test1 = "a";
        System.out.println(answer(test1));

        String test2 = "aa";
        System.out.println(answer(test2));

        String test3 = "ab";
        System.out.println(answer(test3));

        String test4 = "abcdabcd";
        System.out.println(answer(test4));

        String test5 = "abracadabra";
        System.out.println(answer(test5));
        System.out.println("abracadabra".substring(4)); // 保留 i+1~length-1位置
    }
}

實例4：合法括號序列拆分方案

合法的括號匹配序列被定義為:、

1.空串""是合法的括號序列

2.如果" "和"Y"是合法的序列,那么"XY"也是一個合法的括號序列

3,如果"X"是一個合法的序列,那么"(X) "也是一個合法的括號序列

4,每個合法的括號序列都可以由上面的規(guī)則生成例如"", "()", "() () ()", "(() ())", "(((0))"都是合法的。

東東現(xiàn)在有一個合法的括號序列s,一次移除操作分為兩步:

1·移除序列s中第一個左括號

2,移除序列s中任意一個右括號保證操作之后s還是一個合法的括號序列

東東現(xiàn)在想知道使用上述的移除操作有多少種方案可以把序列s變?yōu)榭?/p>

如果兩個方案中有一次移除操作移除的是不同的右括號就認(rèn)為是不同的方案。例如: s= "() () () () ()",輸出1,因為每次都只能選擇被移除的左括號所相鄰的右括號.s= "(((()))) ,輸出24,第一次有4種情況,第二次有3種情

輸入描述：

輸入包括一行，一個合法的括號序列s，序列長度 <=20

輸出描述：

輸出一個整數(shù)，表示方案數(shù)。

(((())))
4*3*2*1=24

思路：
求每一個左括號，右括號比左括號多多少
( ( ( ) ) )
1 2 3

從右向左進(jìn)行遍歷，維護(hù)一個sum ， 遇到右括號++，左括號--

查看一個單獨的合法括號序列移除方案

( ( ( ) ) )
第一個( 可以支配的右括號是3個
第二個( 可以支配的右括號是2個
第三個( 可以支配的右括號是1個

( ( ( ) ) )
3 2 1

所以這個合法括號序列移除方案是3*2*1個

其實統(tǒng)計出每一個左括號位置，右括號比左括號多多少，逆序就是每一個( 可以支配的括號數(shù)

public class Code_37_Parentheses {
    /**
     * 維護(hù)一個sum 變量，遇到 ) ,sum++，遇到 ( sum--
     *
     * 思路：
     * 求每一個左括號，右括號比左括號多多少
     * ( ( ( ) ) )
     * 1 2 3
     *
     * 從右向左進(jìn)行遍歷，維護(hù)一個sum ， 遇到右括號++，左括號--
     *
     * 查看一個單獨的合法括號序列移除方案
     * ( ( ( ) ) )
     * 第一個( 可以支配的右括號是3個
     * 第二個( 可以支配的右括號是2個
     * 第三個( 可以支配的右括號是1個
     *
     * ( ( ( ) ) )
     * 3 2 1
     *
     * 所以這個合法括號序列移除方案是3*2*1個
     * 其實統(tǒng)計出每一個左括號位置，右括號比左括號多多少，逆序就是每一個( 可以支配的括號數(shù)
     */
    public static int possibilities(String parentheses) {
        char[] chars = parentheses.toCharArray();
        int ans = 1;
        int sum = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == ')'){
                sum++;
            } else {
                ans *= sum--;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(possibilities("((()))")); // 6
        System.out.println(possibilities("()(())")); // 2
        System.out.println(possibilities("()()()")); // 1
    }
}

實例5：最短回文長度

京京和東東是好朋友。東東很喜歡回文?；匚氖侵笍那巴笞x和從后往前讀是一樣的詞語。京京準(zhǔn)備給東東一個驚喜,先取定一個字符串s,然后在后面附上0個或者更多個字母形成回文,京京希望這個回文越短越好。請幫助京京計算他能夠得到的最短的回文長度。

輸入描述:輸入包括一個字符串s,字符串s長度length (1 <=length<= 50)

輸出描述:輸出一個整數(shù),表示牛牛能夠得到的最短的回文長度。

示例1輸入 abab輸出 5

import java.util.Arrays;

/**
 * @description: 最短回文長度
 */
public class Code_38_ShortestMakePalindrome {

    /**
     * 思路：必須包含最后一個字符的情況下，求最長的回文子串，其中，不是回文串的范圍字符，逆序填在后面即可
     * 如 abc1234321
     * 必須包含最后一個字符 4 的情況下，最長的回文子串是 1234321
     * 將不包含在最長回文子串內(nèi)的其他字符abc逆序cba --> 添加在后面  abc1234321cba
     *
     * 算法被分解為，怎么求一個字符串的最長回文子串，子串要求連續(xù)
     * 1、暴力解
     * 以每一個字符向兩邊進(jìn)行擴(kuò)散
     * 121
     *  null<-1->2     ---->0
     *  1<-2->1        ---->3
     *  2<-1->1        ---->0
     *  所以擴(kuò)散的最長回文長度就是 3
     *  但是問題來了，對于這種對稱擴(kuò)散尋找，121 奇數(shù)個，是以實軸進(jìn)行的擴(kuò)散，
     *  然而 1221 偶數(shù)個，是虛軸擴(kuò)散才能找到真正的值4，不然就是 0
     *
     *  處理方式：不管是奇數(shù)個還是偶數(shù)個，都進(jìn)行擴(kuò)容處理，求解完畢后除以 2 得到的就是解
     *  121 --> #1#2#1#  最長對稱是 7  7/2=3
     *  1221--> #1#2#2#1# 最長對稱是 9  9/2=4
     *
     *  注意：添加的字符是 任意的，可以是存在的字符，如 2，不影響相對的結(jié)果
     *  時間復(fù)雜度 O(N^2)
     *
     *
     * 2、Manacher 算法
     *
     * 1）、回文半徑：以每個位置的字符為回文中心求出的回文半徑長度；
     *      維護(hù)一個回文半徑數(shù)組，記錄每一個位置可以擴(kuò)散的回文半徑
     * 2）、回文最右邊界：這個位置及之前的位置的回文子串，所到達(dá)的最右邊的地方，同時記錄最右回文中心；
     *      如果有兩個位置擴(kuò)散到同一個右邊界，只記錄最早的那個。
     *
     *      如  # 1 # 2 # 2 # 1 #
     *          0 1 2 3 4 5 6 7 8
     *          4號位置# 的回文最右邊界達(dá)到了8號位置
     *          7號位置1 的回文最右邊界達(dá)到了8號位置
     *          最右回文中心只記錄 4 號位置，不記錄 7 號位置
     *
     *算法出現(xiàn)的幾種情況
     * a、當(dāng)前所求的位置，不在左右邊界里，此時和暴力方法一樣，向兩邊依次檢查
     *      如  # 1 # 2 # 2 # 1 #
     *          0 1 2 3 4 5 6 7 8
     *          0號位置，不在邊界，擴(kuò)
     *          1號位置，不在邊界，向兩邊依次檢查，擴(kuò)到了2 號位置，此時更新左右邊界為 2
     * b、在最右回文右邊界里面
     * c、在最右回文右邊界外
     * d、壓線
     *
     * 其中一點就是找到回文的最右邊界就停, 同時記錄這個最大的回文半徑
     *
     */

    // 預(yù)處理字符串，排除奇偶個字符的影響
    public static char[] getPreprocessedStr(String str){
        char[] tmp = new char[str.length() * 2 + 1];
        int j = 0;
        for (int i = 0; i < tmp.length; i++) {
            if ((i & 1) == 0) {
                tmp[i] = '#';
            } else {
                tmp[i] = str.charAt(j);
            }
            tmp[i] = (i & 1) == 0 ? '#' : str.charAt(j++);
        }
        return tmp;
    }

    public static int manacherStr(String str) {
        if (str == null || str.length() == 0) return 0;

        char[] preArr = getPreprocessedStr(str);// 預(yù)處理字符串，排除奇偶影響

        int index = -1; // 最右回文對稱中心
        int maxR = -1; // 最右回文延伸邊界
        int max = -1; // 最大延伸長度
        int[] radius = new int[preArr.length]; // 記錄每個字符可以延伸的最大回文邊界

        for (int i = 0; i < preArr.length; i++) {
            // 找到當(dāng)前點關(guān)于最右回文對稱中心的對稱點位置
//            int symmetryNode = radius[2 * index - i];
            // 當(dāng)前點的狀態(tài)，1、在最右回文邊界之外，暫時假設(shè)只有自己是回文字符串，記錄為1
            // 2、在最右回文邊界之內(nèi)，記錄為對稱點的回文邊界和最右邊界-i 中最小的
            radius[i] = maxR > i ? Math.min(radius[2 * index - i], maxR - i) : 1;

            // 檢查并更新當(dāng)前下標(biāo)為中心的回文串最遠(yuǎn)延伸的長度
            while (i + radius[i] < preArr.length // 當(dāng)前位置擴(kuò)出的最大右邊界不能超出數(shù)組范圍
                && (i - radius[i] + 1) > 0 // 當(dāng)前位置存在左邊點 ：i-radius[i] <-i-> i+radius[i], 可以繼續(xù)向兩邊擴(kuò)
            ) {
                // 繼續(xù)向外擴(kuò)充，尋找最大的回文半徑
                if (preArr[i + radius[i]] == preArr[i - radius[i]]){
                    radius[i]++;
                } else {
                    break;
                }
            }

            if (i + radius[i] > maxR) {
                maxR = i + radius[i]; // 更新最大回文右邊界
                index = i; // 更新最大回文右邊界
            }

            if (maxR == preArr.length) { // 最大回文右邊界已經(jīng)擴(kuò)到了最后一個字符
                max = radius[i]; // 記錄最大回文半徑
                break;
            }

            System.out.println(Arrays.toString(radius));
        }

        System.out.println("max: " + max);
        return str.length() * 2 - max + 1;
    }

    public static void main(String[] args) {
        System.out.println(manacherStr("abb"));
    }
}