|
幾乎所有的問題都需要面試者對數(shù)據(jù)結(jié)構(gòu)有深刻的理解。無論你是初入職場的新兵(剛從大學(xué)或者編程培訓(xùn)班畢業(yè))，還是擁有幾十年經(jīng)驗(yàn)的職場老鳥。 即便是對于一些非?；A(chǔ)的工作來說，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是必須的。那么，就讓我們先從一些基本概念開始入手。 什么是數(shù)據(jù)結(jié)構(gòu)? 簡單地說，數(shù)據(jù)結(jié)構(gòu)是以某種特定的布局方式存儲數(shù)據(jù)的容器。這種“布局方式”決定了數(shù)據(jù)結(jié)構(gòu)對于某些操作是高效的，而對于其他操作則是低效的。首先我們需要理解各種數(shù)據(jù)結(jié)構(gòu)，才能在處理實(shí)際問題時(shí)選取最合適的數(shù)據(jù)結(jié)構(gòu)。 為什么我們需要數(shù)據(jù)結(jié)構(gòu)? 數(shù)據(jù)是計(jì)算機(jī)科學(xué)當(dāng)中最關(guān)鍵的實(shí)體，而數(shù)據(jù)結(jié)構(gòu)則可以將數(shù)據(jù)以某種組織形式存儲，因此，數(shù)據(jù)結(jié)構(gòu)的價(jià)值不言而喻。 無論你以何種方式解決何種問題，你都需要處理數(shù)據(jù)——無論是涉及員工薪水、股票價(jià)格、購物清單，還是只是簡單的電話簿問題。 數(shù)據(jù)需要根據(jù)不同的場景，按照特定的格式進(jìn)行存儲。有很多數(shù)據(jù)結(jié)構(gòu)能夠滿足以不同格式存儲數(shù)據(jù)的需求。 常見的數(shù)據(jù)結(jié)構(gòu) 首先列出一些最常見的數(shù)據(jù)結(jié)構(gòu)，我們將逐一說明： · 數(shù)組 · 棧 · 隊(duì)列 · 鏈表 · 樹 · 圖 · 字典樹(這是一種高效的樹形結(jié)構(gòu)，但值得單獨(dú)說明) · 散列表(哈希表) 數(shù)組 數(shù)組是最簡單、也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)。棧、隊(duì)列等其他數(shù)據(jù)結(jié)構(gòu)均由數(shù)組演變而來。 每個(gè)數(shù)據(jù)元素都關(guān)聯(lián)一個(gè)正數(shù)值，我們稱之為索引，它表明數(shù)組中每個(gè)元素所在的位置。大部分語言將初始索引定義為零。 以下是數(shù)組的兩種類型： · 一維數(shù)組(如上所示) · 多維數(shù)組(數(shù)組的數(shù)組) 數(shù)組的基本操作 · Insert——在指定索引位置插入一個(gè)元素 · Get——返回指定索引位置的元素 · Delete——刪除指定索引位置的元素 · Size——得到數(shù)組所有元素的數(shù)量 面試中關(guān)于數(shù)組的常見問題 · 尋找數(shù)組中第二小的元素 · 找到數(shù)組中第一個(gè)不重復(fù)出現(xiàn)的整數(shù) · 合并兩個(gè)有序數(shù)組 · 重新排列數(shù)組中的正值和負(fù)值 棧 著名的撤銷操作幾乎遍布任意一個(gè)應(yīng)用。但你有沒有思考過它是如何工作的呢?這個(gè)問題的解決思路是按照將最后的狀態(tài)排列在先的順序，在內(nèi)存中存儲歷史工作狀態(tài)。這沒辦法用數(shù)組實(shí)現(xiàn)。但有了棧，這就變得非常方便了。 可以把棧想象成一列垂直堆放的書。為了拿到中間的書，你需要移除放置在這上面的所有書。這就是LIFO(后進(jìn)先出)的工作原理。 棧的基本操作 · Push——在頂部插入一個(gè)元素 · Pop——返回并移除棧頂元素 · isEmpty——如果棧為空，則返回true · Top——返回頂部元素，但并不移除它 面試中關(guān)于棧的常見問題 · 使用棧計(jì)算后綴表達(dá)式 · 對棧的元素進(jìn)行排序 · 判斷表達(dá)式是否括號平衡 隊(duì)列 與棧相似，隊(duì)列是另一種順序存儲元素的線性數(shù)據(jù)結(jié)構(gòu)。棧與隊(duì)列的最大差別在于棧是LIFO(后進(jìn)先出)，而隊(duì)列是FIFO，即先進(jìn)先出。 隊(duì)列的基本操作 · Enqueue()?——?在隊(duì)列尾部插入元素 · Dequeue()?——移除隊(duì)列頭部的元素 · isEmpty()——如果隊(duì)列為空，則返回true · Top()?——返回隊(duì)列的第一個(gè)元素 面試中關(guān)于隊(duì)列的常見問題 · 使用隊(duì)列表示棧 · 對隊(duì)列的前k個(gè)元素倒序 · 使用隊(duì)列生成從1到n的二進(jìn)制數(shù) 鏈表 鏈表是另一個(gè)重要的線性數(shù)據(jù)結(jié)構(gòu)，乍一看可能有點(diǎn)像數(shù)組，但在內(nèi)存分配、內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)插入和刪除的基本操作方面均有所不同。 鏈表就像一個(gè)節(jié)點(diǎn)鏈，其中每個(gè)節(jié)點(diǎn)包含著數(shù)據(jù)和指向后續(xù)節(jié)點(diǎn)的指針。 鏈表還包含一個(gè)頭指針，它指向鏈表的第一個(gè)元素，但當(dāng)列表為空時(shí)，它指向null或無具體內(nèi)容。 鏈表一般用于實(shí)現(xiàn)文件系統(tǒng)、哈希表和鄰接表。 鏈表內(nèi)部結(jié)構(gòu) 鏈表包括以下類型： · 單鏈表(單向) · 雙向鏈表(雙向) 鏈表的基本操作： · InsertAtEnd - 在鏈表的末尾插入指定元素 · InsertAtHead - 在鏈接列表的開頭/頭部插入指定元素 · Delete - 從鏈接列表中刪除指定元素 · DeleteAtHead - 刪除鏈接列表的第一個(gè)元素 · Search - 從鏈表中返回指定元素 · isEmpty - 如果鏈表為空，則返回true 面試中關(guān)于鏈表的常見問題 · 反轉(zhuǎn)鏈表 · 檢測鏈表中的循環(huán) · 返回鏈表倒數(shù)第N個(gè)節(jié)點(diǎn) · 刪除鏈表中的重復(fù)項(xiàng) 圖 圖是一組以網(wǎng)絡(luò)形式相互連接的節(jié)點(diǎn)。節(jié)點(diǎn)也稱為頂點(diǎn)。 一對節(jié)點(diǎn)(x，y)稱為邊(edge)，表示頂點(diǎn)x連接到頂點(diǎn)y。邊可以包含權(quán)重/成本，顯示從頂點(diǎn)x到y(tǒng)所需的成本。 圖的類型 · 無向圖 · 有向圖 在程序語言中，圖可以用兩種形式表示： · 鄰接矩陣 · 鄰接表 常見圖遍歷算法 · 廣度優(yōu)先搜索 · 深度優(yōu)先搜索 面試中關(guān)于圖的常見問題 · 實(shí)現(xiàn)廣度和深度優(yōu)先搜索 · 檢查圖是否為樹 · 計(jì)算圖的邊數(shù) · 找到兩個(gè)頂點(diǎn)之間的最短路徑 樹 樹形結(jié)構(gòu)是一種層級式的數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)(節(jié)點(diǎn))和連接它們的邊組成。 樹類似于圖，但區(qū)分樹和圖的重要特征是樹中不存在環(huán)路。 樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法，它可以提供解決問題的有效存儲機(jī)制。 樹數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語 · Root - 根節(jié)點(diǎn) · Parent - 父節(jié)點(diǎn) · Child - 子節(jié)點(diǎn) · Leaf - 葉子節(jié)點(diǎn) · Sibling - 兄弟節(jié)點(diǎn) 以下是樹形結(jié)構(gòu)的主要類型 · N元樹 · 平衡樹 · 二叉樹 · 二叉搜索樹 · AVL樹 · 紅黑樹 · 2-3樹 其中，二叉樹和二叉搜索樹是最常用的樹。 面試中關(guān)于樹結(jié)構(gòu)的常見問題 · 求二叉樹的高度 · 在二叉搜索樹中查找第k個(gè)最大值 · 查找與根節(jié)點(diǎn)距離k的節(jié)點(diǎn) · 在二叉樹中查找給定節(jié)點(diǎn)的祖先節(jié)點(diǎn) 字典樹 字典樹，也稱為“前綴樹”，是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)，對于解決字符串相關(guān)問題非常有效。它能夠提供快速檢索，主要用于搜索字典中的單詞，在搜索引擎中自動提供建議，甚至被用于IP的路由。 面試中關(guān)于字典樹的常見問題 · 計(jì)算字典樹中的總單詞數(shù) · 打印存儲在字典樹中的所有單詞 · 使用字典樹對數(shù)組的元素進(jìn)行排序 · 使用字典樹從字典中形成單詞 · 構(gòu)建T9字典(字典樹+ DFS ) 哈希表 哈希法(Hashing)是一個(gè)用于唯一標(biāo)識對象并將每個(gè)對象存儲在一些預(yù)先計(jì)算的唯一索引(稱為“鍵(key)”)中的過程。因此，對象以鍵值對的形式存儲，這些鍵值對的集合被稱為“字典”?？梢允褂面I搜索每個(gè)對象?；诠７ㄓ泻芏嗖煌臄?shù)據(jù)結(jié)構(gòu)，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表。哈希表通常使用數(shù)組實(shí)現(xiàn)。 散列數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個(gè)因素 · 哈希函數(shù) · 哈希表的大小 · 碰撞處理方法 面試中關(guān)于哈希結(jié)構(gòu)的常見問題 · 在數(shù)組中查找對稱鍵值對 · 追蹤遍歷的完整路徑 · 查找數(shù)組是否是另一個(gè)數(shù)組的子集 · 檢查給定的數(shù)組是否不相交 |
|
|
