數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)

首先看數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)都有哪些，如下圖所示。

隊(duì)列和棧是經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)，需要了解它們的特點(diǎn)。隊(duì)列是先進(jìn)先出，棧是后進(jìn)先出。

表，包括很多種，有占用連續(xù)空間的數(shù)組、用指針鏈接的單向和雙向鏈表，首尾相接的循環(huán)鏈表、以及散列表，也叫哈希表。

圖，在特定領(lǐng)域使用的比較多，例如路由算法中會(huì)經(jīng)常使用到，圖分為有向圖、無(wú)向圖及帶權(quán)圖，這部分需要掌握?qǐng)D的深度遍歷和廣度遍歷算法，了解最短路徑算法。

樹的內(nèi)容，樹一般用作查找與排序的輔助結(jié)構(gòu)，剩下兩個(gè)部分都和樹有關(guān)，一個(gè)是二叉樹，一個(gè)是多叉樹。

多叉樹包括 B 樹族，有 B 樹、B+ 樹、B* 樹，比較適合用來(lái)做文件檢索；另外一個(gè)是字典樹，適合進(jìn)行字符串的多模匹配。

二叉樹包括平衡二叉樹、紅黑樹、哈夫曼樹，以及堆，適合用于進(jìn)行數(shù)據(jù)查找和排序。這部分需要了解二叉樹的構(gòu)建、插入、刪除操作的實(shí)現(xiàn)，需要掌握二叉樹的前序、中序、后序遍歷。

算法知識(shí)點(diǎn)

來(lái)看算法部分的知識(shí)點(diǎn)匯總，如下圖所示。

算法題的常用解題方法。

復(fù)雜度是衡量算法好壞的標(biāo)準(zhǔn)之一，我們需要掌握計(jì)算算法時(shí)間復(fù)雜度和空間復(fù)雜度的方法。計(jì)算時(shí)間復(fù)雜度的方法一般是找到執(zhí)行次數(shù)最多的語(yǔ)句，然后計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，最后用大寫 O 來(lái)表示結(jié)果。

常用的字符串匹配算法，了解不同算法的匹配思路。

排序也是經(jīng)?？疾斓闹R(shí)點(diǎn)，排序算法分為插入、交換、選擇、歸并、基數(shù)五類，其中快速排序和堆排序考察的頻率最高，要重點(diǎn)掌握，需要能夠手寫算法實(shí)現(xiàn)。

常用的查找算法，包括二分查找、二叉排序樹、B 樹、Hash、BloomFilter 等，需要了解它們的適用場(chǎng)景，例如二分查找適合小數(shù)量集內(nèi)存查找，B 樹適合文件索引，Hash 常數(shù)級(jí)的時(shí)間復(fù)雜度更適合對(duì)查找效率要求較高的場(chǎng)合，BloomFilter 適合對(duì)大數(shù)據(jù)集進(jìn)行數(shù)據(jù)存在性過(guò)濾。

詳解二叉搜索樹

二叉搜索樹

如下圖所示，二叉搜索樹滿足這樣的條件，每個(gè)節(jié)點(diǎn)包含一個(gè)值，每個(gè)節(jié)點(diǎn)至多有兩個(gè)子樹。每個(gè)節(jié)點(diǎn)左子樹節(jié)點(diǎn)的值都小于自身的值，每個(gè)節(jié)點(diǎn)右子樹節(jié)點(diǎn)的值都大于自身的值。

二叉樹的查詢時(shí)間復(fù)雜度是 log(N)，但是隨著不斷的插入、刪除節(jié)點(diǎn)，二叉樹的樹高可能會(huì)不斷變大，當(dāng)一個(gè)二叉搜索樹所有節(jié)點(diǎn)都只有左子樹或者都只有右子樹時(shí)，其查找性能就退化成線性的了。

平衡二叉樹

平衡二叉樹可以解決上面這個(gè)問(wèn)題，平衡二叉樹保證每個(gè)節(jié)點(diǎn)左右子樹的高度差的絕對(duì)值不超過(guò) 1，例如 AVL 樹。AVL 樹是嚴(yán)格的平衡二叉樹，插入或刪除數(shù)據(jù)時(shí)可能經(jīng)常需要旋轉(zhuǎn)來(lái)保持平衡，比較適合插入、刪除比較少的場(chǎng)景。

紅黑樹

