數(shù)據(jù)結(jié)構(gòu)
鏈表
鏈表是一種由節(jié)點(diǎn)（Node）組成的線性數(shù)據(jù)集合，每個(gè)節(jié)點(diǎn)通過指針指向下一個(gè)節(jié)點(diǎn)株憾。它是一種由節(jié)點(diǎn)組成凑保，并能用于表示序列的數(shù)據(jù)結(jié)構(gòu)。
單鏈表：每個(gè)節(jié)點(diǎn)僅指向下一個(gè)節(jié)點(diǎn)享钞，最后一個(gè)節(jié)點(diǎn)指向空（null）揍诽。
雙鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針p，n栗竖。p指向前一個(gè)節(jié)點(diǎn)暑脆，n指向下一個(gè)節(jié)點(diǎn)；最后一個(gè)節(jié)點(diǎn)指向空狐肢。
循環(huán)鏈表：每個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)添吗，最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)。
時(shí)間復(fù)雜度：
索引：O(n)
查找：O(n)
插入：O(1)
刪除：O(1)
棧
棧是一個(gè)元素集合份名，支持兩個(gè)基本操作：push用于將元素壓入棧碟联，pop用于刪除棧頂元素妓美。
后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（Last In First Out, LIFO）
時(shí)間復(fù)雜度
索引：O(n)
查找：O(n)
插入：O(1)
刪除：O(1)
隊(duì)列
隊(duì)列是一個(gè)元素集合，支持兩種基本操作：enqueue 用于添加一個(gè)元素到隊(duì)列鲤孵，dequeue 用于刪除隊(duì)列中的一個(gè)元素壶栋。
先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（First In First Out, FIFO）。
時(shí)間復(fù)雜度
索引：O(n)
查找：O(n)
插入：O(1)
刪除：O(1)
樹
樹是無向普监、聯(lián)通的無環(huán)圖贵试。
二叉樹
二叉樹是一個(gè)樹形數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多可以有兩個(gè)子節(jié)點(diǎn)凯正，稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)毙玻。
滿二叉樹（Full Tree）：二叉樹中的每個(gè)節(jié)點(diǎn)有 0 或者 2 個(gè)子節(jié)點(diǎn)。
完美二叉樹（Perfect Binary）：二叉樹中的每個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)廊散，并且所有的葉子節(jié)點(diǎn)的深度是一樣的桑滩。
完全二叉樹：二叉樹中除最后一層外其他各層的節(jié)點(diǎn)數(shù)均達(dá)到最大值，最后一層的節(jié)點(diǎn)都連續(xù)集中在最左邊允睹。
二叉查找樹
二叉查找樹（BST）是一種二叉樹运准。其任何節(jié)點(diǎn)的值都大于等于左子樹中的值，小于等于右子樹中的值擂找。
時(shí)間復(fù)雜度
索引：O(log(n))
查找：O(log(n))
插入：O(log(n))
刪除：O(log(n))
字典樹
字典樹戳吝，又稱為基數(shù)樹或前綴樹，是一種用于存儲(chǔ)鍵值為字符串的動(dòng)態(tài)集合或關(guān)聯(lián)數(shù)組的查找樹贯涎。樹中的節(jié)點(diǎn)并不直接存儲(chǔ)關(guān)聯(lián)鍵值听哭，而是該節(jié)點(diǎn)在樹中的位置決定了其關(guān)聯(lián)鍵值。一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都有相同的前綴塘雳，根節(jié)點(diǎn)則是空字符串陆盘。
樹狀數(shù)組
樹狀數(shù)組焚鲜，又稱為二進(jìn)制索引樹（Binary Indexed Tree危号，BIT），其概念上是樹扫步，但以數(shù)組實(shí)現(xiàn)妻顶。數(shù)組中的下標(biāo)代表樹中的節(jié)點(diǎn)酸员，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)或子節(jié)點(diǎn)的下標(biāo)可以通過位運(yùn)算獲得。數(shù)組中的每個(gè)元素都包含了預(yù)計(jì)算的區(qū)間值之和讳嘱，在整個(gè)樹更新的過程中幔嗦，這些計(jì)算的值也同樣會(huì)被更新。
時(shí)間復(fù)雜度
區(qū)間求和：O(log(n))
更新：O(log(n))
線段樹
線段樹是用于存儲(chǔ)區(qū)間和線段的樹形數(shù)據(jù)結(jié)構(gòu)沥潭。它允許查找一個(gè)節(jié)點(diǎn)在若干條線段中出現(xiàn)的次數(shù)邀泉。
時(shí)間復(fù)雜度
區(qū)間查找：O(log(n))
更新：O(log(n))
堆
堆是一種基于樹的滿足某些特性的數(shù)據(jù)結(jié)構(gòu)：整個(gè)堆中的所有父子節(jié)點(diǎn)的鍵值都滿足相同的排序條件。堆分為最大堆和最小堆。在最大堆中汇恤，父節(jié)點(diǎn)的鍵值永遠(yuǎn)大于等于所有子節(jié)點(diǎn)的鍵值庞钢，根節(jié)點(diǎn)的鍵值是最大的。最小堆中因谎，父節(jié)點(diǎn)的鍵值永遠(yuǎn)小于等于所有子節(jié)點(diǎn)的鍵值基括，根節(jié)點(diǎn)的鍵值是最小的。
時(shí)間復(fù)雜度
索引：O(log(n))
查找：O(log(n))
插入：O(log(n))
刪除：O(log(n))
刪除最大值/最小值：O(1)
哈希
哈希用于將任意長度的數(shù)據(jù)映射到固定長度的數(shù)據(jù)财岔。哈希函數(shù)的返回值被稱為哈希值阱穗、哈希碼或者哈希。如果不同的主鍵得到相同的哈希值使鹅，則發(fā)生了沖突。
Hash Map：hash map是一個(gè)存儲(chǔ)鍵值間關(guān)系的數(shù)據(jù)結(jié)構(gòu)昌抠。HashMap 通過哈希函數(shù)將鍵轉(zhuǎn)化為桶或者槽中的下標(biāo)患朱，從而便于指定值的查找。
沖突解決
鏈地址法（Separate Chaining）：在鏈地址法中炊苫，每個(gè)桶（bucket）是相互獨(dú)立的裁厅，每一個(gè)索引對應(yīng)一個(gè)元素列表。處理HashMap 的時(shí)間就是查找桶的時(shí)間（常量）與遍歷列表元素的時(shí)間之和侨艾。
開放地址法（Open Addressing）：在開放地址方法中执虹，當(dāng)插入新值時(shí)，會(huì)判斷該值對應(yīng)的哈希桶是否存在唠梨，如果存在則根據(jù)某種算法依次選擇下一個(gè)可能的位置袋励，直到找到一個(gè)未被占用的地址。開放地址即某個(gè)元素的位置并不永遠(yuǎn)由其哈希值決定当叭。
圖
圖是G =（V茬故，E）的有序?qū)Γ浒旤c(diǎn)或節(jié)點(diǎn)的集合 V 以及邊或弧的集合E蚁鳖，其中E包括了兩個(gè)來自V的元素（即邊與兩個(gè)頂點(diǎn)相關(guān)聯(lián) 磺芭，并且該關(guān)聯(lián)為這兩個(gè)頂點(diǎn)的無序?qū)Γ?/p>
無向圖：圖的鄰接矩陣是對稱的，因此如果存在節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的邊醉箕，那節(jié)點(diǎn) v 到節(jié)點(diǎn) u 的邊也一定存在钾腺。
有向圖：圖的鄰接矩陣不是對稱的。因此如果存在節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的邊并不意味著一定存在節(jié)點(diǎn) v 到節(jié)點(diǎn) u 的邊讥裤。
算法
排序
快速排序
穩(wěn)定：否
時(shí)間復(fù)雜度
最優(yōu)：O(nlog(n))
最差：O(n^2)
平均：O(nlog(n))
合并排序
合并排序是一種分治算法放棒。這個(gè)算法不斷地將一個(gè)數(shù)組分為兩部分，分別對左子數(shù)組和右子數(shù)組排序坞琴，然后將兩個(gè)數(shù)組合并為新的有序數(shù)組哨查。
穩(wěn)定：是
時(shí)間復(fù)雜度：
最優(yōu)：O(nlog(n))
最差：O(nlog(n))
平均：O(nlog(n))
正在上傳...取消
桶排序
桶排序是一種將元素分到一定數(shù)量的桶中的排序算法。每個(gè)桶內(nèi)部采用其他算法排序剧辐，或遞歸調(diào)用桶排序寒亥。
時(shí)間復(fù)雜度
最優(yōu)：Ω(n + k)
最差: O(n^2)
平均：Θ(n + k)
基數(shù)排序
基數(shù)排序類似于桶排序邮府，將元素分發(fā)到一定數(shù)目的桶中。不同的是溉奕，基數(shù)排序在分割元素之后沒有讓每個(gè)桶單獨(dú)進(jìn)行排序褂傀，而是直接做了合并操作。
時(shí)間復(fù)雜度
最優(yōu)：Ω(nk)
最差: O(nk)
平均：Θ(nk)
圖算法
深度優(yōu)先搜索
深度優(yōu)先搜索是一種先遍歷子節(jié)點(diǎn)而不回溯的圖遍歷算法加勤。
時(shí)間復(fù)雜度：O(|V| + |E|)
廣度優(yōu)先搜索
廣度優(yōu)先搜索是一種先遍歷鄰居節(jié)點(diǎn)而不是子節(jié)點(diǎn)的圖遍歷算法仙辟。
時(shí)間復(fù)雜度：O(|V| + |E|)
拓?fù)渑判?/b>
拓?fù)渑判蚴怯邢驁D節(jié)點(diǎn)的線性排序。對于任何一條節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的邊鳄梅，u 的下標(biāo)先于 v叠国。
時(shí)間復(fù)雜度：O(|V| + |E|)
Dijkstra算法
Dijkstra 算法是一種在有向圖中查找單源最短路徑的算法。
時(shí)間復(fù)雜度：O(|V|^2)
Bellman-Ford算法
Bellman-Ford是一種在帶權(quán)圖中查找單一源點(diǎn)到其他節(jié)點(diǎn)最短路徑的算法戴尸。
雖然時(shí)間復(fù)雜度大于 Dijkstra 算法粟焊，但它可以處理包含了負(fù)值邊的圖。
時(shí)間復(fù)雜度：
最優(yōu)：O(|E|)
最差：O(|V||E|)
Floyd-Warshall 算法
Floyd-Warshall算法是一種在無環(huán)帶權(quán)圖中尋找任意節(jié)點(diǎn)間最短路徑的算法孙蒙。
該算法執(zhí)行一次即可找到所有節(jié)點(diǎn)間的最短路徑（路徑權(quán)重和）项棠。
時(shí)間復(fù)雜度：
最優(yōu)：O(|V|^3)
最差：O(|V|^3)
平均：O(|V|^3)
最小生成樹算法
最小生成樹算法是一種在無向帶權(quán)圖中查找最小生成樹的貪心算法。換言之挎峦，最小生成樹算法能在一個(gè)圖中找到連接所有節(jié)點(diǎn)的邊的最小子集香追。
時(shí)間復(fù)雜度：O(|V|^2)
Kruskal 算法
Kruskal算法也是一個(gè)計(jì)算最小生成樹的貪心算法，但在 Kruskal 算法中坦胶，圖不一定是連通的透典。
時(shí)間復(fù)雜度：O(|E|log|V|)
貪心算法
貪心算法總是做出在當(dāng)前看來最優(yōu)的選擇，并希望最后整體也是最優(yōu)的顿苇。
使用貪心算法可以解決的問題必須具有如下兩種特性：
最優(yōu)子結(jié)構(gòu)
問題的最優(yōu)解包含其子問題的最優(yōu)解掷匠。
貪心選擇
每一步的貪心選擇可以得到問題的整體最優(yōu)解。
實(shí)例-硬幣選擇問題
給定期望的硬幣總和為 V 分岖圈，以及 n 種硬幣讹语，即類型是 i 的硬幣共有 coinValue[i] 分，i的范圍是 [0…n – 1]蜂科。假設(shè)每種類型的硬幣都有無限個(gè)顽决，求解為使和為 V 分最少需要多少硬幣？
硬幣：便士（1美分）导匣，鎳（5美分）才菠，一角（10美分），四分之一（25美分）贡定。
假設(shè)總和 V 為41,赋访。我們可以使用貪心算法查找小于或者等于 V 的面值最大的硬幣，然后從 V 中減掉該硬幣的值，如此重復(fù)進(jìn)行蚓耽。
V = 41 | 使用了0個(gè)硬幣
V = 16 | 使用了1個(gè)硬幣(41 – 25 = 16)
V = 6 | 使用了2個(gè)硬幣(16 – 10 = 6)
V = 1 | 使用了3個(gè)硬幣(6 – 5 = 1)
V = 0 | 使用了4個(gè)硬幣(1 – 1 = 0)
位運(yùn)算
位運(yùn)算即在比特級(jí)別進(jìn)行操作的技術(shù)渠牲。使用位運(yùn)算技術(shù)可以帶來更快的運(yùn)行速度與更小的內(nèi)存使用。
測試第 k 位：s & (1 << k);
設(shè)置第k位：s |= (1 << k);
關(guān)閉第k位：s &= ~(1 << k);
切換第k位：s ^= (1 << k);
乘以2n：s << n;
除以2n：s >> n;
交集：s & t;
并集：s | t;
減法：s & ~t;
提取最小非0位：s & (-s);
提取最小0位：~s & (s + 1);
交換值：x ^= y; y ^= x; x ^= y;
運(yùn)行時(shí)分析
大 O 表示
大 O 表示用于表示某個(gè)算法的上界步悠，用于描述最壞的情況签杈。
小 O 表示
小 O 表示用于描述某個(gè)算法的漸進(jìn)上界，二者逐漸趨近鼎兽。
大 Ω 表示
大 Ω 表示用于描述某個(gè)算法的漸進(jìn)下界答姥。
小 ω 表示
小 ω 表示用于描述某個(gè)算法的漸進(jìn)下界，二者逐漸趨近谚咬。
Theta Θ 表示
Theta Θ 表示用于描述某個(gè)算法的確界鹦付，包括最小上界和最大下界。
以為這就結(jié)束了择卦？No, 這些知識(shí)不僅僅是停留在理論睁壁，還有代碼實(shí)現(xiàn)。
這其實(shí)是來自 GitHub 的一個(gè) repo：https://github.com/kdn251/interviews
除了上述算法和數(shù)據(jù)結(jié)知識(shí)外互捌，其中還有推薦了一些算法練習(xí)網(wǎng)站、視頻教程行剂、面試寶典秕噪、Google、Facebook 等知名公司面試題及解答代碼厚宰。下載實(shí)例代碼或者收藏練習(xí)網(wǎng)站腌巾。
