面試算法知識(shí)梳理(3) - 字符串算法第二部分

面試算法代碼知識(shí)梳理系列

面試算法知識(shí)梳理(1) - 排序算法
面試算法知識(shí)梳理(2) - 字符串算法第一部分
面試算法知識(shí)梳理(3) - 字符串算法第二部分
面試算法知識(shí)梳理(4) - 數(shù)組第一部分
面試算法知識(shí)梳理(5) - 數(shù)組第二部分
面試算法知識(shí)梳理(6) - 數(shù)組第三部分
面試算法知識(shí)梳理(7) - 數(shù)組第四部分
面試算法知識(shí)梳理(8) - 二分查找算法及其變型
面試算法知識(shí)梳理(9) - 鏈表算法第一部分
面試算法知識(shí)梳理(10) - 二叉查找樹
面試算法知識(shí)梳理(11) - 二叉樹算法第一部分
面試算法知識(shí)梳理(12) - 二叉樹算法第二部分
面試算法知識(shí)梳理(13) - 二叉樹算法第三部分

一魁亦、概要

本文介紹了有關(guān)字符串的算法第二部分的Java代碼實(shí)現(xiàn)桐绒，所有代碼均可通過(guò) 在線編譯器 直接運(yùn)行，算法目錄：

  • 查找字符串中的最長(zhǎng)重復(fù)子串
  • 求長(zhǎng)度為N的字符串的最長(zhǎng)回文子串
  • 將字符串中的*移到前部，并且不改變非*的順序
  • 不開(kāi)辟用于交換的空間，完成字符串的逆序C++
  • 最短摘要生成
  • 最長(zhǎng)公共子序列

二孩饼、代碼實(shí)現(xiàn)

2.1 查找字符串中的最長(zhǎng)重復(fù)子串

問(wèn)題描述

給定一個(gè)文本文件作為輸入具钥，查找其中最長(zhǎng)的重復(fù)子字符串怎茫。例如昨悼，"Ask not what your country can do for you, but what you can do for your country"中最長(zhǎng)的重復(fù)字符串是“can do for you”蝗锥，第二長(zhǎng)的是"your country"。

解決思路

這里解決問(wèn)題的時(shí)候用到了 后綴數(shù)組 的思想率触，它指的是字符串所有右子集的集合终议，例如字符串abcde，它的后綴數(shù)組就為["abcde", "bcde", "cde", "de", "e"]葱蝗。

解法分為三步：

  • 求得輸入字符串p的后綴數(shù)組穴张，把它存放在一個(gè)List當(dāng)中，這里注意去掉空格的情況两曼。
  • 對(duì)List中的所有元素進(jìn)行快速排序皂甘。快速排序的目的不在于使得整個(gè)數(shù)組有序悼凑，而在于 使得前綴差異最小的兩個(gè)字符串在數(shù)組中位于相鄰的位置偿枕，對(duì)于上面的例子，其排序結(jié)果為：
后綴數(shù)組的快速排序結(jié)果
  • 遍歷排序后的數(shù)組户辫，只需要對(duì)數(shù)組中的 相鄰的兩個(gè)元素 從頭開(kāi)始比較渐夸，計(jì)算出這兩個(gè)字符串相同前綴的長(zhǎng)度。遍歷之后渔欢，取得的最大值就是最長(zhǎng)重復(fù)子串的長(zhǎng)度墓塌，而這兩個(gè)字符串的相同前綴就是最長(zhǎng)重復(fù)子串。

實(shí)現(xiàn)代碼

import java.util.ArrayList;
import java.util.List;
import java.lang.String;

class Untitled {

    static void quickSortStr(List<String> c, int start, int end){
        if(start >= end)
            return;
        int pStart = start;
        int pEnd = end;
        int pMid = start;
        String t = null;
        for (int j = pStart+1; j <= pEnd; j++) {
            if ((c.get(pStart)).compareTo(c.get(j)) > 0) {
                pMid++;
                t = c.get(pMid); 
                c.set(pMid, c.get(j)); 
                c.set(j, t);
            }
        }
        t = c.get(pStart); 
        c.set(pStart, c.get(pMid)); 
        c.set(pMid, t);
        quickSortStr(c, pStart, pMid-1);
        quickSortStr(c, pMid+1, pEnd);
    }
    