紅黑樹是一種更加實(shí)用的非嚴(yán)格的平衡二叉樹。紅黑樹更關(guān)注局部平衡而非整體平衡，確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出 2 倍，所以是接近平衡的，但減少了許多不必要的旋轉(zhuǎn)操作，更加實(shí)用。前面提到過(guò)，Java 8 的 HashMap 中就應(yīng)用了紅黑樹來(lái)解決散列沖突時(shí)的查找問(wèn)題。TreeMap 也是通過(guò)紅黑樹來(lái)保證有序性的。

紅黑樹除了擁有二叉搜索樹的特點(diǎn)外，還有以下規(guī)則，如下圖所示。

每個(gè)節(jié)點(diǎn)不是紅色就是黑色。

根節(jié)點(diǎn)是黑色。

每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)，如圖中的黑色三角。

紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的。

任意節(jié)點(diǎn)到其葉節(jié)點(diǎn)的每條路徑上，包含相同數(shù)量的黑色節(jié)點(diǎn)。? ??

詳解?B 樹

B?樹

B 樹是一種多叉樹，也叫多路搜索樹。B 樹中每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素，非常適合用在文件索引上，可以有效減少磁盤 IO 次數(shù)。B 樹中所有結(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)稱為 B 樹的階，如下圖所示是一棵 3 階 B 樹，也叫 2-3 樹。

一個(gè) m 階 B 樹有如下特點(diǎn)：

非葉節(jié)點(diǎn)最多有 m 棵子樹；

根節(jié)點(diǎn)最少有兩個(gè)子樹，非根、非葉節(jié)點(diǎn)最少有 m/2 棵子樹；

非葉子結(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)，等于該節(jié)點(diǎn)子樹個(gè)數(shù)?1，就是說(shuō)一個(gè)節(jié)點(diǎn)如果有 3棵子樹，那么其中必定包含 2 個(gè)關(guān)鍵字；

非葉子節(jié)點(diǎn)中的關(guān)鍵字大小有序，如上圖中左邊的節(jié)點(diǎn)中 37、51 兩個(gè)元素就是有序的；

節(jié)點(diǎn)中每個(gè)關(guān)鍵字的左子樹中的關(guān)鍵字都小于該關(guān)鍵字，右子樹中的關(guān)鍵字都大于該關(guān)鍵字。如上圖中關(guān)鍵字 51 的左子樹有 42、49，都小于 51，右子樹的節(jié)點(diǎn)有 59，大于51；

所有葉節(jié)點(diǎn)都在同一層。

B 樹在查找時(shí)，從根結(jié)點(diǎn)開始，對(duì)結(jié)點(diǎn)內(nèi)的有序的關(guān)鍵字序列進(jìn)行二分查找，如果找到就結(jié)束，沒(méi)有找到就進(jìn)入查詢關(guān)鍵字所屬范圍的子樹進(jìn)行查找，直到葉節(jié)點(diǎn)。

總結(jié)一下：

B 樹的關(guān)鍵字分布在整顆樹中，一個(gè)關(guān)鍵字只出現(xiàn)在一個(gè)節(jié)點(diǎn)中；

搜索可能在非葉節(jié)點(diǎn)停止；

B 樹一般應(yīng)用在文件系統(tǒng)。

B+?樹

下圖是 B 樹的一個(gè)變種，叫作 B+ 樹。

B+ 樹的定義與 B 樹基本相同，除了下面這幾個(gè)特點(diǎn)。

節(jié)點(diǎn)中的關(guān)鍵字與子樹數(shù)目相同，比如節(jié)點(diǎn)中有 3 個(gè)關(guān)鍵字，那么就有 3 棵子樹；

關(guān)鍵字對(duì)應(yīng)的子樹中的節(jié)點(diǎn)都大于或等于關(guān)鍵字，子樹中包括關(guān)鍵字自身；

所有關(guān)鍵字都出現(xiàn)在葉子節(jié)點(diǎn)中；

所有葉子節(jié)點(diǎn)都有指向下一個(gè)葉子節(jié)點(diǎn)的指針。

與 B 樹不同，B+ 樹在搜索時(shí)不會(huì)在非葉子節(jié)點(diǎn)命中，一定會(huì)查詢到葉子節(jié)點(diǎn)；另外一個(gè)，葉子節(jié)點(diǎn)相當(dāng)于數(shù)據(jù)存儲(chǔ)層，保存關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)，而非葉子節(jié)點(diǎn)只保存關(guān)鍵字和指向葉節(jié)點(diǎn)的指針，不保存關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)，所以同樣數(shù)量關(guān)鍵字的非葉節(jié)點(diǎn)，B+ 樹比 B 樹要小很多。

