從廣義上來(lái)講：數(shù)據(jù)結(jié)構(gòu)就是一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ， 算法就是操作數(shù)據(jù)的方法

數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法是要作用在特定的數(shù)據(jù)結(jié)構(gòu)上的。

10個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹、堆、跳表、圖、Trie樹

10個(gè)最常用的算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、字符串匹配算法

本文總結(jié)了20個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)和算法，不管是應(yīng)付面試還是工作需要，只要集中精力攻克這20個(gè)知識(shí)點(diǎn)就足夠了。

數(shù)據(jù)結(jié)構(gòu)和算法（一）：復(fù)雜度、數(shù)組、鏈表、棧、隊(duì)列的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（二）：遞歸、排序、通用排序算法的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（三）：二分查找、跳表、散列表、哈希算法的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（四）：二叉樹、紅黑樹、遞歸樹、堆和堆排序、堆的應(yīng)用的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（五）：圖、深度優(yōu)先搜索和廣度優(yōu)先搜索、字符串匹配算法、Trie樹、AC自動(dòng)機(jī)的傳送門

數(shù)據(jù)結(jié)構(gòu)和算法（六）：貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、拓?fù)渑判虻膫魉烷T

第二十一章 圖

首先呢，先思考一個(gè)問題，如何存儲(chǔ)微博、微信等社交網(wǎng)絡(luò)中的好友關(guān)系呢？

一、什么是圖？及圖中的幾個(gè)基礎(chǔ)概念

• 1. 圖跟前邊講的樹一樣，也是一種非線性表結(jié)構(gòu)，比樹更加復(fù)雜，樹中的元素我們稱之為節(jié)點(diǎn)，圖中的元素就稱之為頂點(diǎn)，從下圖可以看出，圖的頂點(diǎn)可以與任意頂點(diǎn)建立關(guān)系，我們把這種關(guān)系稱之為邊（edge）。
     
     圖中的頂點(diǎn)和邊
• 2. 我們可以把微信的好友關(guān)系看做一張圖，其中每個(gè)用戶都可以看做一個(gè)頂點(diǎn)，用戶之間的好友關(guān)系就可以看做邊，每個(gè)用戶有多少好友，就叫做頂點(diǎn)的度，度就是跟頂點(diǎn)相連接的邊的條數(shù)。
• 3. 微博中允許單向關(guān)注，也就是用戶A關(guān)注了用戶B，但是用戶B沒有關(guān)注用戶A，我們就可以用有向圖，來(lái)表示這種關(guān)系，如下圖所示，我們把有方向的圖叫做有向圖，沒有方向的圖叫做無(wú)向圖。
     
     有向圖
• 4. 在圖中，我們把一個(gè)頂點(diǎn)有多少條邊叫做度，如果圖有方向，就把指向頂點(diǎn)的邊數(shù)叫做入度，從這個(gè)頂點(diǎn)指出去的邊叫做出度，如下圖所示。對(duì)應(yīng)到微博的例子，入度就表示有多少粉絲，出度就表示關(guān)注了多少人。
     
     度、入度、出度
• 5. QQ中不但記錄了好友關(guān)系，還記錄了親密度，這種帶親密度的好友關(guān)系，我們可以用帶權(quán)圖來(lái)表示，如下圖，每條邊都有一個(gè)權(quán)重(weight)，可以通過這個(gè)權(quán)重來(lái)表示QQ中的親密度。
     
     帶權(quán)圖

二、如何在內(nèi)存中存儲(chǔ)圖？

方法一：鄰接矩陣法