    //獲得兩個(gè)字符串從第一個(gè)字符開(kāi)始奥额，相同部分的最大長(zhǎng)度苫幢。
    static int comLen(String p1, String p2){
        int count = 0;
        int p1Index = 0;
        int p2Index = 0;
        while (p1Index < p1.length()) {
            if (p1.charAt(p1Index++) != p2.charAt(p2Index++))
                return count;
            count++;
        }
        return count;
    }

    static String longComStr(String p, int length){
        List<String> dic = new ArrayList<String>();
        int ml = 0 ;
        for (int i = 0; i < length; i++) {
            if (p.charAt(i) != ' ') {
                //構(gòu)造所有的后綴數(shù)組。
                dic.add(p.substring(i, p.length()));
            }
        }
        String mp = null;
        //對(duì)后綴數(shù)組進(jìn)行排序垫挨。
        quickSortStr(dic, 0, dic.size()-1);
        //打印排序后的數(shù)組用于調(diào)試韩肝。
        for (int i = 0; i < dic.size(); i++) {
            System.out.println("index=" + i + ",data=" + dic.get(i));
        }
        for (int i = 0; i < dic.size()-1; i++) {
            int tl = comLen(dic.get(i), dic.get(i+1));
            if (tl > ml) {
                ml = tl;
                mp = dic.get(i).substring(0, ml);
            }
        }
        return mp;
    } 

    public static void main(String[] args) {
        String source = "Ask not what your country can do for you, but what you can do for your country";
        System.out.println("result = " + longComStr(source, source.length()));
    }
}

運(yùn)行結(jié)果

>> result = can do for you

2.2 求長(zhǎng)度為 N 的字符串的最長(zhǎng)回文子串

問(wèn)題描述

長(zhǎng)度為N的字符串，求這個(gè)字符串里的最長(zhǎng)回文子串九榔，回文字符串 簡(jiǎn)單來(lái)說(shuō)就是一個(gè)字符串正著讀和反著讀是一樣的伞梯。

解決思路

這里用到的是Manacher算法，首先需要對(duì)原始的字符串進(jìn)行預(yù)處理帚屉，即在每個(gè)字符之間加上一個(gè)標(biāo)志位，這里用#來(lái)表示漾峡，這會(huì)使得對(duì)于任意一個(gè)輸入攻旦，經(jīng)過(guò)處理后的字符串長(zhǎng)度為2*len+1，也就是說(shuō) 處理后的字符串始終為奇數(shù)生逸。

在上面我們已經(jīng)介紹過(guò)牢屋，回文串中最左或最右位置的字符與其對(duì)稱軸的距離稱為 回文半徑且预，Manacher定義了一個(gè)數(shù)組RL[i]，它表示 第i個(gè)字符為對(duì)稱軸的回文串 的 最右一個(gè)字符與字符i的閉區(qū)間所包含的字符個(gè)數(shù)烙无，以google為例锋谐，經(jīng)過(guò)處理后的字符串為#g#o#o#g#l#e，那么RL[i]的值為：


而RL[i]-1的值就是原始字符串中截酷，以位置i為對(duì)稱軸的最長(zhǎng)回文串的長(zhǎng)度涮拗，那么接下來(lái)的問(wèn)題就變成如何計(jì)算RL[i]數(shù)組。

首先迂苛，我們需要兩個(gè)輔助的變量maxidR和maxid三热，它表示當(dāng)前計(jì)算的回文字符串中，所能觸及到的最右位置三幻，而maxid則表示該回文串的對(duì)稱軸所在位置就漾，而RL[maxid]為該回文串的距離。

假設(shè)我們此時(shí)遍歷到了第i個(gè)字符念搬，那么這時(shí)候有兩種情況：

(1) i < maxidR

在這種情況下抑堡，我們知道p[maxid+1, .., maxid+RL[maxid]-1]和p[maxid-1, .., maxid-RL[maxid]+1]部分是關(guān)于p[maxid]對(duì)稱的，利用這個(gè)有效信息朗徊，可以避免一些不必要的判斷首妖。

現(xiàn)在，我們獲得i關(guān)于maxid的對(duì)稱點(diǎn)j荣倾，這個(gè)點(diǎn)位于maxid的左側(cè)悯搔，因此，我們已經(jīng)計(jì)算過(guò)以它為中心的回文字符串長(zhǎng)度RL[j]舌仍，對(duì)于以p[j]為中心的回文字符串有兩種情況：

  • 以j為中心的回文字符的最左邊j-(RL[j]-1) 大于等于 maxidR關(guān)于maxid的對(duì)稱點(diǎn)maxid-(maxidR-maxid)妒貌，在這種情況下，我們可以推斷出以i為對(duì)稱點(diǎn)的RL[i]的值最小為RL[j]铸豁。
  • 大于的情況灌曙，可以保證以i為對(duì)稱點(diǎn)的RL[i]至少為(maxidR-i)+1。

