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