|
在互聯(lián)網(wǎng)行業(yè)的算法面試中經常會被考到數(shù)據(jù)結構的知識，它與算法相輔相成，沒有扎實的數(shù)據(jù)結構基礎，學好算法幾乎不太可能。 挨踢君精心整理了Google資深工程師的學習筆記和解題技巧，總結出6大數(shù)據(jù)結構必考知識點，同時以力扣LeetCode經典題輔助講解，幫助你更好的理解數(shù)據(jù)結構要點。 一、數(shù)據(jù)結構、字符串 數(shù)組和字符串是最基本的數(shù)據(jù)結構，在很多編程語言中都有著十分相似的性質，這部分的算法面試題也是最多的。 很多時候，在分析字符串相關面試題的過程中，要針對字符串當中的每一個字符進行分析和處理，甚至有時候需要先把給定的字符串轉換成字符數(shù)組之后再進行分析和處理，舉個最簡單的例子：翻轉一個字符串。 一種比較快速和直觀的方法是用兩個指針，一個指向字符串的第一個字符a，一個指向它的最后一個字符m，然后互相交換。交換之后，兩個指針向中央一步步地靠攏并相互交換字符，直到兩個指針相遇。由于無法直接修改字符串里的字符，所以必須先把字符串變換為數(shù)組，然后再運用這個算法。 采用數(shù)據(jù)的優(yōu)缺點 a.優(yōu)點：
b.缺點：
所以，在考慮是否應當采用數(shù)組去輔助所用算法時，務必需要考慮它的優(yōu)缺點，看看它的缺點是否會阻礙所用算法的復雜度以及空間復雜度。 01 例題分析 力扣（LeetCode）第242題. Valid Anagram 判斷兩個字符串是否互為字謎 解題思路： 所謂字謎，也就是兩個字符串中的相同字符的數(shù)量要對應相等。例如：s 等于 “anagram”，t 等于 “nagaram”, s 和 t 就互為字謎，因為它們都包含有三個字符a，一個字符g，一個字符m，一個字符n以及一個字符r。而當 s 為 “rat”，t 為 “car”的時候，s 和 t 不互為字謎。 題目里有一個重要的前提：假設兩個字符串只包含小寫字母。小寫字母一共 26 個，這意味著，可以利用兩個個長度都為 26 的字符數(shù)組來統(tǒng)計每個字符串中小寫字母出現(xiàn)的次數(shù)，然后再對比看看是否相等即可。 或者，也可以只利用一個長度為26的字符數(shù)組，將出現(xiàn)在字符串 s 里的字符個數(shù)加一，而出現(xiàn)在字符串 t 里的字符個數(shù)減一，最后判斷每個小寫字母的個數(shù)是否都為零就可以了。 二、鏈表 鏈表的出現(xiàn)在某種程度上是為了避免數(shù)組的一大缺陷，即分配數(shù)組的時候需要開辟一段連續(xù)的內存空間，但魚和熊掌不可兼得，鏈表也犧牲了數(shù)組的一些優(yōu)點，鏈表不能通過下標進行快速查詢。所以在考慮是否需要運用鏈表的時候，務必搞懂所用算法是否需要經常進行查詢和遍歷。 1.鏈表的優(yōu)點和缺點 a.優(yōu)點：
b.缺點：
很顯然，如果要解決的問題里面需要很多快速的查詢，鏈表可能并不適合。一般而言，如果數(shù)據(jù)的元素個數(shù)不確定，而且需要經常進行數(shù)據(jù)的添加和刪除，那么鏈表會比較合適，而如果數(shù)據(jù)元素大小確定，刪除插入的操作并不多，那么數(shù)組可能更適合。 2.鏈表的經典解題方法 a.利用快慢指針（有時候需要用到三個指針）： 例如，鏈表的翻轉，尋找倒數(shù)第k個元素，或者尋找鏈表中間位置的元素，判斷鏈表是否有環(huán)等等。 b.構建一個虛假的鏈表頭: 這個方法一般用在要返回新的鏈表的題目中，例如：
在這類問題里，如果不用一個虛假的鏈表頭，那么在創(chuàng)建新鏈表的第一個元素時，都虛要判斷一下鏈表的頭指針是否為空，也就是要多寫一條if else語句，比較簡潔的寫法是創(chuàng)建一個空的鏈表頭，直接往其后面添加元素即可，最后返回這個空的鏈表頭的下一個節(jié)點即可。 另外，鏈表有單鏈表和雙鏈表，它們是實現(xiàn)很多復雜數(shù)據(jù)結構的基礎，在解決鏈表的題目時，建議在紙上或者白板上畫出節(jié)點之間的相互關系，然后畫出修改的方法，這樣可以有效地分析問題，因為憑空想象是比較困難的，而且在面試的時候，如果能把方法畫在白板上，還能幫助面試官清楚地看到你的思路。 02 例題分析 力扣（LeetCode）第25題. Reverse Nodes in k-Group 在鏈表中對每k個節(jié)點所組成的部分進行翻轉 解題思路： 這道題是力扣（LeetCode） 第24題. Swap Nodes in Pairs （在鏈表中每兩個節(jié)點進行翻轉）的擴展，在這道題里，當k等于2時，第25題就變成了第24題。 那么這道題考察了兩個知識點：
在翻轉鏈表的時候，我們可以借助三個指針：prev、curr、next，分別代表了前一個節(jié)點、當前節(jié)點和下一個節(jié)點。 最為重要的是，當完成了局部的翻轉后，prev就是最終的新的鏈表頭，curr指向了下一個要被處理的局部，而原來的頭指針head成為了鏈表的尾巴。 三、棧 棧是許多力扣中等難度偏上的題目里面經常需要用到的數(shù)據(jù)結構。掌握好它是十分必要的。 1.棧的特點 棧的特點就是后進先出（LIFO），對于棧中的數(shù)據(jù)來說，所有操作都是在棧的頂部完成的，只可以查看棧頂部的數(shù)據(jù)，只能夠向棧的頂部壓?入數(shù)據(jù)，也只能從棧的頂部彈出數(shù)據(jù)。 因此，可以利用一個單鏈表來實現(xiàn)棧的數(shù)據(jù)結構，而且，因為只針對棧頂元素進行操作，所以借用單鏈表的頭就能讓所有棧的操作在O(1)的時間內完成。雖然可以用一個數(shù)組外加一個指針也能實現(xiàn)相似的效果，但是，一旦數(shù)組的長度發(fā)生了改變，哪怕只是在最后添加一個新的元素，時間復雜度不再是O(1)，而且，空間復雜度也得不到優(yōu)化。 2.什么時候需要用到棧呢？ 圍繞棧的算法面試題很多，基本的核心思想就是：當解決某個問題的時候，只關心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。 例如，給出了一串由左括號和右括號組成的字符串，需要判斷這些括號的組成是否合法。方法就是可以利用一個棧，不斷地往里壓左括號，一旦遇上了一個右括號，就把棧頂?shù)淖罄ㄌ枏棾鰜?，表示這是一個合法的組合，以此類推，直到最后判斷棧里還有沒有左括號剩余。 03 例題分析 力扣（LeetCode）第739題. Daily Temperatures 氣溫變化 解題思路： 給定一個數(shù)組 T 代表了未來幾天里每天的溫度值，要求返回一個新的數(shù)組 D，D中的每個元素表示需要經過多少天才能等來溫度的升高。例如： 給定 T：[23, 25, 21, 19, 22, 26, 23] 返回 D: [ 1, 4, 2, 1, 1, 0, 0] 最直觀的做法就是針對每個溫度值向后進行以此搜索，找到比當前溫度更高的值，這樣的計算復雜度就是O(n^2)。 在這樣的搜索過程中，產生了很多重復的對比，從25度開始往后面尋找一個比25度更高的溫度的過程中，先后經歷了21度，19度和22度，這是一個溫度由低到高的過程，也就是在這個過程中已經找到了19度以及21度的答案了，就是22度。 可以運用一個堆棧 stack 來快速地知道需要經過多少天就能等到溫度升高?；镜乃枷胧菑念^到尾掃描一遍給定的數(shù)組 T，如果當天的溫度比堆棧 stack 頂端所記錄的那天溫度還要高，那么就能知道結果了。 這是一道比較有意思的題目，建議到力扣（LeetCode）上試試。 利用堆棧，還可以幫助解決如下常見的問題：
四、隊列 1.隊列的特點 隊列的最大特點是先進先出（FIFO），就好像按順序排隊一樣。 對于隊列的數(shù)據(jù)來說，只允許在隊尾查看和添加數(shù)據(jù)，在隊頭查看和刪除數(shù)據(jù)。 2.如何實現(xiàn)一個隊列 可以借助雙鏈表實現(xiàn)隊列，雙鏈表的頭指針允許在隊頭查看和刪除數(shù)據(jù)，而雙鏈表的尾指針允許在隊尾查看和添加數(shù)據(jù)。 當需要按照一定的順序來處理數(shù)據(jù)，而要處理的數(shù)據(jù)量在不斷地變化的時候，就需要使用隊列。 在算法面試題當中，廣度優(yōu)先搜索（Breadth-First Search）是運用隊列最多的地方。 五、雙端隊列 雙端隊列和普通隊列最大的不同在于，它允許在隊列的頭尾兩端都能在O(1)的時間內進行數(shù)據(jù)的查看、添加和刪除。 與隊列相似，可以利用一個雙鏈表來實現(xiàn)雙端隊列。 雙端隊列最常用的地方就是實現(xiàn)一個長度動態(tài)變化的窗口或者連續(xù)區(qū)間，而動態(tài)窗口這種數(shù)據(jù)結構在很多題目里都有運用。下面通過一道經典的例題來分析它的用法。 04 例題分析 力扣（LeetCode）第239題. Sliding Window Maximum 尋找滑動窗口中的最大值 解題思路： 給定一個數(shù)組以及一個窗口的長度 k，現(xiàn)在移動這個窗口，要求打印出一個數(shù)組，數(shù)組里的每個元素是當前窗口當中最大的那個數(shù)。例如： 輸入：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3 輸出：[3, 3, 5, 5, 6, 7] 可以利用一個雙端隊列來保存當前窗口中最大那個數(shù)在數(shù)組里的下標，有了這個下標，就能很快地知道新的窗口是否已經不再包含原來那個最大的數(shù)，如果不再包含，就把舊的數(shù)從雙端隊列的頭刪除，而雙端隊列新的頭就是當前窗口中最大的那個數(shù)。按照這樣的操作，我們可以在O(n)的時間里完成所有任務。 在這道題當中，我們需要頻繁地進行兩個操作： 1、將新的數(shù)據(jù)加入到窗口的尾部 2、將舊的數(shù)據(jù)從窗口頭部刪除 雙端隊列，它能讓上面的這兩種操作都能在O(1)的時間里完成，使整個算法的復雜度能控制在O(n)。 六、樹 樹的結構十分直觀，而樹的很多概念定義都有一個相同的特點：遞歸，也就是說，一棵樹要滿足某種性質，往往要求每個節(jié)點都必須滿足。例如，在定義一棵二叉搜索樹時，每個節(jié)點也都必須是一棵二叉搜索樹。 正因為樹有這樣的性質，大部分關于樹的面試題都與遞歸有關，換句話說，面試官希望通過一道關于樹的問題來考察你對于遞歸算法掌握的熟練程度。 在面試中?？嫉臉涞男螤钣校浩胀ǘ鏄洹⑵胶舛鏄?、完全二叉樹、二叉搜索樹、四叉樹（Quadtree）、多叉樹（N-ary Tree）。 對于一些特殊的樹，例如紅黑樹（Red-Black Tree）、自平衡二叉搜索樹（AVL Tree），大家不必花費太多時間去準備，一般在面試中不會被問到，除非你所涉及的研究領域跟它們相關或者你十分感興趣。 關于樹的考題，無非就是要考查樹的遍歷以及序列化（serialization)。樹的基本遍歷有三種：前序遍歷（Preorder Traversal）、中序遍歷（Inorder Traversal）以及后序遍歷（Postorder Traversal）。掌握好這三種遍歷的遞歸寫法和非遞歸寫法是非常重要的，同時，懂得分析各種寫法的時間復雜度和空間復雜度同樣重要。 無論你是前端工程師，還是后端工程師，在準備面試的時候，樹這個數(shù)據(jù)結構可以說是最應該花時間學習的。掌握好樹，能證明你對遞歸有很好的認識，能幫助你學習圖論。另外，樹的許多性質都是面試的熱門考點，尤其是二叉搜索樹（BST）。 下面可以通過一道例題來看看樹的考察點。 05 例題分析 力扣（LeetCode）第 230題. Kth Smallest Element in a BST 在一棵二叉搜索樹中尋找第k小的元素 解題思路： 這道題考察了兩個知識點： 1、二叉搜索樹的性質 2、二叉搜索樹的遍歷 二叉搜索樹的中序遍歷可以說是二叉搜索樹性質里最喜歡被考的知識點，因為節(jié)點被遍歷到的順序是按照節(jié)點數(shù)值大小的順序排列好的。也就意味著，按照中序遍歷一次這個二叉搜索樹，遍歷當中遇到的元素都是按照從小到大的順序出現(xiàn)。 采用這個知識點，只需要對這棵樹進行中序遍歷的操作，當訪問到第k個元素的時候返回結果就好。 另外，這道題可以變成求解第k大的元素，方法就是對這個二叉搜索樹進行反向的中序遍歷，那么數(shù)據(jù)的被訪問順序就是由大到小了。
|
|
|
來自： 星光閃亮圖書館 > 《數(shù)據(jù)結構與算法》