當(dāng)然這上面只是推測(cè)出的 最小情況节芥，之后仍然要繼續(xù)遍歷來(lái)更新RL[i]的值在刺。

(2) i >= maxidR

這時(shí)候沒(méi)有任何的已知信息，我們只能從i的左右兩邊慢慢遍歷头镊。

實(shí)現(xiàn)代碼

class Untitled {
    
    static int maxSynStr(char ip[], int len) {
        int size = 2*len + 1;
        char a[] = new char[size];
        int RL[] = new int[size];
        int i = 0;
        int n;
        while (i < len) {
            a[(i<<1)+1] = ip[i];
            a[(i<<1)+2] = '#';
            i++;
        }
        a[0] = '#';
        //最遠(yuǎn)字符的中心對(duì)稱點(diǎn)蚣驼。
        int maxid = 0;
        //探索到的最遠(yuǎn)字符。
        int maxidR = 0;
        int ans = 0;
        RL[0] = 1;
        for (i = 1; i < size; i++) {
            //首先推測(cè)出i為中心的最小回文半徑相艇。
            int offset = 0;
            if (i < maxidR) {
                //j是關(guān)于maxid在左邊的對(duì)稱點(diǎn)颖杏。
                int j = maxid-(i-maxid);
                //獲取之前計(jì)算出的以j為中心的回文半徑。
                if (j-(RL[j]-1) >= maxid-(maxidR-maxid)) {
                    offset = RL[j]-1;
                } else {
                    offset = maxidR-maxid;
                } 
            }
            do {
                offset++;
            } while(i-offset >= 0 && i+offset < size && a[i+offset] == a[i-offset]);
            //最后一次是匹配失敗的坛芽，因此要減去1留储。
            offset--;
            //RL[i]的值包括了自己翼抠，因此要加1。
            RL[i] = offset+1;
            //更新當(dāng)前最大的回文半徑获讳。
            if (i+offset > maxidR){
                maxidR = i+offset;
                maxid = i;
            }
            if (RL[i] > ans) {
                ans = RL[i];
            }
        }
        return ans-1;
    } 
    
    public static void main(String[] args) {
        char[] source = "google".toCharArray();
        System.out.println("result=" + maxSynStr(source, 6));
    }
}

運(yùn)行結(jié)果：

>> result=4

2.3 將字符串中的 * 移到前部阴颖，并且不改變非 * 的順序

問(wèn)題描述

將字符串中的*移到前部，并且不改變非*的順序丐膝，例如ab**cd**e*12量愧，處理后為*****abcde12。

解決思路

我們可以將整個(gè)數(shù)組分為兩個(gè)部分：有可能包含*字符的部分和一定不包含*字符的部分尤误。初始時(shí)候侠畔，整個(gè)數(shù)組只有有 有可能包含*字符的部分，那么我們就可以 從后往前 遍歷损晤，每遇到一個(gè)非*的字符就把它放到 一定不包含*字符的部分软棺，由于需要保持非*的順序，因此需要將它插入到該部分的首部尤勋。

實(shí)現(xiàn)代碼

class Untitled {

    static void moveNullCharPos(char p[], int length) {
        if (length > 1) {
            char t;
            char c;
            int lastCharIndex = length;
            //必須要從后向前掃描喘落。
            for(int j = length-1; j >=0 ;j--) {
                if ((c = p[j]) != '*') {
                    lastCharIndex--;
                    t = p[lastCharIndex]; p[lastCharIndex] = p[j]; p[j] = t;
                }
            }
        }
        System.out.println(p);
    }

    public static void main(String[] args) {
        char[] source = "ab**cd**e*12".toCharArray();
        moveNullCharPos(source, source.length);
    }
}

運(yùn)行結(jié)果：

>> *****abcde12

2.4 不開(kāi)辟用于交換的空間，完成字符串的逆序（C++）

問(wèn)題描述

不開(kāi)辟用于交換的空間最冰，完成字符串的逆序瘦棋。

解決思路

這里利用的是 兩次亦或等于本身 的思想。

實(shí)現(xiàn)代碼

#include <iostream>
using namespace std;