B+ 樹更適合索引系統(tǒng)，MySQL 數(shù)據(jù)庫(kù)的索引就提供了 B+ 樹實(shí)現(xiàn)。原因有三個(gè)：

由于葉節(jié)點(diǎn)之間有指針相連，B+ 樹更適合范圍檢索；

由于非頁(yè)節(jié)點(diǎn)只保存關(guān)鍵字和指針，同樣大小非葉節(jié)點(diǎn)，B+ 樹可以容納更多的關(guān)鍵字，可以降低樹高，查詢時(shí)磁盤讀寫代價(jià)更低；

B+ 樹的查詢效率比較穩(wěn)定。任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路，所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，效率相當(dāng)。

最后可以簡(jiǎn)單了解，還有一種 B* 樹的變種，在 B+ 樹的非葉節(jié)點(diǎn)上，也增加了指向同一層下一個(gè)非葉節(jié)點(diǎn)的指針。

詳解字符串匹配

字符串匹配問(wèn)題

在面試時(shí)，字符串相關(guān)的問(wèn)題經(jīng)常作為算法考察題，下面來(lái)看字符串匹配的問(wèn)題。先來(lái)了解一道?？嫉拿嬖囶}：“判斷給定字符串中的括號(hào)是否匹配”。

一般面試題目的描述都比較簡(jiǎn)單，在解答前，可以跟面試官進(jìn)一步溝通一下題目要求和細(xì)節(jié)。以這道題為例，可以跟面試官確認(rèn)括號(hào)的范圍，是不是只考慮大中小括號(hào)就可以，包不包括尖括號(hào)；對(duì)函數(shù)的入?yún)⒑头祷刂涤袥](méi)有什么樣的要求；需不需要考慮針對(duì)大文件的操作等。

我們假定細(xì)化后本題的要求為：只考慮大中小括號(hào)；不考慮針對(duì)大文件的操作，以字符串作為入?yún)ⅲ祷刂禐椴紶栴愋?；未出現(xiàn)括號(hào)也算作匹配的情況。那么，解題思路如下。

字符匹配問(wèn)題可以考慮使用棧的特性來(lái)處理。

遇到左括號(hào)時(shí)入棧，遇到右括號(hào)時(shí)出棧對(duì)比，看是不是成對(duì)的括號(hào)。

當(dāng)匹配完成時(shí)，如果棧內(nèi)為空說(shuō)明匹配，否則說(shuō)明左括號(hào)多于右括號(hào)。

字符串代碼

來(lái)看實(shí)際的實(shí)現(xiàn)代碼，如下圖所示(巧妙運(yùn)用hahmap把對(duì)應(yīng)括號(hào)用key和value的方式存儲(chǔ))。

按照上面的思路，需要對(duì)字符串進(jìn)行遍歷，所以首先要能確定棧操作的觸發(fā)條件，就是定義好括號(hào)對(duì)，方便入棧和出棧匹配。這里要注意，編碼實(shí)現(xiàn)時(shí)一定要注意編碼風(fēng)格與規(guī)范，例如變量命名必須要有明確意義，不要簡(jiǎn)單使用 a、b 這種沒(méi)有明確意義的變量名。

我們首先定義了 brackets 的 map，key 是所有右括號(hào)，value 是對(duì)應(yīng)的左括號(hào)，這樣定義方便出棧時(shí)對(duì)比括號(hào)是否是成對(duì)。

再看一下匹配函數(shù)的邏輯。這里也要注意，作為工具類函數(shù)，要做好健壯性防御，首先要對(duì)輸入?yún)?shù)進(jìn)行驗(yàn)空。

然后我們定義一個(gè)保存字符類型的棧，開始對(duì)輸入的字符串進(jìn)行遍歷。

如果當(dāng)前字符是 brackets 中的值，也就是左括號(hào)，則入棧。這里要注意，map 的值查詢方法是 O(N) 的，因?yàn)楸绢}中括號(hào)種類很少，才使用這種方式讓代碼更簡(jiǎn)潔一些。如果當(dāng)前字符不是左括號(hào)，在使用 containskey 來(lái)判斷是不是右括號(hào)。如果是右括號(hào)，需要檢驗(yàn)是否匹配，如果棧為空表示右括號(hào)多于左括號(hào)，如果棧不空，但出棧的左括號(hào)不匹配，這兩種情況都說(shuō)明字符串中的括號(hào)是不匹配的。