• 1. 用連續(xù)的內(nèi)存空間存儲(chǔ)圖的方法叫做領(lǐng)接矩陣（Adjacency Matrix），鄰接矩陣的底層是二維數(shù)組，對(duì)無(wú)向圖來(lái)說(shuō)，如果頂點(diǎn)i和頂點(diǎn)j之間有邊，我們就將A[i][j]和A[j][i]標(biāo)記為1；對(duì)于有向圖來(lái)說(shuō)，如果頂點(diǎn)i和頂點(diǎn)j之間只有一條從頂點(diǎn)i指向頂點(diǎn)j的邊，就只將A[i][j]標(biāo)記為1；對(duì)于帶權(quán)圖來(lái)說(shuō)，數(shù)組中存放的是響應(yīng)的權(quán)重。如下圖所示：
     
     鄰接矩陣存儲(chǔ)法.png
• 2. 用鄰接矩陣存儲(chǔ)圖，雖然簡(jiǎn)單直觀，但是比較浪費(fèi)內(nèi)存空間。例如在無(wú)向圖中，如果A[i][j]等于1，那么A[j][i]也一定等于1，我們存儲(chǔ)一個(gè)其實(shí)就夠了，從對(duì)角線一份為二，我們只需要存儲(chǔ)一半就夠了，另一半就浪費(fèi)了。如下圖：
     
     用鄰接矩陣存儲(chǔ)無(wú)向圖有點(diǎn)浪費(fèi)

• 3. 用鄰接矩陣的方法存儲(chǔ)圖，相當(dāng)于給所有的頂點(diǎn)之間的關(guān)系都預(yù)留的內(nèi)存，但是如果我們是稀疏圖，也就是說(shuō)，頂點(diǎn)很多，但是每個(gè)頂點(diǎn)的邊并不多的時(shí)候，用鄰接矩陣就更加浪費(fèi)了，例如，微信有好幾個(gè)億的用戶，但是每個(gè)用戶的好友并不多，一般也就幾百個(gè)，對(duì)應(yīng)在圖中，就是好幾億個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)就幾百個(gè)邊，用鄰接矩陣來(lái)存儲(chǔ)的話，絕大部分的空間都被浪費(fèi)了。
• 4. 也不是說(shuō)鄰接矩陣存儲(chǔ)法完全沒有優(yōu)點(diǎn)，首先，鄰接矩陣存儲(chǔ)方式簡(jiǎn)單、直觀，基于數(shù)組，獲取頂點(diǎn)之間的關(guān)系非常高效；其次，計(jì)算方便，很多圖的運(yùn)算可以轉(zhuǎn)換成矩陣之間的運(yùn)算，例如求解最短路徑問題，就是利用矩陣循環(huán)相乘若干次得到結(jié)果。

方法二：鄰接表存儲(chǔ)法

• 1. 鄰接表的每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表，鏈表中存儲(chǔ)的是與此頂點(diǎn)有關(guān)系的其他頂點(diǎn)，如下圖，就是一個(gè)有向圖用鄰接表法存儲(chǔ)的直觀展示。

     
     
     有向圖用鄰接表存儲(chǔ)
• 2. 相比于鄰接矩陣存儲(chǔ)，鄰接表存儲(chǔ)更節(jié)省內(nèi)存，但是使用起來(lái)比較耗時(shí)，例如，想知道頂點(diǎn)2與頂點(diǎn)4之間是否存在關(guān)系，就需要遍歷頂點(diǎn)2所對(duì)應(yīng)的的鏈表。我們也可以仿照前邊處理散列沖突的方式，來(lái)處理遍歷鏈表所帶來(lái)的的耗時(shí)問題，將鏈表替換成跳表或者紅黑樹，這樣查找的時(shí)間復(fù)雜度就從O(n)變成了O(logn)了。

三、如何在存儲(chǔ)微博中的社交關(guān)系呢？

• 1. 社交網(wǎng)絡(luò)是一個(gè)稀疏圖，用鄰接矩陣法存儲(chǔ)比較浪費(fèi)時(shí)間，所以應(yīng)該采用鄰接表法來(lái)存儲(chǔ)，但是用一個(gè)鄰接表只能表示用戶關(guān)注了誰(shuí)，無(wú)法知道粉絲列表，所以我們還需要一個(gè)逆鄰接表，來(lái)存放粉絲，也就是存放指向這個(gè)定向的邊，如下圖：

     
     
     鄰接表和逆鄰接表