void reverWithoutTemp(char *p, int length){
    int i = 0;
    int j = length-1;
    while (i < j) {
        p[i] = p[i]^p[j];  
        //實(shí)際上是p[i]^p[j]^p[j]暖哨，這里的p[i]和p[j]指的是原始數(shù)組中的值赌朋。
        p[j] = p[i]^p[j];  
        //實(shí)際上是(p[i]^(p[i]^p[j]^p[j]))^(p[i]^p[j]^p[j])，這里的p[i]和p[j]指的是原始數(shù)組中的值篇裁。
        p[i] = p[i]^p[j];  
        i++;j--;
    }
    std::cout << p << std::endl;
}

int main() {
    char p[] = "1234566";
    reverWithoutTemp(p, 7);
    return 0;
}

運(yùn)行結(jié)果：

>> 6654321

2.5 最短摘要生成

問(wèn)題描述

給定一段描述w和一組關(guān)鍵字q沛慢，我們從這段描述中找出包含所有關(guān)鍵字的最短字符序列，這個(gè)最短字符序列就稱為 最短摘要：

  • 最短字符序列必須包含所有的關(guān)鍵字
  • 最短字符序列中關(guān)鍵字的順序可以是隨意的

解決思路

假設(shè)我們的輸入序列如下所示达布，其中w表示非關(guān)鍵字的字符串团甲，而q則表示關(guān)鍵字的字符串：

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

這里，我們引入額外的三個(gè)變量pStart黍聂、pEnd和flag數(shù)組躺苦，flag數(shù)組用于統(tǒng)計(jì)pStart和pEnd之間關(guān)鍵字的命中情況。

這里說(shuō)明一下flag數(shù)組的作用产还，flag數(shù)組和關(guān)鍵字p數(shù)組的長(zhǎng)度相同匹厘，每命中一個(gè)關(guān)鍵字，就將flag數(shù)組的對(duì)應(yīng)位置+1脐区，而flagSize只有在每次遇到一個(gè)新的關(guān)鍵字時(shí)才更新愈诚，因此它表示flag數(shù)組中 不重復(fù)的關(guān)鍵字的個(gè)數(shù)。

算法的步驟如下：

  • 第一步：我們將pEnd從w[0]開(kāi)始移動(dòng)，每發(fā)現(xiàn)一個(gè)命中的關(guān)鍵字扰路，就更新flag[]數(shù)組，直到w[pStart,..,pEnd] 包含了所有的關(guān)鍵字倔叼，即w0,w1,w2,w3,q0,w4,w5,q1汗唱。
  • 第二步：開(kāi)始移動(dòng)pStart，這時(shí)候pStart,..,pEnd之間的長(zhǎng)度將會(huì)逐漸變短丈攒，在移動(dòng)的過(guò)程中哩罪，同時(shí)更新flag[]數(shù)組，直到pStart,...,pEnd之間 不再包含所有的關(guān)鍵字巡验，這時(shí)候就可以求得 目前為止的最短摘要長(zhǎng)度际插，即q0,w4,w5,q1。
  • 第三步：重復(fù)第一步的操作显设，移動(dòng)pEnd使得pStart,...,pEnd重新 包含所有的關(guān)鍵字框弛，再執(zhí)行第二步的操作來(lái) 更新最短摘要長(zhǎng)度，直到pEnd遍歷到w的最后一個(gè)元素捕捂。

實(shí)現(xiàn)代碼

class Untitled {

    static int findKey(String[] p1, String p2) {
        int len = p1.length;
        for(int i = 0; i < len; i++) {
            if(p1[i].equals(p2))
                return i;
        }
        return -1;
    }
    
    //p1為原始數(shù)據(jù)瑟枫，p2為所有的關(guān)鍵詞。
    static int calMinAbst(String[] p1, String[] p2) {
        int p1Len = p1.length;
        int p2Len = p2.length;
        int r;
        int shortAbs = Integer.MAX_VALUE;
        int tAbs = 0;
        int pBegin = 0;
        int pEnd = 0;
        int absBegin = 0;
        int absEnd = 0;
        int flagSize = 0;
        int flag[] = new int[p2Len];
        //初始化標(biāo)志位數(shù)組指攒。
        for (int i = 0; i < p2Len; i++) {
            flag[i] = 0;
        }
        while (pEnd < p1Len) {
            //只有先找到全部的關(guān)鍵詞才退出循環(huán)慷妙。
            while (flagSize != p2Len && pEnd < p1Len) {
                r = findKey(p2, p1[pEnd++]);
                if (r != -1) {
                    if (flag[r] == 0) {
                        flagSize++;
                    }
                    flag[r]++;
                }
            }
            while (flagSize == p2Len) {
                if ((tAbs = pEnd-pBegin) < shortAbs) {
                    shortAbs = tAbs;
                    absBegin = pBegin;
                    absEnd = pEnd-1;
                }
                r = findKey(p2, p1[pBegin++]);
                if (r != -1) {
                    flag[r]--;
                    if (flag[r] == 0) {
                        flagSize--;
                    }
                }
            }
        }
        for (int i = absBegin; i <= absEnd; i++) {
            System.out.print(p1[i] + ",");
        }
        System.out.println("\n最短摘要長(zhǎng)度=" + tAbs);
        return shortAbs;
    }