當(dāng)遍歷完成時(shí)，如果棧中沒(méi)有多余的左括號(hào)，則匹配。

最后強(qiáng)調(diào)一下：編碼題除了編程思路，一定要注意編程風(fēng)格和細(xì)節(jié)點(diǎn)的處理。

字符串解題思路

接下來(lái)，總結(jié)一下字符串匹配類問(wèn)題的解題技巧。

首先要認(rèn)真審題，避免答偏?？梢韵却_定是單模式匹配問(wèn)題還是多模式匹配問(wèn)題，命中條件是否有多個(gè)。

然后確定對(duì)算法時(shí)間復(fù)雜度或者內(nèi)存占用是否有額外要求。

最后要明確期望的返回值是什么，比如存在有多個(gè)命中結(jié)果時(shí)，是返回第一個(gè)命中的，還是全部返回。

關(guān)于解題思路。

如果是單模式匹配問(wèn)題，可以考慮使用 BM 或者 KMP 算法。

如果是多模匹配，可以考慮使用 Tire 樹來(lái)解決。

在實(shí)現(xiàn)匹配算法時(shí)，可以考慮用前綴或者后綴匹配的方式來(lái)進(jìn)行。

最后可以考慮是否能夠通過(guò)棧、二叉樹或者多叉樹等數(shù)據(jù)結(jié)構(gòu)來(lái)輔助解決。

建議了解一下常見(jiàn)的字符串單模、多模匹配算法的處理思路。

詳解?TopK

TopK?問(wèn)題

TopK 問(wèn)題是在實(shí)際業(yè)務(wù)中經(jīng)常出現(xiàn)的典型問(wèn)題，例如微博的熱門排行就屬于 TopK 問(wèn)題。

TopK 一般是要求在 N 個(gè)數(shù)的集合中找到最小或者最大的 K 個(gè)值，通常 N 都非常得大。TopK 可以通過(guò)排序的方式解決，但是時(shí)間復(fù)雜度較高，一般是 O(nk)，這里我們來(lái)看看更加高效的方法。

如下圖所示，首先取前 K 個(gè)元素建立一個(gè)大根堆，然后對(duì)剩下的 N-K 個(gè)元素進(jìn)行遍歷，如果小于堆頂?shù)脑?，則替換掉堆頂元素，然后調(diào)整堆。當(dāng)全部遍歷完成時(shí)，堆中的 K 個(gè)元素就是最小的 K 個(gè)值。

這個(gè)算法的時(shí)間復(fù)雜度是 N*logK。算法的優(yōu)點(diǎn)是不用在內(nèi)存中讀入全部的元素，能夠適用于非常大的數(shù)據(jù)集。

TopK 變種問(wèn)題

TopK 變種的問(wèn)題，就是從 N 個(gè)有序隊(duì)列中，找到最小或者最大的 K 個(gè)值。這個(gè)問(wèn)題的不同點(diǎn)在于，是對(duì)多個(gè)數(shù)據(jù)集進(jìn)行排序。由于初始的數(shù)據(jù)集是有序的，因此不需要遍歷完 N 個(gè)隊(duì)列中所有的元素。因此，解題思路是如何減少要遍歷的元素。

解題思路如下圖所示。

第一步先用 N 個(gè)隊(duì)列的隊(duì)頭元素，也就是每個(gè)隊(duì)列的最小元素，組成一個(gè)有 K 個(gè)元素的小根堆。方式同 TopK 中的方法。

第二步獲取堆頂值，也就是所有隊(duì)列中最小的一個(gè)元素。

第三步用這個(gè)堆頂元素所在隊(duì)列的下一個(gè)值放入堆頂，然后調(diào)整堆。

最后重復(fù)這個(gè)步驟直到獲取夠 K 個(gè)數(shù)。

這里還可以有個(gè)小優(yōu)化就是第三步往堆頂放入新值時(shí)，跟堆的最大值進(jìn)行一下比較，如果已經(jīng)大于堆中最大值，就可以提前終止循環(huán)了。這個(gè)算法的時(shí)間復(fù)雜度是 (N+K-1)*logK，注意這里與隊(duì)列的長(zhǎng)度無(wú)關(guān)。

