數據結構是算法的基石，如果沒有扎實的數據結構基礎，想要把算法學好甚至融會貫通是非常困難的，而優秀的算法又往往取決于你采用哪種數據結構。 所以，接下來兩節課的主題是，在算法面試中經常會被用到的數據結構以及一些實用技巧。同時穿插一些經典的題目，加深理解。這節課主要講： * 數組、字符串 * 鏈表 * 棧 * 隊列 * 雙端隊列 * 樹 #### 數組、字符串（Array & String） * [ ] 字符串轉化 數組和字符串是最基本的數據結構，在很多編程語言中都有著十分相似的性質，而圍繞著它們的算法面試題也是最多的。 很多時候，在分析字符串相關面試題的過程中，我們往往要針對字符串當中的每一個字符進行分析和處理，甚至有時候我們得先把給定的字符串轉換成字符數組之后再進行分析和處理。 舉例：翻轉字符串“algorithm”。 ? 解法：用兩個指針，一個指向字符串的第一個字符 a，一個指向它的最后一個字符 m，然后互相交換。交換之后，兩個指針向中央一步步地靠攏并相互交換字符，直到兩個指針相遇。這是一種比較快速和直觀的方法。 注意：由于無法直接修改字符串里的字符，所以必須先把字符串變換為數組，然后再運用這個算法。 #### 數組的優缺點 要掌握一種數據結構，就必須要懂得分析它的優點和缺點。數組的優點在于： * 構建非常簡單 * 能在 O(1) 的時間里根據數組的下標（index）查詢某個元素 而數組的缺點在于： * 構建時必須分配一段連續的空間 * 查詢某個元素是否存在時需要遍歷整個數組，耗費 O(n) 的時間（其中，n 是元素的個數） * 刪除和添加某個元素時，同樣需要耗費 O(n) 的時間 所以，當你在考慮是否應當采用數組去輔助你的算法時，請務必考慮它的優缺點，看看它的缺點是否會阻礙你的算法復雜度以及空間復雜度。 * [ ] 例題分析 LeetCode 第 242 題：給定兩個字符串 s 和 t，編寫一個函數來判斷 t 是否是 s 的字母異位詞。 說明：你可以假設字符串只包含小寫字母。 示例?1 ``` 輸入: s = "anagram", t = "nagaram" 輸出: true ``` 示例 2 ``` 輸入: s = "rat", t = "car" 輸出: false ``` 字母異位詞，也就是兩個字符串中的相同字符的數量要對應相等。例如，s 等于 “anagram”，t 等于 “nagaram”，s 和 t 就互為字母異位詞。因為它們都包含有三個字符 a，一個字符 g，一個字符 m，一個字符 n，以及一個字符 r。而當 s 為 “rat”，t 為 “car”的時候，s 和 t 不互為字母異位詞。 * [ ] 解題思路 一個重要的前提“假設兩個字符串只包含小寫字母”，小寫字母一共也就 26 個，因此： 1. 可以利用兩個長度都為 26 的字符數組來統計每個字符串中小寫字母出現的次數，然后再對比是否相等； 2. 可以只利用一個長度為 26 的字符數組，將出現在字符串 s 里的字符個數加 1，而出現在字符串 t 里的字符個數減 1，最后判斷每個小寫字母的個數是否都為 0。 按上述操作，可得出結論：s 和 t 互為字母異位詞。 建議：限于篇幅不對此題進行代碼剖析，但是這道題非常經典，建議大家到 LeetCode 上試試。 #### 鏈表（LinkedList） 單鏈表：鏈表中的每個元素實際上是一個單獨的對象，而所有對象都通過每個元素中的引用字段鏈接在一起。 雙鏈表：與單鏈表不同的是，雙鏈表的每個結點中都含有兩個引用字段。 * [ ] 鏈表的優缺點 * 鏈表的優點如下： 鏈表能靈活地分配內存空間； 能在 O(1) 時間內刪除或者添加元素，前提是該元素的前一個元素已知，當然也取決于是單鏈表還是雙鏈表，在雙鏈表中，如果已知該元素的后一個元素，同樣可以在 O(1) 時間內刪除或者添加該元素。 * 鏈表的缺點是： 不像數組能通過下標迅速讀取元素，每次都要從鏈表頭開始一個一個讀取； 查詢第 k 個元素需要 O(k) 時間。 **應用場景**：如果要解決的問題里面需要很多快速查詢，鏈表可能并不適合；如果遇到的問題中，數據的元素個數不確定，而且需要經常進行數據的添加和刪除，那么鏈表會比較合適。而如果數據元素大小確定，刪除插入的操作并不多，那么數組可能更適合。 * [ ] 經典解法 鏈表是實現很多復雜數據結構的基礎，經典解法如下。 **1. 利用快慢指針（有時候需要用到三個指針）** 典型題目例如：鏈表的翻轉，尋找倒數第 k 個元素，尋找鏈表中間位置的元素，判斷鏈表是否有環等等。 **2. 構建一個虛假的鏈表頭** 一般用在要返回新的鏈表的題目中，比如，給定兩個排好序的鏈表，要求將它們整合在一起并排好序。又比如，將一個鏈表中的奇數和偶數按照原定的順序分開后重新組合成一個新的鏈表，鏈表的頭一半是奇數，后一半是偶數。 在這類問題里，如果不用一個虛假的鏈表頭，那么在創建新鏈表的第一個元素時，我們都得要判斷一下鏈表的頭指針是否為空，也就是要多寫一條 if else 語句。比較簡潔的寫法是創建一個空的鏈表頭，直接往其后面添加元素即可，最后返回這個空的鏈表頭的下一個節點即可。 建議：在解決鏈表的題目時，可以在紙上或者白板上畫出節點之間的相互關系，然后畫出修改的方法，既可以幫助你分析問題，又可以在面試的時候，幫助面試官清楚地看到你的思路。 * [ ] 例題分析 LeetCode 第 25 題：給你一個鏈表，每?k?個節點一組進行翻轉，請你返回翻轉后的鏈表。k?是一個正整數，它的值小于或等于鏈表的長度。如果節點總數不是?k?的整數倍，那么請將最后剩余的節點保持原有順序。 說明： * 你的算法只能使用常數的額外空間。 * 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。 示例： ``` 給定這個鏈表：1->2->3->4->5 當?k=2 時，應當返回：2->1->4->3->5 當?k=3 時，應當返回：3->2->1->4->5 ``` * [ ] 解題思路 這道題考察了兩個知識點： 1. 對鏈表翻轉算法是否熟悉 2. 對遞歸算法的理解是否清晰 在翻轉鏈表的時候，可以借助三個指針：prev、curr、next，分別代表前一個節點、當前節點和下一個節點，實現過程如下所示。  1. 將 curr 指向的下一節點保存到 next 指針； 2. curr 指向 prev，一起前進一步； 3. 重復之前步驟，直到 k 個元素翻轉完畢； 4. 當完成了局部的翻轉后，prev 就是最終的新的鏈表頭，curr 指向了下一個要被處理的局部，而原來的頭指針 head 成為了鏈表的尾巴。 注意：這道題是“LeetCode 第 24 題，兩個一組翻轉鏈表“的擴展，即當 k 等于 2 時，第 25 題就變成了第 24 題。 #### 棧（Stack） 特點：棧的最大特點就是后進先出（LIFO）。對于棧中的數據來說，所有操作都是在棧的頂部完成的，只可以查看棧頂部的元素，只能夠向棧的頂部壓?數據，也只能從棧的頂部彈出數據。 實現：利用一個單鏈表來實現棧的數據結構。而且，因為我們都只針對棧頂元素進行操作，所以借用單鏈表的頭就能讓所有棧的操作在 O(1) 的時間內完成。 應用場景：在解決某個問題的時候，只要求關心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。 如果打算用一個數組外加一個指針來實現相似的效果，那么，一旦數組的長度發生了改變，哪怕只是在最后添加一個新的元素，時間復雜度都不再是 O(1)，而且，空間復雜度也得不到優化。 注意：棧是許多 LeetCode 中等難度偏上的題目里面經常需要用到的數據結構，掌握好它是十分必要的。 * [ ] 例題分析一 LeetCode 第 20 題：給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。 有效字符串需滿足： 1. 左括號必須用相同類型的右括號閉合。 2. 左括號必須以正確的順序閉合。 注意：空字符串可被認為是有效字符串。 示例 1 ``` 輸入: "()" 輸出: true ``` 示例 2 ``` 輸入: "(]" 輸出: false ``` * [ ] 解題思路 利用一個棧，不斷地往里壓左括號，一旦遇上了一個右括號，我們就把棧頂的左括號彈出來，表示這是一個合法的組合，以此類推，直到最后判斷棧里還有沒有左括號剩余。 * [ ] 例題分析二 LeetCode 第 739 題：根據每日氣溫列表，請重新生成一個列表，對應位置的輸入是你需要再等待多久溫度才會升高超過該日的天數。如果之后都不會升高，請在該位置用?0?來代替。 提示：氣溫列表 temperatures 長度的范圍是?[1, 30000]。 示例：給定一個數組 T 代表了未來幾天里每天的溫度值，要求返回一個新的數組 D，D 中的每個元素表示需要經過多少天才能等來溫度的升高。 ``` 給定 T：[23, 25, 21, 19, 22, 26, 23] 返回 D: ?[ ?1, ? 4, ??2, ? 1, ? 1, ??0, ? 0] ``` * [ ] 解題思路 第一個溫度值是 23 攝氏度，它要經過 1 天才能等到溫度的升高，也就是在第二天的時候，溫度升高到 24 攝氏度，所以對應的結果是 1。接下來，從 25 度到下一次溫度的升高需要等待 4 天的時間，那時溫度會變為 26 度。 思路 1：最直觀的做法就是針對每個溫度值向后進行依次搜索，找到比當前溫度更高的值，這樣的計算復雜度就是?O(n2)。 但是，在這樣的搜索過程中，產生了很多重復的對比。例如，從 25 度開始往后面尋找一個比 25 度更高的溫度的過程中，經歷了 21 度、19 度和 22 度，而這是一個溫度由低到高的過程，也就是說在這個過程中已經找到了 19 度以及 21 度的答案，它就是 22 度。 思路 2：可以運用一個堆棧 stack 來快速地知道需要經過多少天就能等到溫度升高。從頭到尾掃描一遍給定的數組 T，如果當天的溫度比堆棧 stack 頂端所記錄的那天溫度還要高，那么就能得到結果。 ? 1. 對第一個溫度 23 度，堆棧為空，把它的下標壓入堆棧； 2. 下一個溫度 24 度，高于 23 度高，因此 23 度溫度升高只需 1 天時間，把 23 度下標從堆棧里彈出，把 24 度下標壓入； 3. 同樣，從 24 度只需要 1 天時間升高到 25 度； 4. 21 度低于 25 度，直接把 21 度下標壓入堆棧； 5. 19 度低于 21 度，壓入堆棧； 6. 22 度高于 19 度，從 19 度升溫只需 1 天，從 21 度升溫需要 2 天； 7. 由于堆棧里保存的是下標，能很快計算天數； 8. 22 度低于 25 度，意味著尚未找到 25 度之后的升溫，直接把 22 度下標壓入堆棧頂端； 9. 后面的溫度與此同理。 該方法只需要對數組進行一次遍歷，每個元素最多被壓入和彈出堆棧一次，算法復雜度是 O(n)。 利用堆棧，還可以解決如下常見問題： * 求解算術表達式的結果（LeetCode 224、227、772、770) * 求解直方圖里最大的矩形區域（LeetCode 84） * [ ] 隊列（Queue） 特點：和棧不同，隊列的最大特點是先進先出（FIFO），就好像按順序排隊一樣。對于隊列的數據來說，我們只允許在隊尾查看和添加數據，在隊頭查看和刪除數據。 實現：可以借助雙鏈表來實現隊列。雙鏈表的頭指針允許在隊頭查看和刪除數據，而雙鏈表的尾指針允許我們在隊尾查看和添加數據。 應用場景：直觀來看，當我們需要按照一定的順序來處理數據，而該數據的數據量在不斷地變化的時候，則需要隊列來幫助解題。在算法面試題當中，廣度優先搜索（Breadth-First Search）是運用隊列最多的地方，我們將在第 06 課時中詳細介紹。 * [ ] 雙端隊列（Deque） 特點：雙端隊列和普通隊列最大的不同在于，它允許我們在隊列的頭尾兩端都能在 O(1) 的時間內進行數據的查看、添加和刪除。 實現：與隊列相似，我們可以利用一個雙鏈表實現雙端隊列。 應用場景：雙端隊列最常用的地方就是實現一個長度動態變化的窗口或者連續區間，而動態窗口這種數據結構在很多題目里都有運用。 * [ ] 例題分析 LeetCode 第 239 題：給定一個數組?nums，有一個大小為?k?的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口?k 內的數字，滑動窗口每次只向右移動一位。返回滑動窗口最大值。 注意：你可以假設?k?總是有效的，1 ≤ k ≤?輸入數組的大小，且輸入數組不為空。 示例：給定一個數組以及一個窗口的長度 k，現在移動這個窗口，要求打印出一個數組，數組里的每個元素是當前窗口當中最大的那個數。 ``` 輸入：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3 輸出：[3, 3, 5, 5, 6, 7] ``` * [ ] 解題思路 思路 1：移動窗口，掃描，獲得最大值。假設數組里有 n 個元素，算法復雜度就是 O(n)。這是最直觀的做法。 思路 2：利用一個雙端隊列來保存當前窗口中最大那個數在數組里的下標，雙端隊列新的頭就是當前窗口中最大的那個數。通過該下標，可以很快地知道新的窗口是否仍包含原來那個最大的數。如果不再包含，我們就把舊的數從雙端隊列的頭刪除。 因為雙端隊列能讓上面的這兩種操作都能在 O(1) 的時間里完成，所以整個算法的復雜度能控制在 O(n)。 1. 初始化窗口 k=3，包含 1，3，-1，把 1 的下標壓入雙端隊列的尾部； 2. 把 3 和雙端隊列的隊尾的數據逐個比較，3 >1，把 1 的下標彈出，把 3 的下標壓入隊尾； 3. -1<3，-1 壓入雙端隊列隊尾保留到下一窗口進行比較； 4. 3 為當前窗口的最大值； 5. 窗口移動，-3 與隊尾數據逐個比較，-3<-1，-3 壓入雙端隊列隊尾保留； 6. 3 為當前窗口的最大值； 7. 窗口繼續移動，5>-3，-3 從雙端隊列隊尾彈出； 8. 5>-1，-1 從隊尾彈出； 9. 3 超出當前窗口，從隊列頭部彈出； 10. 5 壓入隊列頭部，成為當前窗口最大值； 11. 繼續移動窗口，操作與上述同理。 窗口最大值只需讀取雙端隊列頭部元素。 * [ ] 樹（Tree） 樹的結構十分直觀，而樹的很多概念定義都有一個相同的特點：遞歸，也就是說，一棵樹要滿足某種性質，往往要求每個節點都必須滿足。例如，在定義一棵二叉搜索樹時，每個節點也都必須是一棵二叉搜索樹。 正因為樹有這樣的性質，大部分關于樹的面試題都與遞歸有關，換句話說，面試官希望通過一道關于樹的問題來考察你對于遞歸算法掌握的熟練程度。 * [ ] 樹的形狀 在面試中常考的樹的形狀有：普通二叉樹、平衡二叉樹、完全二叉樹、二叉搜索樹、四叉樹（Quadtree）、多叉樹（N-ary Tree）。 對于一些特殊的樹，例如紅黑樹（Red-Black Tree）、自平衡二叉搜索樹（AVL Tree），一般在面試中不會被問到，除非你所涉及的研究領域跟它們相關或者你十分感興趣，否則不需要特別著重準備。 關于樹的考題，無非就是要考查樹的遍歷以及序列化（serialization)。 * [ ] 樹的遍歷 * 1. 前序遍歷（Preorder Traversal） 方法：先訪問根節點，然后訪問左子樹，最后訪問右子樹。在訪問左、右子樹的時候，同樣，先訪問子樹的根節點，再訪問子樹根節點的左子樹和右子樹，這是一個不斷遞歸的過程。 應用場景：運用最多的場合包括在樹里進行搜索以及創建一棵新的樹。 * 2. 中序遍歷（Inorder Traversal） 方法：先訪問左子樹，然后訪問根節點，最后訪問右子樹，在訪問左、右子樹的時候，同樣，先訪問子樹的左邊，再訪問子樹的根節點，最后再訪問子樹的右邊。 應用場景：最常見的是二叉搜索樹，由于二叉搜索樹的性質就是左孩子小于根節點，根節點小于右孩子，對二叉搜索樹進行中序遍歷的時候，被訪問到的節點大小是按順序進行的。 * 3. 后序遍歷（Postorder Traversal） 方法：先訪問左子樹，然后訪問右子樹，最后訪問根節點。? 應用場景：在對某個節點進行分析的時候，需要來自左子樹和右子樹的信息。收集信息的操作是從樹的底部不斷地往上進行，好比你在修剪一棵樹的葉子，修剪的方法是從外面不斷地往根部將葉子一片片地修剪掉。 注意： * 掌握好這三種遍歷的遞歸寫法和非遞歸寫法是非常重要的，懂得分析各種寫法的時間復雜度和空間復雜度同樣重要。 * 無論是前端工程師，還是后端工程師，在準備面試的時候，樹這個數據結構都是最應該花時間學習的，既能證明你對遞歸有很好的認識，又能幫助你學習圖論（關于圖論，我們將在下一節課一起討論）。樹的許多性質都是面試的熱門考點，尤其是二叉搜索樹（BST）。 建議：練習一道經典的 LeetCode 第 250 題，在一棵二叉樹里，統計有多少棵子樹，要求子樹里面的元素擁有相同的數字。 * [ ] 例題分析 LeetCode 第 230 題：給定一個二叉搜索樹，編寫一個函數?kthSmallest?來查找其中第?k?個最小的元素。 說明：你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。 * [ ] 解題思路 這道題考察了兩個知識點： * 二叉搜索樹的性質 * 二叉搜索樹的遍歷 二叉搜索樹的性質：對于每個節點來說，該節點的值比左孩子大，比右孩子小，而且一般來說，二叉搜索樹里不出現重復的值。 二叉搜索樹的中序遍歷是高頻考察點，節點被遍歷到的順序是按照節點數值大小的順序排列好的。即，中序遍歷當中遇到的元素都是按照從小到大的順序出現。 因此，我們只需要對這棵樹進行中序遍歷的操作，當訪問到第 k 個元素的時候返回結果就好。 注意：這道題可以變成求解第 K 大的元素，方法就是對這個二叉搜索樹進行反向的中序遍歷，那么數據的被訪問順序就是由大到小了。 #### 總結 這節課主要講解算法面試中常用的基本數據結構。掌握好這些數據結構是基礎，絕大部分的算法面試題都得靠它們來幫忙，因此，一定要花功夫勤練題目來深入理解它們。