    public static void main(String[] args) {
        String keyword[] = {"微軟", "計(jì)算機(jī)", "亞洲"};
        String str[] = { 
            "微軟","亞洲","研究院","成立","于","1998","年","，","我們","的","使命",
            "是","使","未來(lái)","的","計(jì)算機(jī)","能夠","看","允悦、","聽(tīng)","膝擂、","學(xué)","，",
            "能","用","自然語(yǔ)言","與","人類","進(jìn)行","交流","隙弛。","在","此","基礎(chǔ)","上",
            "架馋，","微軟","亞洲","研究院","還","將","促進(jìn)","計(jì)算機(jī)","在","亞太","地區(qū)",
            "的","普及","，","改善","亞太","用戶","的","計(jì)算","體驗(yàn)","驶鹉。","”"
        };
        calMinAbst(str, keyword);
    }
}

運(yùn)行結(jié)果

>> 微軟,亞洲,研究院,還,將,促進(jìn),計(jì)算機(jī),
>> 最短摘要長(zhǎng)度=7

2.6 最長(zhǎng)公共子序列

問(wèn)題描述

經(jīng)典的LCS問(wèn)題绩蜻，這里主要解釋一下最長(zhǎng)公共子序列的含義。最長(zhǎng)公共子串和最長(zhǎng)公共子序列的區(qū)別：子串是 串的一個(gè)連續(xù)的部分室埋，子序列則是 不改變序列的順序办绝，而從序列中去掉任意的元素 而獲得的新序列。

解決思路

經(jīng)典的LCS問(wèn)題姚淆，原理可以參考這篇被廣泛轉(zhuǎn)載的文章 程序員編程藝術(shù)第十一章：最長(zhǎng)公共子序列問(wèn)題孕蝉，這里給出簡(jiǎn)要介紹一下基本的思想。

LCS基于下面這個(gè)定理：

LCS 算法定理

最終目的是構(gòu)建類似于下面的一個(gè)矩陣：

LCS 矩陣
  • 對(duì)于矩陣腌逢，定義c[i][j]：它表示字符串序列A的前i個(gè)字符組成的序列A和字符串序列B的前j個(gè)字符組成的序列B之間的最長(zhǎng)公共子序列的長(zhǎng)度降淮，其中i<=A.len，并且j<=B.len。
  • 如果A[i]=B[j]佳鳖，那么A與B之間的最長(zhǎng)公共子序列的最后一項(xiàng)一定是這個(gè)元素霍殴，也就是c[i][j] = c[i-1][j-1]+1。
  • 如果A[i]!=B[j]系吩，則c[i][j]= max(c[i-1][j], c[i][j-1])来庭。
  • 初始值為：c[0][j]=c[i][0]=0。

代碼實(shí)現(xiàn)

class Untitled {

    static void LCS(char a[], int aLen, char b[], int bLen){
        int c[][] = new int[bLen+1][aLen+1];
        for (int i = 1; i < bLen+1; i++) {
            for (int j = 1; j < aLen+1; j++) {
                if (a[j-1] == b[i-1]) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = (c[i-1][j]>c[i][j-1]) ? c[i-1][j]:c[i][j-1];
                }
            }
        }
        int csl = c[bLen][aLen];
        char p[] = new char[csl+1];
        int i = bLen, j = aLen;
        while (i > 0 && j > 0 && c[i][j] > 0) {
            if (c[i][j] == c[i-1][j]) {
                i--;
            } else if(c[i][j] == c[i][j-1]) {
                j--;
            } else if(c[i][j] > c[i-1][j-1]) {
                p[c[i][j]] = a[j-1];
                i--;j--;
            }
        }
        for (i = 1; i <= csl; i++) {
            System.out.print(p[i]);
        }
    } 

    public static void main(String[] args) {
        char p1[] = "aadaae".toCharArray();
        char p2[] = "adaaf".toCharArray();
        LCS(p1, p1.length, p2, p2.length);
    }
}