• 2. 用鏈表的話時(shí)間復(fù)雜度是O(n)，所以我們應(yīng)該將鏈表替換成跳表或者紅黑樹等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，由于微博中需要按照用戶首字母排序，所以我們可以使用跳表，跳表的插入、查找、刪除的時(shí)間復(fù)雜度都是O(logn)非常高效，同時(shí)跳表中的數(shù)據(jù)都是有序的，分頁(yè)獲取粉絲列表或者關(guān)注列表也很高效。

• 3. 微博擁有好幾億的用戶，一臺(tái)機(jī)器的內(nèi)存肯定是不夠的，我們可以用過哈希算法進(jìn)行數(shù)據(jù)分片，將鄰接表存放到不同機(jī)器上?？梢赃@樣處理：對(duì)數(shù)據(jù)進(jìn)行哈希得到哈希值，再用這個(gè)哈希值和機(jī)器總數(shù)取模，得到機(jī)器編號(hào)，將這個(gè)數(shù)據(jù)的鄰接表放到這臺(tái)機(jī)器上就可以了。

     
     
     用哈希算法進(jìn)行數(shù)據(jù)分片
• 4. 我們還可以利用外部存儲(chǔ)來(lái)持久化存儲(chǔ)數(shù)據(jù)，例如使用數(shù)據(jù)庫(kù)，并建立多級(jí)索引。

第二十二章 深度優(yōu)先搜索和廣度優(yōu)先搜索

一、什么是搜索算法

• 1. 算法是作用在具體數(shù)據(jù)結(jié)構(gòu)上的，深度優(yōu)先搜索和廣度優(yōu)先搜索算法都是作用于圖這種數(shù)據(jù)結(jié)構(gòu)上的，這是因?yàn)閳D的表達(dá)能力很強(qiáng)，大部分涉及搜索的場(chǎng)景都可以抽象成“圖”。
• 2. 圖的搜索算法，其實(shí)在圖上找出從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑，今天介紹兩種最簡(jiǎn)單、最暴力的搜索算法：廣度優(yōu)先搜索（Breadth-First-Search）和深度優(yōu)先搜索（Depth-First-Search）

二、BFS-廣度優(yōu)先搜索（Breadth-First-Search）

• 1. 廣度優(yōu)先搜索，其實(shí)就是地毯式的層層遞進(jìn)策略，即先查找最近的頂點(diǎn)，再找次近的，依次往外搜索，如下圖：

     
     
     廣度優(yōu)先搜索
• 2. 用Swift代碼實(shí)現(xiàn)，如下

//單鏈表
class SingleLinkedList{
    var headNode: SingleLinkedNode?
    var nodeMap: Dictionary<String, SingleLinkedNode>?
    var nodeCount: Int = 0
    
    //插入一個(gè)節(jié)點(diǎn)
    func insertNode(node: SingleLinkedNode){
        nodeMap?.updateValue(node, forKey: node.key)
        nodeCount = nodeCount + 1
        if headNode == nil{
            headNode = node
        }else{
            lastNode().next = node
        }
    }
    
    //獲取一個(gè)節(jié)點(diǎn)
    func lastNode() -> SingleLinkedNode{
        var node = headNode
        while node?.next != nil {
            node = node?.next
        }
        if node != nil{
            return node!
        }else{
            return SingleLinkedNode(key: "error", value: "error")
        }
    }
    
    //根據(jù)key獲取節(jié)點(diǎn)
    func getNode(key: String) -> SingleLinkedNode?{
        return nodeMap?[key]
    }
    
    //刪除node的下一個(gè)節(jié)點(diǎn)
    func deleteNode(_ node: SingleLinkedNode){
        if (nodeMap?[node.key] ?? SingleLinkedNode(key: "", value: "")) == node{
            nodeCount = nodeCount - 1
            node.next = node.next?.next
        }else{
            print("該節(jié)點(diǎn)不存在")
        }
    }
    
