涉及的幾個部分?jǐn)?shù)據(jù)結(jié)構(gòu)部分
數(shù)組樱哼、棧、鏈表剿配、隊列搅幅、樹、圖
數(shù)組
數(shù)組是最簡單呼胚、也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)茄唐。棧、隊列等其他數(shù)據(jù)結(jié)構(gòu)均由數(shù)組演變而來砸讳。
面試問題：
1琢融、尋找數(shù)組中第二小的元素
2、找到數(shù)組中第一個不重復(fù)出現(xiàn)的整數(shù)
3簿寂、合并兩個有序數(shù)組
4漾抬、重新排列數(shù)組中的正值和負(fù)值
棧
可以把棧想象成一列垂直堆放的書。為了拿到中間的書常遂，你需要移除放置在這上面的所有書纳令。這就是LIFO（后進先出）的工作原理。
下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是（C）A．隊列B．循環(huán)隊列C．棧D．順序表
具有記憶功能的數(shù)據(jù)結(jié)構(gòu)是棧克胳，原因很簡單：后進棧的先出棧平绩，所以你對一個棧進行出棧操作，出來的元素肯定是你最后存入棧中的元素漠另，所以棧有記憶功能捏雌。
棧的基本操作
Push——在頂部插入一個元素
Pop——返回并移除棧頂元素
isEmpty——如果棧為空，則返回true
Top——返回頂部元素笆搓，但并不移除它
面試中關(guān)于棧的常見問題
1性湿、使用棧計算后綴表達式
后綴表達式，指的是不包含括號满败，運算符放在兩個運算對象的后面肤频，所有的計算按運算符出現(xiàn)的順序，嚴(yán)格從左向右進行(不再考慮運算符的優(yōu)先規(guī)則)算墨。
對于一個算術(shù)表達式我們的一般寫法是這樣的(3 + 4) × 5 – 6宵荒，這中寫法是中序表達式 ，而后序表達式則是將運算符放在操作數(shù)的后面,如3 4 + 5 × 6 –，可以看出后序表達式中沒有括號, 只表達了計算的順序, 而這個順序恰好就是計算器中的一般計算順序报咳，給出一個算式侠讯，如：（3 * 4-（2+5）） * 4 / 2，其等價的后綴表達式為：3 4 * 2 5 + - 4 * 2 /少孝；計算方法為從左到右掃描后綴表達式继低，遇到數(shù)字則入棧，遇到運算符則將棧中的數(shù)字出棧稍走，第一個出棧的數(shù)字充當(dāng)?shù)诙€運算數(shù)，第二個出棧的數(shù)字充當(dāng)?shù)谝粋€運算數(shù)柴底，與運算符作運算婿脸，并將結(jié)果入棧，最后棧中剩下的那個數(shù)就是運算結(jié)果柄驻。
2狐树、對棧的元素進行排序
編寫程序，按升序?qū)＿M行排序（即最大元素位于棧頂）鸿脓。最多只能使用一個額外的棧存放臨時數(shù)據(jù)抑钟，但不得將元素復(fù)制到別的數(shù)據(jù)結(jié)構(gòu)（如數(shù)組）。
假設(shè)數(shù)據(jù)保存在原棧s1中野哭，另設(shè)輔助棧s2在塔。數(shù)據(jù)進行一系列處理后以升序排在棧s1中，那么s1中的數(shù)據(jù)一定是由s2棧傾倒出的拨黔。所以在完成所有數(shù)據(jù)在s1中升序排列之前數(shù)據(jù)應(yīng)該在s2中降序排列蛔溃，即大元素位于棧底。所以問題轉(zhuǎn)化為從s1中彈出元素輸入到s2中并使這些元素降序排列篱蝇『卮考慮這一操作的中間過程，假設(shè)已經(jīng)彈出s1的部分元素壓入s2中零截，數(shù)據(jù)在s2中已排序麸塞，s2從棧底到棧頂有5,3,2,1這4個元素，假設(shè)當(dāng)前s1的棧頂元素是4涧衙，現(xiàn)在要將4入棧s2哪工，為了保持s2棧中元素的順序，4應(yīng)該放入3的下面绍撞。這時候s2中的1正勒，2，3都需要彈出給4讓出位置傻铣，1章贞，2，3只能臨時存放在s1中，為了避免s1原先的棧頂元素4被覆蓋鸭限，可以設(shè)臨時變量保存棧頂4蜕径，然后彈出4.再將s2中小于的4的元素全部彈出到s1中，原先s1的棧頂4先入棧s2败京，再將1,2,3從s1中還原到s2,這時候s2中的元素還是排好序的兜喻，為5,4,3,2,1。
3赡麦、判斷表達式是否括號平衡
思路：建立一個順序棧朴皆，當(dāng)表達式中有左括號時將其入棧，當(dāng)出現(xiàn)右括號時泛粹，將棧頂元素出棧遂铡，檢查與當(dāng)前右括號是否匹配。最后如果棧為空則表示該表達式中的括號是匹配的晶姊。
隊列
與棧相似扒接，隊列是另一種順序存儲元素的線性數(shù)據(jù)結(jié)構(gòu)。棧與隊列的最大差別在于棧是LIFO（后進先出）们衙，而隊列是FIFO钾怔，即先進先出。
隊列的基本操作
Enqueue()?——?在隊列尾部插入元素
Dequeue()?——移除隊列頭部的元素
isEmpty()——如果隊列為空蒙挑，則返回true
Top()?——返回隊列的第一個元素
面試中關(guān)于隊列的常見問題
1宗侦、使用隊列表示棧
棧實現(xiàn)隊列：思路是有兩個棧，一個用來放數(shù)據(jù)（數(shù)據(jù)棧）脆荷，一個用來輔助（輔助棧）凝垛。數(shù)據(jù)添加時，會依次壓人棧蜓谋，取數(shù)據(jù)時肯定會取棧頂元素梦皮，但我們想模擬隊列的先進先出，所以就得取棧底元素桃焕，那么輔助棧就派上用場了剑肯，把數(shù)據(jù)棧的元素依次彈出到輔助棧，但保留最后一個元素观堂，最后數(shù)據(jù)棧就剩下了最后一個元素让网，直接把元素返回，這時數(shù)據(jù)棧已經(jīng)沒有了數(shù)據(jù)师痕。最后呢溃睹，把輔助棧的元素依次壓人數(shù)據(jù)棧，這樣胰坟，我們成功取到了棧底元素因篇。
隊列實現(xiàn)棧
思路同上：有數(shù)據(jù)隊列和輔助隊列，模擬棧的先進后出，隊列是隊尾進隊頭出竞滓，也就是說每次取值要取隊列的隊尾元素咐吼，數(shù)據(jù)隊列出隊到輔助隊列，留下最后一個元素返回商佑，輔助隊列再把元素出隊到數(shù)據(jù)隊列
2锯茄、對隊列的前k個元素倒序
實現(xiàn)方法為每次遍歷隊列，從中找出最小的元素茶没，放入臨時隊列肌幽，遍歷的過程是出隊的過程，注意如果一個元素比當(dāng)前的最小值大礁叔，則要放回隊列當(dāng)中牍颈，如果比當(dāng)前的最小值小，則保存起來琅关，暫時不放回隊列中，發(fā)現(xiàn)更小的讥蔽，把原來的最小值放入涣易，更新最小值，在遍歷完一次以后冶伞，將最小值存入臨時隊列新症。然后開始第二次遍歷，注意每次遍歷原隊列中都會減少一個元素响禽，因此共遍歷隊列N次徒爹，每次對隊列N、N-1芋类、N-2 ... 1這么多次出隊操作來找最小值隆嗅，在最后一次完成后臨時隊列中存放的就是排序好的結(jié)果，出隊N次即可按非降序輸出侯繁。
3胖喳、使用隊列生成從1到n的二進制數(shù)
十進制數(shù)化二進制數(shù)：整數(shù)部分用“除二取余“法，將數(shù)除以2贮竟，將余數(shù)放入棧丽焊，商再除以2，重復(fù)咕别。直至商為0技健。小數(shù)部分用“乘二取整”法，數(shù)乘2惰拱，然后取整掌栅、放入隊列里
鏈表
鏈表是另一個重要的線性數(shù)據(jù)結(jié)構(gòu)，乍一看可能有點像數(shù)組公黑，但在內(nèi)存分配、內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)插入和刪除的基本操作方面均有所不同删掀。
鏈表就像一個節(jié)點鏈，其中每個節(jié)點包含著數(shù)據(jù)和指向后續(xù)節(jié)點的指針导街。 鏈表還包含一個頭指針披泪，它指向鏈表的第一個元素，但當(dāng)列表為空時搬瑰，它指向null或無具體內(nèi)容款票。
鏈表一般用于實現(xiàn)文件系統(tǒng)、哈希表和鄰接表泽论。
鏈表按方向分包括以下類型：
單鏈表（單向）
雙向鏈表（雙向）
鏈表的基本操作：
InsertAtEnd - 在鏈表的末尾插入指定元素
InsertAtHead - 在鏈接列表的開頭/頭部插入指定元素
Delete? - 從鏈接列表中刪除指定元素
DeleteAtHead - 刪除鏈接列表的第一個元素
Search? - 從鏈表中返回指定元素
isEmpty - 如果鏈表為空艾少，則返回true
面試中關(guān)于鏈表的常見問題
1、反轉(zhuǎn)鏈表
鏈表反轉(zhuǎn)單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題翼悴，也是一個非掣抗唬基礎(chǔ)的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1鹦赎。最容易想到的方法遍歷一遍鏈表谍椅，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素古话，然后將當(dāng)前節(jié)點元素的指針反轉(zhuǎn)后雏吭，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷
還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當(dāng)前節(jié)點之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點陪踩。
2杖们、檢測鏈表中的循環(huán)
判斷鏈表是否存在環(huán)型鏈表問題：判斷一個鏈表是否存在環(huán)，例如下面這個鏈表就存在一個環(huán)：
例如N1->N2->N3->N4->N5->N2就是一個有環(huán)的鏈表肩狂，環(huán)的開始結(jié)點是N5這里有一個比較簡單的解法摘完。設(shè)置兩個指針p1，p2婚温。每次循環(huán)p1向前走一步描焰，p2向前走兩步。直到p2碰到NULL指針或者兩個指針相等結(jié)束循環(huán)栅螟。如果兩個指針相等則說明存在環(huán)荆秦。
3、返回鏈表倒數(shù)第N個節(jié)點
思路很簡單力图，只有兩種出現(xiàn)的情況：
1步绸、鏈表的長度剛剛好等于n，也就是說刪除表頭節(jié)點吃媒，
2瓤介、鏈表長度大于n吕喘，那么我們先定義兩個表頭，一個后移n位刑桑，然后兩個鏈表同時后移氯质，這時當(dāng)后面的節(jié)點到達尾部時，前面的節(jié)點就是刪除的節(jié)點的前一個節(jié)點祠斧。
4闻察、刪除鏈表中的重復(fù)項
思路一：
遍歷鏈表，把遍歷的值存儲到一個Hashtable中琢锋，在遍歷過程中辕漂，若當(dāng)前訪問的值在Hashtable中已經(jīng)存在，則說明這個數(shù)據(jù)是重復(fù)的吴超，因此就可以刪除钉嘹。
優(yōu)點：時間復(fù)雜度較低O(n)
缺點：在遍歷過程中需要額外的存儲空間來保存已遍歷過的值
思路二：
對鏈表進行雙重循環(huán)遍歷，外循環(huán)正常遍歷鏈表鲸阻，假設(shè)外循環(huán)當(dāng)前遍歷的結(jié)點為cur跋涣，內(nèi)循環(huán)從cur開始遍歷，若碰到與cur所指向結(jié)點值相同鸟悴，則刪除這個重復(fù)結(jié)點
優(yōu)點：不需要額外的存儲空間
缺點：時間復(fù)雜度較高O(n^2)
思路三：
外循環(huán)當(dāng)前遍歷的結(jié)點為cur仆潮，內(nèi)循環(huán)從鏈表頭開始遍歷至cur，只要碰到與cur值相同的結(jié)點就刪除該結(jié)點遣臼，同時內(nèi)循環(huán)結(jié)束，因為與cur相同的結(jié)點只可能存在一個（如果存在多個拾并，在前面的遍歷過程中已經(jīng)被刪除了）
優(yōu)點：采用這種方法在特定的數(shù)據(jù)發(fā)布的情況下會提高算法的時間復(fù)雜度
樹
樹形結(jié)構(gòu)是一種層級式的數(shù)據(jù)結(jié)構(gòu)揍堰，由頂點（節(jié)點）和連接它們的邊組成。 樹類似于圖嗅义，但區(qū)分樹和圖的重要特征是樹中不存在環(huán)路屏歹。
樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法，它可以提供解決問題的有效存儲機制之碗。
以下是樹形結(jié)構(gòu)的主要類型：
N元樹蝙眶、平衡樹、二叉樹褪那、二叉搜索樹幽纷、AVL樹、紅黑樹博敬、2-3樹
二叉樹和二叉搜索樹是最常用的樹
二叉查找樹（BinarySearch Tree友浸，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹偏窝，或者是具有下列性質(zhì)的二叉樹：
1）若任意節(jié)點的左子樹不空收恢，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值武学；
2）若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值伦意；
3）任意節(jié)點的左火窒、右子樹也分別為二叉查找樹。
二叉查找樹性質(zhì)：對二叉查找樹進行中序遍歷驮肉，即可得到有序的數(shù)列熏矿。
面試中關(guān)于樹結(jié)構(gòu)的常見問題：
1、求二叉樹的高度
算法一：采用后序遍歷二叉樹缆八，結(jié)點最大棧長即為二叉樹的高度曲掰；
算法二：層次遍歷二叉樹，最大層次即為二叉樹的高度奈辰；
算法三：采用遞歸算法栏妖，求二叉樹的高度
2、在二叉搜索樹中查找第k個最大值
解題思路：通過中序遍歷二叉搜索樹奖恰，找到第k大的節(jié)點的值temp吊趾，然后通過層次遍歷二叉搜索樹，找到值為temp的節(jié)點瑟啃，并且返回該節(jié)點
注意考慮：
1）二叉搜索樹為空论泛，或者k為0則直接返回null；
2）k的值大于二叉搜索樹的節(jié)點個數(shù)蛹屿，則返回null
3）查找與根節(jié)點距離k的節(jié)點
4）在二叉樹中查找給定節(jié)點的祖先節(jié)點
這道題的傳統(tǒng)思路是想方法把根到兩個點的路徑分別保存在兩個容器中屁奏，然后從后往前遍歷容器找出相等的節(jié)點便為最近公共祖先。很容易計算出這是一個時間復(fù)雜度為o(n)错负，空間復(fù)雜度為o(lgn)的算法坟瓢。
如果我們這時要求使用空間復(fù)雜度為o（1）的算法
我們可以這樣做： 假設(shè)2個節(jié)點為p1, p2。
我們遍歷這顆樹犹撒，如果發(fā)現(xiàn)這個節(jié)點為p1/p2或者這個
節(jié)點的子樹中有p1/p2時折联，返回p1/p2。否則為NULL.
在這里注意识颊，如果一個節(jié)點的左右子樹都返回一個非NULL值诚镰，那么這個節(jié)點一定為p1,p2的最近公共祖先。 這時我們返回這個節(jié)點祥款。如果p1為p2的祖先清笨，那么遍歷到p1時便會返回而不會遍歷p1子樹。那么不會有節(jié)點的左右子樹都不為NULL镰踏，只會返回p1,而p1正好是它們的最近公共祖先函筋。
圖
圖是一組以網(wǎng)絡(luò)形式相互連接的節(jié)點。節(jié)點也稱為頂點奠伪。 一對節(jié)點（x跌帐，y）稱為邊（edge）首懈，表示頂點x連接到頂點y。邊可以包含權(quán)重/成本谨敛，顯示從頂點x到y(tǒng)所需的成本究履。
圖的類型
無向圖
有向圖
在程序語言中，圖可以用兩種形式表示：
鄰接矩陣
鄰接表
常見圖遍歷算法
廣度優(yōu)先搜索
深度優(yōu)先搜索
面試中關(guān)于圖的常見問題
1脸狸、實現(xiàn)廣度和深度優(yōu)先搜索
深度優(yōu)先搜索
（1）用棧記錄下一步的走向最仑。訪問一個頂點的過程中要做三件事：
①訪問頂點
②頂點入棧，以便記住它
③標(biāo)記頂點炊甲，以便不會再訪問它
（2）訪問規(guī)則：
a.如果可能泥彤，訪問一個鄰接的未訪問頂點，標(biāo)記它卿啡，并入棧吟吝。
b.當(dāng)不能執(zhí)行a時（沒有鄰接的未訪問頂點），如果棧不為空颈娜，就從棧中彈出一個頂點剑逃。
c.如果不能執(zhí)行規(guī)則a和b，就完成了整個搜索過程官辽。
（3）實現(xiàn)：基于以上規(guī)則蛹磺，循環(huán)執(zhí)行，直到棧為空同仆。每次循環(huán)各種萤捆，它做四件事：
①用peek()方法檢查棧頂?shù)捻旤c。
②試圖找到這個頂點還未訪問的鄰接點俗批。
③如果沒有找到鳖轰，出棧。
④如果找到這樣的頂點扶镀，訪問并入棧。
廣度優(yōu)先搜索（BFS）：
（1）用隊列記錄下一步的走向焰轻。深度優(yōu)先搜素表現(xiàn)的好像是盡快遠(yuǎn)離起點似的臭觉，相反，廣度優(yōu)先搜索中辱志，算法好像要盡可能靠近起始點蝠筑。
（2）訪問規(guī)則：
a.訪問下一個未訪問的鄰接點（如果存在），這個頂點必須是當(dāng)前頂點的鄰接點揩懒，標(biāo)記它什乙，并入隊列。
b.如果因為已經(jīng)沒有未訪問頂點而不能執(zhí)行規(guī)則a已球，那么從隊列頭取一個頂點（如果存在）臣镣，并使其成為當(dāng)前頂點辅愿。
c.如果因為隊列為空而不能執(zhí)行規(guī)則b，則完成了整個搜索過程忆某。
（3）實現(xiàn)：基于以上規(guī)則点待，對下圖做bfs遍歷
深度優(yōu)先搜素算法：不全部保留結(jié)點，占用空間少弃舒；有回溯操作(即有入棧癞埠、出棧操作)，運行速度慢聋呢。
廣度優(yōu)先搜索算法：保留全部結(jié)點苗踪，占用空間大； 無回溯操作(即無入棧削锰、出棧操作)通铲，運行速度快。
2喂窟、檢查圖是否為樹
一個無向圖G是一棵樹的條件是G必須是無回路的連通圖或是有n-1條邊的連通圖测暗，這里采用后者實現(xiàn)。
在深度搜索遍歷的過程中磨澡，同時對遍歷過的頂點和邊數(shù)計數(shù)碗啄，當(dāng)全部頂點都遍歷過且邊數(shù)為2?(n?1)2?(n?1)時，這個圖就是一棵樹稳摄，否則不是一棵樹稚字。
2）計算圖的邊數(shù)
無向圖的任何2個不同的節(jié)點都可以有一條鄰接邊.
結(jié)點個數(shù)為m,圖中的邊數(shù)為從m中取2的組合數(shù),為 m(m-1)/2.
3）找到兩個頂點之間的最短路徑
迪杰斯特拉算法計算的是有向網(wǎng)中的某個頂點到其余所有頂點的最短路徑；弗洛伊德算法計算的是任意兩頂點之間的最短路徑厦酬。
迪杰斯特拉算法解決的是從網(wǎng)中的一個頂點到所有其它頂點之間的最短路徑胆描，算法整體的時間復(fù)雜度為O(n2)。但是如果需要求任意兩頂點之間的最短路徑仗阅，使用迪杰斯特拉算法雖然最終雖然也能解決問題昌讲，但是大材小用，相比之下使用弗洛伊德算法解決此類問題會更合適减噪。
迪杰斯特拉算法的解決思路是：以每一個頂點為源點短绸，執(zhí)行迪杰斯特拉算法。這樣可以求得每一對頂點之間的最短路徑筹裕。
弗洛伊德的核心思想是：對于網(wǎng)中的任意兩個頂點（例如頂點 A 到頂點 B）來說醋闭，之間的最短路徑不外乎有 2 種情況：
1、直接從頂點 A 到頂點 B 的弧的權(quán)值為頂點 A 到頂點 B 的最短路徑朝卒；
2证逻、從頂點 A 開始，經(jīng)過若干個頂點抗斤，最終達到頂點 B囚企，期間經(jīng)過的弧的權(quán)值和為頂點 A 到頂點 B 的最短路徑丈咐。
字典樹（這是一種高效的樹形結(jié)構(gòu)，但值得單獨說明）
字典樹洞拨，也稱為“前綴樹”扯罐，是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)，對于解決字符串相關(guān)問題非常有效烦衣。它能夠提供快速檢索歹河，主要用于搜索字典中的單詞，在搜索引擎中自動提供建議花吟，甚至被用于IP的路由秸歧。
以下是在字典樹中存儲三個單詞“top”，“so”和“their”的例子：
這些單詞以頂部到底部的方式存儲衅澈，其中綠色節(jié)點“p”键菱，“s”和“r”分別表示“top”，“thus”和“theirs”的底部今布。
面試中關(guān)于字典樹的常見問題
計算字典樹中的總單詞數(shù)
打印存儲在字典樹中的所有單詞
使用字典樹對數(shù)組的元素進行排序
使用字典樹從字典中形成單詞
構(gòu)建T9字典（字典樹+ DFS ）
散列表（哈希表）
哈希法（Hashing）是一個用于唯一標(biāo)識對象并將每個對象存儲在一些預(yù)先計算的唯一索引（稱為“鍵（key）”）中的過程经备。因此，對象以鍵值對的形式存儲部默，這些鍵值對的集合被稱為“字典”侵蒙。可以使用鍵搜索每個對象傅蹂》坠耄基于哈希法有很多不同的數(shù)據(jù)結(jié)構(gòu)，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表份蝴。
哈希表通常使用數(shù)組實現(xiàn)犁功。
散列數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個因素：
哈希函數(shù)
哈希表的大小
碰撞處理方法
面試中關(guān)于哈希結(jié)構(gòu)的常見問題：
在數(shù)組中查找對稱鍵值對
追蹤遍歷的完整路徑
查找數(shù)組是否是另一個數(shù)組的子集
檢查給定的數(shù)組是否不相交
容易考察的幾個應(yīng)用問題
數(shù)據(jù)結(jié)構(gòu)部分：
約瑟夫環(huán) 循環(huán)鏈表（雙向循環(huán)鏈表）
迷宮游戲（圖--迪杰斯特拉算法和弗洛伊德算法）
八皇后問題（回溯法）
漢諾塔問題（遞歸問題）
出入口為一個的停車場問題（棧、隊列）
具體筆面試題（提高版）：
說說紅黑樹婚夫？及其與AVL樹對比
答：路徑浸卦，紅節(jié)點的左右子樹一定為黑，根節(jié)點一定為黑案糙，葉節(jié)點（nul）節(jié)點必須為黑镐躲，節(jié)點不是紅就是黑。與AVL樹的對比侍筛，降低了高度的嚴(yán)格性對時間進行了優(yōu)化，而AVL樹的嚴(yán)格高度平衡耗費了更多的時間,這種時間主要在插入和刪除過程中撒穷，但是如果查詢操作特別多而動態(tài)調(diào)整很少那么AVL是更好的選擇匣椰，否則紅黑樹更好。哈希沖突端礼？怎樣解決禽笑？
答：
開地址法入录，鏈地址法，再哈希法佳镜，公共溢出區(qū)
3.（平衡多路查找樹）b樹僚稿，b+樹，b樹蟀伸？
答：
當(dāng)數(shù)據(jù)非常多平衡二叉查找樹會比較深蚀同，就會出現(xiàn)很多io操作，非常耗時性能達到瓶頸啊掏，所以出現(xiàn)了平衡多路查找樹蠢络，b樹數(shù)據(jù)信息分布在整棵樹上，b+樹是數(shù)據(jù)信息分布在葉子節(jié)點上迟蜜，而且葉子節(jié)點連成一個鏈表（例如跳表）刹孔，適合范圍性數(shù)據(jù)查找，b樹利用了b+樹的空指針建立了兄弟節(jié)點娜睛，用于分裂節(jié)點的時候（類似于線索二叉樹）
位圖法髓霞，布隆過濾器進行排序和去重和前top？
答：
都可以進行去重畦戒，位圖使用1個或者布隆過濾器使用了多個哈希函數(shù)方库，進行排序位圖可以實現(xiàn)（申請n/32+1個大小的bytes數(shù)組，每32個位置代表int數(shù)組的1個位置兢交，0-31薪捍，32-63....，數(shù)字如果出現(xiàn)位置就置1）配喳，前top問題：小頂堆酪穿，分治patiction，更精妙的是冒泡排序（每次可確定一個當(dāng)前的最大值）晴裹。中綴表達式轉(zhuǎn)為后綴表達式被济，前綴表達式？
答：
轉(zhuǎn)化為后綴表達式從前向后涧团，轉(zhuǎn)化為前綴表達式從后向前（轉(zhuǎn)化為了后綴表達式求解）只磷，遇見數(shù)字直接加入字符串，遇見左括號直接入棧泌绣，右括號彈棧直到左括號出現(xiàn)钮追，遇見符號如果棧尾的符號優(yōu)先級小那么直接入棧，否則符號出棧直到棧尾元素優(yōu)先級小于此符號阿迈，特殊的左括號優(yōu)先級最小元媚。堆的插入和刪除？
答：
插入放入堆尾進行從底向上進行調(diào)整，刪除的那個元素與堆底元素刊棕，然后對交換上去的元素向下進行調(diào)整進行堆化堆和棧的區(qū)別炭晒？
答：空間分配，棧是自動分配甥角，堆是需要手動申請网严，數(shù)據(jù)類型先進后出的線性結(jié)構(gòu)，樹形結(jié)構(gòu)嗤无。對一千萬個整數(shù)排序,整數(shù)范圍[-1000,1000]間,如何排序最快?
先映射到正整數(shù)上震束，計算每個位置上的個數(shù)構(gòu)建一個計數(shù)信息表，在通過計數(shù)信息表構(gòu)建一個位置表（比如：數(shù)值1000有10個前1000的數(shù)有200個翁巍，那么數(shù)值1000的位置信息表對應(yīng)的值就是205個）驴一，從后向前便利數(shù)字在對應(yīng)的位置表上個數(shù)減一（從前向后處理不方便）。第k大的數(shù)灶壶？
答：
快排可以轉(zhuǎn)化為前k大的問題肝断，構(gòu)建最小堆k個元素最后堆頂元素就是。最小生成樹的prim和kruskal驰凛？
答：
prim每次連接頂點與樹之間的最小距離（選最短的頂點胸懈，需要優(yōu)先級隊列），kruskal每次給頂點加最小權(quán)重的邊只要不構(gòu)成環(huán)（選最短的邊恰响，使用并查集主要利用遞歸實現(xiàn)路徑壓縮以及頭目合并）趣钱。億級文件進行取交集？
答：布隆過濾器進行判重來達到查找交集的效果但是會有小小的損失因為判定為重復(fù)可能不是重復(fù)因為出現(xiàn)了沖突但是判定為不是重復(fù)就一定不重復(fù)要是真要實現(xiàn)完全精準(zhǔn)查在進行暴力檢查也可以如何快速找出兩個隊列中相同的元素胚宦，假設(shè)隊列的長度非常大首有？
答：
1、直接hash枢劝，對一個隊列元素經(jīng)過hash進行存儲井联，用另外一個隊列計算hash值然后對比！（空間消耗大）
2您旁、布隆過濾器烙常，創(chuàng)建位圖只有0/1，生成多個hash函數(shù)每個函數(shù)計算一個值進行映射到k個位置記為1鹤盒，然后一直這樣處理即可如果映射到的值已經(jīng)全是1了那就是重復(fù)的蚕脏，但是會有誤判的，不是重復(fù)的那么一定不是重復(fù)的是重復(fù)的可能實際上不重復(fù)（hash碰撞）Ｕ炀狻（堆空間進行優(yōu)化）驼鞭。
13.Dijkstra和最小生成樹prim？
答：
prim是每次選取一個節(jié)點到樹的距離最短生成樹尺碰，是針對整個圖來說構(gòu)建一個消費最少的結(jié)構(gòu)挣棕。
dijkstra是單源點最短路徑是每次選取一個距離源點最短的節(jié)點以此為節(jié)點進行更新每次都會以此節(jié)點為基礎(chǔ)確定一個距離源點的未確定最短路徑節(jié)點的最短路徑汇竭。（適應(yīng)于有向圖權(quán)重為正的結(jié)構(gòu)）。
存儲二叉樹的結(jié)構(gòu)有哪些穴张？各自的特點是什么？
答：
順序存儲可能會浪費空間(在非完全二叉樹的時候)两曼，但是讀取某個指定的節(jié)點的時候效率比較高O(0)
鏈?zhǔn)酱鎯ο鄬Χ鏄浔容^大的時候浪費空間較少皂甘，但是讀取某個指定節(jié)點的時候效率偏低O(nlogn)說說關(guān)于動態(tài)規(guī)劃的思想？
答：動態(tài)規(guī)劃簡稱就是DP悼凑，其思想主要在于偿枕，本質(zhì)上是一種劃分子問題的算法，站在任何一個子問題的處理上看户辫，當(dāng)前子問題的提出都要依據(jù)現(xiàn)有的類似結(jié)論渐夸，而當(dāng)前問題的結(jié)論是后 面問題求解的鋪墊。任何DP都是基于存儲的算法渔欢，核心是狀態(tài)轉(zhuǎn)移方程墓塌；
比較經(jīng)典的題目就是：“01”背包問題和矩陣相乘問題；優(yōu)先隊列奥额，阻塞隊列苫幢，優(yōu)先阻塞隊列等多種隊列的區(qū)別？
答：
同：隊列都不能插入null元素垫挨；
不同：
優(yōu)先隊列(PriorityQueue)：就是在隊列中根據(jù)某一個特征值自動進行排序韩肝，優(yōu)先隊列分為兩種，最大優(yōu)先隊列和最小優(yōu)先隊列九榔，優(yōu)先隊列的一個最大特性就是哀峻，當(dāng)插入元素或者刪除元素的時候，隊列會自動進行調(diào)整哲泊，保證隊首元素一定是優(yōu)先權(quán)最大/最小剩蟀。正是由于優(yōu)先隊列的這種特性，優(yōu)先隊列可以被用在很多地方攻旦，比如作業(yè)調(diào)度喻旷，進程調(diào)度等。
（1）其底層是通過堆來實現(xiàn)（默認(rèn)是小堆）牢屋；----具體是小堆還是大堆且预，需要根據(jù)隊列元素中的比較器來判斷
（2）就是會對插入的元素進行排序（可以根據(jù)隊列的元素內(nèi)容的comparable比較器的設(shè)置進行自定義，默認(rèn)是用的從小到大）
（3）不允許插入null元素
阻塞隊列（BlockingQueue）：是一個支持兩個附加操作的隊列烙无。這兩個附加的操作是：在隊列為空時锋谐，獲取元素的線程會等待隊列變?yōu)榉强铡．?dāng)隊列滿時截酷，存儲元素的線程會等待隊列可用涮拗。阻塞隊列常用于生產(chǎn)者和消費者的場景，生產(chǎn)者是往隊列里添加元素的線程，消費者是從隊列里拿元素的線程三热。阻塞隊列就是生產(chǎn)者存放元素的容器鼓择，而消費者也只從容器里拿元素。
其實現(xiàn)類有如下幾種：
優(yōu)先阻塞隊列(PriorityBlockingQueue)：（1）其是阻塞隊列的一個實現(xiàn)類（2）其底層與優(yōu)先隊列一致就漾，不過其內(nèi)部進行了加鎖處理（3）不允許插入null元素呐能。