運(yùn)行結(jié)果

>> adaa

更多文章穿挨，歡迎訪問(wèn)我的 Android 知識(shí)梳理系列：

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末月弛，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子科盛，更是在濱河造成了極大的恐慌帽衙，老刑警劉巖，帶你破解...
    沈念sama閱讀 217,542評(píng)論 6贊 504
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件贞绵，死亡現(xiàn)場(chǎng)離奇詭異厉萝，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)但壮，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評(píng)論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門冀泻，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人蜡饵，你說(shuō)我怎么就攤上這事弹渔。” “怎么了溯祸？”我有些...
    開(kāi)封第一講書人閱讀 163,912評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵肢专，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我焦辅，道長(zhǎng)博杖，這世上最難降的妖魔是什么？ 我笑而不...
    開(kāi)封第一講書人閱讀 58,449評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任筷登，我火速辦了婚禮剃根，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘前方。我一直安慰自己狈醉，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,500評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布惠险。 她就那樣靜靜地躺著苗傅，像睡著了一般。 火紅的嫁衣襯著肌膚如雪班巩。 梳的紋絲不亂的頭發(fā)上渣慕，一...
    開(kāi)封第一講書人閱讀 51,370評(píng)論 1贊 302
  • 城市分裂傳說(shuō)
    那天，我揣著相機(jī)與錄音，去河邊找鬼逊桦。 笑死眨猎，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的强经。 我是一名探鬼主播宵呛，決...
    沈念sama閱讀 40,193評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼夕凝！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起户秤，我...
    開(kāi)封第一講書人閱讀 39,074評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤码秉，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后鸡号，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體转砖，經(jīng)...
    沈念sama閱讀 45,505評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,722評(píng)論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年鲸伴，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了府蔗。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,841評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡汞窗，死狀恐怖姓赤，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情仲吏，我是刑警寧澤不铆，帶...
    沈念sama閱讀 35,569評(píng)論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站裹唆，受9級(jí)特大地震影響誓斥，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜许帐，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,168評(píng)論 3贊 328
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一劳坑、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧成畦，春花似錦距芬、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 31,783評(píng)論 0贊 22
  • 一樁弒父案蔑穴，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至惧浴，卻和暖如春存和，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 32,918評(píng)論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工捐腿， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留纵朋，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,962評(píng)論 2贊 370
  • 代替公主和親
    正文 我出身青樓茄袖，卻偏偏與公主長(zhǎng)得像操软，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子宪祥，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,781評(píng)論 2贊 354

推薦閱讀更多精彩內(nèi)容

  • 最長(zhǎng)回文子串——Manacher 算法 1. 問(wèn)題定義 最長(zhǎng)回文字符串問(wèn)題:給定一個(gè)字符串聂薪，求它的最長(zhǎng)回文子串長(zhǎng)度...
    林大鵬閱讀 2,768評(píng)論 0贊 6
  • 這次要記錄的是一個(gè)經(jīng)典的字符串的題目，也是一個(gè)經(jīng)典的馬拉車算法的實(shí)踐蝗羊。相信在很多地方都會(huì)考到或者問(wèn)到這道題目藏澳，這道...
    檸檬烏冬面閱讀 2,909評(píng)論 0贊 9
  • 上一篇KMP算法之后好幾天都沒(méi)有更新，今天介紹最長(zhǎng)回文子串耀找。 首先介紹一下什么叫回文串翔悠，就是正著讀和倒著讀的字符順...
    zero_sr閱讀 2,295評(píng)論 2贊 8
  • 回溯算法 回溯法：也稱為試探法，它并不考慮問(wèn)題規(guī)模的大小野芒，而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案蓄愁，并...
    fredal閱讀 13,657評(píng)論 0贊 89
  • 最長(zhǎng)回文串問(wèn)題是一個(gè)經(jīng)典的算法題。 0. 問(wèn)題定義 最長(zhǎng)回文子串問(wèn)題：給定一個(gè)字符串狞悲，求它的最長(zhǎng)回文子串長(zhǎng)度撮抓。如果...
    曾會(huì)玩閱讀 4,021評(píng)論 2贊 25