    func size() -> Int{
        return nodeCount
    }
}

//單鏈表的節(jié)點(diǎn)
class SingleLinkedNode: Equatable{
    static func == (lhs: SingleLinkedNode, rhs: SingleLinkedNode) -> Bool {
        if lhs.key == rhs.key && lhs.value == rhs.value && lhs.next == rhs.next{
            return true
        }
        return false
    }
    
    var key:String = "-1"
    var value: String?
    var next: SingleLinkedNode?
    init(key: String,value: String) {
        self.key = key
        self.value = value
    }
}

//先入先出的順序隊(duì)列
class Queue<T>{
    private var array: Array<T> = Array()
    //入隊(duì)
    func enqueue(_ e: T){
        array.append(e)
    }
    //出隊(duì)
    func dequeue() -> T?{
        if let first = array.first{
            array.remove(at: 0)
            return first
        }
        return nil
    }
    
    func size() -> Int{
        return array.count;
    }
}

let queue = Queue<Int>()
queue.enqueue(11)
queue.enqueue(2)
queue.enqueue(333)
let testQueue1 = queue.dequeue()
let testQueue2 = queue.dequeue()
let testQueue3 = queue.dequeue()

//無(wú)向圖
class Graph{
    private var peakCount: Int = 0                          //頂點(diǎn)的個(gè)數(shù)
    private var linkedArray = Array<SingleLinkedList>()     //單鏈表的數(shù)組
    
    //初始化
    init(peakCount: Int) {
        self.peakCount = peakCount
        let linkedList = SingleLinkedList()
        self.linkedArray = Array(repeating: linkedList, count: self.peakCount)
    }
    
    //增加一條邊（無(wú)向圖一條邊需要存兩次）
    func addEdge(s: Int,t: Int){
        let nodeT = SingleLinkedNode(key:"\(t)" ,value: "\(t)")
        let nodeS = SingleLinkedNode(key: "\(s)", value: "\(s)")
        linkedArray[s].insertNode(node: nodeT)
        linkedArray[t].insertNode(node: nodeS)
    }
    
    // 廣度優(yōu)先搜索 從頂點(diǎn)開始 尋找到t頂點(diǎn)的路徑 打印出來(lái)
    func bfs(start_s: Int,target_t: Int){
        //如果起點(diǎn)等于重點(diǎn) 直接return
        if start_s == target_t {
            return
        }
        //已經(jīng)訪問過的頂點(diǎn)
        var visited = Array<Bool>()
        //先入先出的隊(duì)列，負(fù)責(zé)存儲(chǔ)已經(jīng)被訪問過但其相連的頂點(diǎn)還沒有訪問的頂點(diǎn)
        let queue = Queue<Int>()
        //將第一個(gè)頂點(diǎn)s加入隊(duì)列
        queue.enqueue(start_s)
        //記錄搜索路徑
        var recordSearchPath = Array(repeating: -1, count: peakCount)
        while(queue.size() != 0){
            //當(dāng)前頂點(diǎn)
            let currentPeak = queue.dequeue() ?? 0
            for i in 0..<linkedArray[currentPeak].size(){
                //當(dāng)前頂點(diǎn)所對(duì)應(yīng)的的節(jié)點(diǎn)
                let currentNode = linkedArray[currentPeak].getNode(key: "\(i)")
                //當(dāng)前節(jié)點(diǎn)的位置
                let currentSub = Int(currentNode?.key ?? "0") ?? 0
                if !visited[currentSub]{
                    recordSearchPath[currentSub] = currentPeak
                    if currentSub == target_t{
                        print("找到了")
                        return
                    }
                    visited[currentSub] = true
                    queue.enqueue(currentSub)
                }
            }
        }
    }
}