詳解常用算法

算法的知識(shí)點(diǎn)比較多，提高算法解題能力需要適當(dāng)刷題，但不能單純依靠刷題來(lái)解決問(wèn)題。需要掌握幾種常用解題思路與方法，才能以不變應(yīng)萬(wàn)變。這里講一下：分治、動(dòng)態(tài)規(guī)劃、貪心、回溯和分支界定這五種常用的算法題解題方法，來(lái)看看它們分別適用于什么場(chǎng)景，如何應(yīng)用。

分治法

分治法的思想是將一個(gè)難以直接解決的復(fù)雜問(wèn)題或者大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，分而治之。比如快速排序、歸并排序等都是應(yīng)用了分治法。

適合使用分治法的場(chǎng)景需要滿足三點(diǎn)要求：

可以分解為子問(wèn)題；

子問(wèn)題的解可以合并為原問(wèn)題的解；

子問(wèn)題之間沒(méi)有關(guān)聯(lián)。

使用分治法解決問(wèn)題的一般步驟如下圖表格所示。

第一步，要找到最小子問(wèn)題的求解方法；

第二步，要找到合并子問(wèn)題解的方法；

第三步，要找到遞歸終止條件。

動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法，與分治法類似，也是將問(wèn)題分解為多個(gè)子問(wèn)題。與分治法不同的是，子問(wèn)題的解之間是有關(guān)聯(lián)的。前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。動(dòng)態(tài)規(guī)劃法依次解決各子問(wèn)題，在求解每一個(gè)子問(wèn)題時(shí)，列出所有局部解，通過(guò)決策保留那些有可能達(dá)到全局最優(yōu)的局部解。最后一個(gè)子問(wèn)題的解就是初始問(wèn)題的解。

使用動(dòng)態(tài)規(guī)劃的場(chǎng)景需要也滿足三點(diǎn)條件：

子問(wèn)題的求解必須是按順序進(jìn)行的；

相鄰的子問(wèn)題之間有關(guān)聯(lián)關(guān)系；

最后一個(gè)子問(wèn)題的解就是初始問(wèn)題的解。

使用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)，如上圖表格第二行。

第一步，先要分析最優(yōu)解的性質(zhì)；

第二步，遞歸的定義最優(yōu)解；

第三步，記錄不同階段的最優(yōu)值；

第四步，根據(jù)階段最優(yōu)解選擇全局最優(yōu)解

貪心算法

第三個(gè)貪心算法，因?yàn)樗紤]的是局部的最優(yōu)解，所以貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解。貪心算法的關(guān)鍵是貪心策略的選擇。貪心策略必須具備無(wú)后效性，就是說(shuō)某個(gè)狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

貪心算法使用的場(chǎng)景必須滿足兩點(diǎn)：

局部最優(yōu)解能產(chǎn)生全局最優(yōu)解；

就是剛才說(shuō)的必須具備無(wú)后效性。

如下圖所示，使用貪心算法解題的一般步驟為：

第一步，先分解為子問(wèn)題；

第二步、按貪心策略計(jì)算每個(gè)子問(wèn)題的局部最優(yōu)解；

第三步，合并局部最優(yōu)解。

回溯算法

回溯算法實(shí)際上是一種深度優(yōu)先的搜索算法，按選優(yōu)的條件向前搜索，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回上一步重新選擇，這種走不通就退回再走的方法就是回溯法。

回溯法適用于能夠深度優(yōu)先搜索，并且需要獲取解空間的所有解的場(chǎng)合，例如迷宮問(wèn)題等。

如上圖所示，回溯法一般的解題步驟為：

第一步先針對(duì)所給問(wèn)題，確定問(wèn)題的解空間；

第二步、確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則；

第三步，以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。

分支界定法

最后是分支界定法，與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出滿足約束條件的所有解，而分支界定法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解。

分支界定法適用于廣度優(yōu)先搜索，并且獲取解空間的任意解就可以的場(chǎng)合，例如求解整數(shù)規(guī)劃問(wèn)題。

如上圖所示，分支界定法一般的解題步驟：

第一步先確定解的特征；

第二步在確定子節(jié)點(diǎn)搜索策略，例如是先入先出，還是先入后出；

第三步通過(guò)廣度優(yōu)先遍歷尋找解。