• 3. 廣度優(yōu)先搜索最壞情況下，終止頂點(diǎn)t與起始頂點(diǎn)s相距很遠(yuǎn)，需要遍歷整個(gè)圖才能找到，每個(gè)頂點(diǎn)都要進(jìn)隊(duì)列一次，每條邊也都要被訪問一次，所以廣度優(yōu)先搜索的時(shí)間復(fù)雜度是O(V+E)，V代表頂點(diǎn)數(shù)量，E代表邊的數(shù)量；對(duì)于一個(gè)連通圖來(lái)說(shuō)，圖中的所有頂點(diǎn)都是連通的，E肯定大于等于V-1，所以廣度優(yōu)先搜索的時(shí)間復(fù)雜度也可以簡(jiǎn)寫為O(E)，E代表邊數(shù)。
• 4. 廣度優(yōu)先搜索的空間消耗主要在幾個(gè)輔助變量上，輔助變量的存儲(chǔ)空間的大小不過超過頂點(diǎn)的個(gè)數(shù)，所以空間復(fù)雜度是O(V)，V代表頂點(diǎn)數(shù)。

三、DFS-深度優(yōu)先搜索（Depth-First-Search）

• 1. 深度優(yōu)先搜索，其實(shí)就是走迷宮，你站在岔路口上，選擇一條路往下走，走著走著發(fā)現(xiàn)走不通了，就退回到上一個(gè)岔路口，重新選擇一條路繼續(xù)走，按照這種策略，一直走下去，直到找到出口為止。如下圖：

     
     
     深度優(yōu)先搜索策略
• 2. 用Swift代碼實(shí)現(xiàn)，如下
• 3. 從上圖中可以看出，按照深度優(yōu)先搜索策略，每條邊最多會(huì)被訪問2次，一次是遍歷，一次是回退，所以深度優(yōu)先搜索的時(shí)間復(fù)雜度是O(E)，E代表邊數(shù)
• 4. 從代碼可以看出，深度優(yōu)先搜索的內(nèi)存消耗跟頂點(diǎn)的個(gè)數(shù)成正比，所以空間復(fù)雜度為O(V)，V代表頂點(diǎn)數(shù)。

第二十三章 字符串匹配基礎(chǔ)

字符串匹配算法分為單模式串匹配和多模式串匹配。單模式匹配，即一個(gè)串和另一個(gè)串進(jìn)行匹配，例如：BF算法、RK算法、BM算法、KMP算法；也有多模式串匹配，即在一個(gè)串中同時(shí)查找多個(gè)串，例如：Tire樹。

一、BF算法

• 1. BF算法的BF是Brute Force的縮寫，中文叫做暴力匹配算法，從名字就可以看出，這種算法簡(jiǎn)單、暴力、好懂，相應(yīng)的性能也不高。
• 2. 這里有兩個(gè)概念必須先弄懂：主串和模式串，我們?cè)谧址瓵中查找字符串B，A就是主串，B就是模式串。我們把主串的長(zhǎng)度記為n，模式串長(zhǎng)度記為m，因?yàn)樵谥鞔胁檎夷Ｊ酱?，主串肯定比模式串長(zhǎng)，n>m.
• 3. BF的核心思想是：在主串中，檢查起始位置分別是0、1、2...n-m且長(zhǎng)度為m的n-m+1個(gè)子串，看有沒有和模式串匹配的。例如下圖所示
     
     BF核心思想.png
• 4. 極端情況下，BF需要匹配n-m+1次，每次匹配m個(gè)字符，所以最壞時(shí)間復(fù)雜度為O(n*m)

二、RK算法

• 1. RK算法的全稱是Rabin-Karp算法，是BF算法的升級(jí)版，RK算法在BF算法的基礎(chǔ)上，引入了哈希算法，降低了時(shí)間復(fù)雜度。
• 2. RK算法的思想是這樣的：我們通過哈希算法對(duì)主串中的n-m+1個(gè)子串求哈希值，然后逐個(gè)與模式串的哈希值比較，如果相同就證明匹配成功了。（如果出現(xiàn)哈希沖突，可以將哈希值相同的兩個(gè)串，在進(jìn)行一次逐個(gè)字符的比較）
• 3. 整個(gè)RK算法可以分為兩部分：計(jì)算子串的哈希值、模式串的哈希值與子串哈希值進(jìn)行比較。我們可以通過設(shè)計(jì)巧妙的哈希算法，使得掃描一次主串就可以得到所有子串的哈希值，這部分的時(shí)間復(fù)雜度為O(n)；哈希值之間的比較的時(shí)間復(fù)雜度是O(1)，需要比較n-m+1次，所以這部分的時(shí)間復(fù)雜度也是O(n)，所以整體RK算法的時(shí)間復(fù)雜度是O(n)。

三、BM算法

• 1. BM算法是一種非常高效的字符串匹配算法，其性能是著名的KMP算法的3~4倍。

• 2. 前邊講的匹配算法都是像下圖一樣，將模式串一位一位的往前移動(dòng)，與主串的子串進(jìn)行一次一次的對(duì)比進(jìn)行查找的，而BM算法就第二個(gè)圖一樣，為了提高查找效率，找出了移動(dòng)規(guī)律，按照規(guī)律跳著往后移動(dòng)，例如：發(fā)現(xiàn)c與d不匹配了，就將模式串往后移動(dòng)三位。

     
     
     模式串一位一位往后移動(dòng)
     
     
     BM找到了移動(dòng)規(guī)律，可以移動(dòng)多位

• 3. BM算法發(fā)現(xiàn)移動(dòng)規(guī)律有兩個(gè)：壞字符規(guī)則和好后綴規(guī)則
• 4. 壞字符規(guī)則
  • (1). 我們從模式串的末尾往前倒著匹配，當(dāng)我們發(fā)現(xiàn)某個(gè)字符沒法匹配時(shí)，我們就把這個(gè)字符叫做壞字符。
    
    壞字符.png
  • (2). 如果壞字符在模式串中存在，那么我們就把懷字符對(duì)應(yīng)的模式串中的這個(gè)字符的下標(biāo)記做xi，如果懷字符在模式串中不存在，我們就把xi記作-1；我們把懷字符對(duì)應(yīng)在模式串中的字符的下標(biāo)記做si；規(guī)律就是：模式串往后移動(dòng)的位置就等于si-xi。如下圖所示：
    
    壞字符規(guī)則移動(dòng)位數(shù)
• 5. 好后綴規(guī)則

  • (1). 我們把主串中和模式串相匹配的字符，稱之為好后綴，如下圖：

    
    
    好后綴
  • (2). 我們把好后綴bc記做{u}，拿{u}在模式串中查找，如果找到了另一個(gè)跟{u}相匹配的子串{u*}，我們就將模式串滑動(dòng)到子串{u*}跟主串中{u}對(duì)齊的位置，如下圖:
    
    找到與好后綴相同的子串，則滑動(dòng)對(duì)齊
  • (3). 如果在模式串中找不到另一個(gè)與{u}相匹配的子串，我們還得考察好后綴的后綴子串，是否存在跟模式串的前綴子串相匹配。如果好后綴的后綴子串跟模式串的前綴子串相匹配，則將模式串滑動(dòng)到對(duì)齊的位置，如下圖：
    
    滑動(dòng)模式串到圖中位置
  • (4). 如果好后綴的后綴子串與模式串的前綴子串不匹配，則直接將模式串滑動(dòng)到主串的好后綴{u}的后面，如下圖：
    
    {u}代表好后綴
• 6. 當(dāng)模式串和主串中的某個(gè)字符不匹配時(shí)，我們?cè)撊绾芜x擇使用壞字符規(guī)則還是好后綴規(guī)則呢？我們可以分別計(jì)算壞字符規(guī)則和好后綴規(guī)則往后移動(dòng)的位數(shù)，然后取兩個(gè)數(shù)最大的，作為模式串往后移動(dòng)的位數(shù)。

第二十四章 Trie樹

一、什么是Trie樹

• 1. Trie樹，也叫字典樹，顧名思義，是一種樹形結(jié)構(gòu)，專門用來(lái)處理字符串匹配，經(jīng)常用來(lái)解決在一組字符串集合中快速查找某個(gè)字符串的問題。

• 2. Trie樹的本質(zhì)就是，利用字符串之間的公共前綴，將重復(fù)的前綴組合在一起，就像下圖一樣：

     
     
     Trie樹

• 3. 利用how、hi、her、hello、so、see等字符串構(gòu)造一顆Trie樹，過程如下圖所示：

     
     
     構(gòu)造一顆Tire樹

二、如何實(shí)現(xiàn)一顆Trie樹？

• 1. Trie樹主要有兩個(gè)操作：將字符串集合構(gòu)造成Trie樹、在Trie樹中查找一個(gè)字符串

• 2. Trie樹是一個(gè)多叉樹，可以通過下標(biāo)和字符一一對(duì)應(yīng)的數(shù)組，來(lái)存儲(chǔ)子節(jié)點(diǎn)的指針，如下圖所示：

     
     
     Trie樹的存儲(chǔ)
• 3. 一個(gè)Trie樹的結(jié)點(diǎn)，用代碼可以這么寫：

class TrieNode{
    var data: Character?         //存放一個(gè)字符，例如：“h”
    var childArray: [TrieNode]?  //存放子節(jié)點(diǎn)指針的數(shù)組，例如：存放以h開頭的字符的子節(jié)點(diǎn)的指針
}

• 4. 想在一組字符串中頻繁的查找一個(gè)字符串，使用Trie樹解決就會(huì)非常高效，過程分為構(gòu)建Tire樹和查找該字符串。構(gòu)建Trie樹的過程需要掃描所有字符串，時(shí)間復(fù)雜度是O(n)，n代表所有字符串的長(zhǎng)度之和，一旦構(gòu)建Trie樹成功，后續(xù)查詢就會(huì)非常高效，如果要查詢的字符串長(zhǎng)度為k，那么我們只需要對(duì)比大約k個(gè)節(jié)點(diǎn)，就可以完成操作，時(shí)間復(fù)雜度為O(k)，k表示要查找的字符串的長(zhǎng)度。
• 5. Trie樹比較消耗內(nèi)存，是一種空間換時(shí)間的思路，用數(shù)組存放子節(jié)點(diǎn)的指針，我們知道存放一個(gè)字符需要1個(gè)字節(jié)，而存放26個(gè)字母的指針，需要26*8=208個(gè)字節(jié)，額外占用了208個(gè)字節(jié)，這還只是26個(gè)字母的情況。我們可以將數(shù)組換成有序數(shù)組、跳表、散列表、紅黑樹等數(shù)據(jù)結(jié)構(gòu)，來(lái)節(jié)省內(nèi)存的消耗。

三、Trie樹與散列表、紅黑樹的比較

• 1. 如果想要在一組字符串中精確查找某個(gè)字符串，一般建議使用散列表或者紅黑樹。
• 2. Trie樹的優(yōu)勢(shì)不在于動(dòng)態(tài)集合數(shù)據(jù)的查找，而在于查找前綴匹配的字符串，例如：搜索引擎中的關(guān)鍵詞提示功能、輸入法自動(dòng)補(bǔ)全功能、IDE代碼編輯器自動(dòng)補(bǔ)全功能等。

第二十五章 AC自動(dòng)機(jī)

一、什么是 AC自動(dòng)機(jī)？

二、如何構(gòu)建AC自動(dòng)機(jī)?

三、如何在AC自動(dòng)機(jī)上匹配主串？