- 在線練習
- 在線編程面試
- 數(shù)據(jù)結構
- 算法
- 貪心算法
- 位運算
- 復雜度分析
- 視頻教程
- 面試寶典
- 計算機科學資訊
- 文件結構
在線練習
- LeetCode
- Virtual Judge
- CareerCup
- HackerRank
- CodeFights
- Kattis
- HackerEarth
- Codility
- Code Forces
- Code Chef
- Sphere Online Judge – SPOJ
在線編程面試
數(shù)據(jù)結構
鏈表
- 鏈表是一種由節(jié)點（Node）組成的線性數(shù)據(jù)集合，每個節(jié)點通過指針指向下一個節(jié)點。它是一種由節(jié)點組成货抄，并能用于表示序列的數(shù)據(jù)結構奠宜。
- 單鏈表：每個節(jié)點僅指向下一個節(jié)點，最后一個節(jié)點指向空（null）威始。
- 雙鏈表：每個節(jié)點有兩個指針p涌哲，n。p指向前一個節(jié)點眷蚓，n指向下一個節(jié)點；最后一個節(jié)點指向空反番。
- 循環(huán)鏈表：每個節(jié)點指向下一個節(jié)點沙热，最后一個節(jié)點指向第一個節(jié)點。
- 時間復雜度：
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
棧
- 棧是一個元素集合罢缸，支持兩個基本操作：push用于將元素壓入棧篙贸，pop用于刪除棧頂元素。
- 后進先出的數(shù)據(jù)結構（Last In First Out, LIFO）
- 時間復雜度
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
隊列
- 隊列是一個元素集合枫疆，支持兩種基本操作：enqueue 用于添加一個元素到隊列爵川，dequeue 用于刪除隊列中的一個元素。
- 先進先出的數(shù)據(jù)結構（First In First Out, FIFO）息楔。
- 時間復雜度
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
樹
- 樹是無向寝贡、聯(lián)通的無環(huán)圖。
二叉樹
- 二叉樹是一個樹形數(shù)據(jù)結構值依，每個節(jié)點最多可以有兩個子節(jié)點圃泡，稱為左子節(jié)點和右子節(jié)點。
- 滿二叉樹（Full Tree）：二叉樹中的每個節(jié)點有 0 或者 2 個子節(jié)點愿险。
- 完美二叉樹（Perfect Binary）：二叉樹中的每個節(jié)點有兩個子節(jié)點颇蜡，并且所有的葉子節(jié)點的深度是一樣的。
- 完全二叉樹：二叉樹中除最后一層外其他各層的節(jié)點數(shù)均達到最大值，最后一層的節(jié)點都連續(xù)集中在最左邊澡匪。
二叉查找樹
- 二叉查找樹（BST）是一種二叉樹熔任。其任何節(jié)點的值都大于等于左子樹中的值，小于等于右子樹中的值唁情。
- 時間復雜度
- 索引：O(log(n))
- 查找：O(log(n))
- 插入：O(log(n))
- 刪除：O(log(n))
image
字典樹
- 字典樹疑苔，又稱為基數(shù)樹或前綴樹，是一種用于存儲鍵值為字符串的動態(tài)集合或關聯(lián)數(shù)組的查找樹甸鸟。樹中的節(jié)點并不直接存儲關聯(lián)鍵值惦费，而是該節(jié)點在樹中的位置決定了其關聯(lián)鍵值。一個節(jié)點的所有子節(jié)點都有相同的前綴抢韭，根節(jié)點則是空字符串薪贫。
image
樹狀數(shù)組
- 樹狀數(shù)組，又稱為二進制索引樹（Binary Indexed Tree刻恭，BIT）瞧省，其概念上是樹，但以數(shù)組實現(xiàn)鳍贾。數(shù)組中的下標代表樹中的節(jié)點鞍匾，每個節(jié)點的父節(jié)點或子節(jié)點的下標可以通過位運算獲得。數(shù)組中的每個元素都包含了預計算的區(qū)間值之和骑科，在整個樹更新的過程中橡淑，這些計算的值也同樣會被更新。
- 時間復雜度
- 區(qū)間求和：O(log(n))
- 更新：O(log(n))
image
線段樹
- 線段樹是用于存儲區(qū)間和線段的樹形數(shù)據(jù)結構咆爽。它允許查找一個節(jié)點在若干條線段中出現(xiàn)的次數(shù)。
- 時間復雜度
- 區(qū)間查找：O(log(n))
- 更新：O(log(n))
image
堆
- 堆是一種基于樹的滿足某些特性的數(shù)據(jù)結構：整個堆中的所有父子節(jié)點的鍵值都滿足相同的排序條件符糊。堆分為最大堆和最小堆蜜笤。在最大堆中，父節(jié)點的鍵值永遠大于等于所有子節(jié)點的鍵值把兔，根節(jié)點的鍵值是最大的瓮顽。最小堆中，父節(jié)點的鍵值永遠小于等于所有子節(jié)點的鍵值缕贡，根節(jié)點的鍵值是最小的。
- 時間復雜度
- 索引：O(log(n))
- 查找：O(log(n))
- 插入：O(log(n))
- 刪除：O(log(n))
- 刪除最大值/最小值：O(1)
image
哈希
- 哈希用于將任意長度的數(shù)據(jù)映射到固定長度的數(shù)據(jù)。哈希函數(shù)的返回值被稱為哈希值晾咪、哈希碼或者哈希收擦。如果不同的主鍵得到相同的哈希值，則發(fā)生了沖突谍倦。
- Hash Map：hash map 是一個存儲鍵值間關系的數(shù)據(jù)結構塞赂。HashMap 通過哈希函數(shù)將鍵轉化為桶或者槽中的下標，從而便于指定值的查找昼蛀。
- 沖突解決
- 鏈地址法（Separate Chaining）：在鏈地址法中宴猾，每個桶（bucket）是相互獨立的，每一個索引對應一個元素列表叼旋。處理HashMap 的時間就是查找桶的時間（常量）與遍歷列表元素的時間之和仇哆。
- 開放地址法（Open Addressing）：在開放地址方法中，當插入新值時夫植，會判斷該值對應的哈希桶是否存在讹剔，如果存在則根據(jù)某種算法依次選擇下一個可能的位置，直到找到一個未被占用的地址详民。開放地址即某個元素的位置并不永遠由其哈希值決定辟拷。
image
圖
- 圖是G =（V，E）的有序對阐斜，其包括頂點或節(jié)點的集合 V 以及邊或弧的集合E衫冻，其中E包括了兩個來自V的元素（即邊與兩個頂點相關聯(lián) ，并且該關聯(lián)為這兩個頂點的無序對）谒出。
- 無向圖：圖的鄰接矩陣是對稱的隅俘，因此如果存在節(jié)點 u 到節(jié)點 v 的邊，那節(jié)點 v 到節(jié)點 u 的邊也一定存在笤喳。
- 有向圖：圖的鄰接矩陣不是對稱的为居。因此如果存在節(jié)點 u 到節(jié)點 v 的邊并不意味著一定存在節(jié)點 v 到節(jié)點 u 的邊。
image
算法
排序
快速排序
- 穩(wěn)定：否
- 時間復雜度
- 最優(yōu)：O(nlog(n))
- 最差：O(n^2)
- 平均：O(nlog(n))
image
合并排序
- 合并排序是一種分治算法杀狡。這個算法不斷地將一個數(shù)組分為兩部分蒙畴，分別對左子數(shù)組和右子數(shù)組排序，然后將兩個數(shù)組合并為新的有序數(shù)組膳凝。
- 穩(wěn)定：是
- 時間復雜度：
- 最優(yōu)：O(nlog(n))
- 最差：O(nlog(n))
- 平均：O(nlog(n))
[圖片上傳失敗...(image-71f5a2-1556886570822)]
桶排序
- 桶排序是一種將元素分到一定數(shù)量的桶中的排序算法蹬音。每個桶內部采用其他算法排序著淆，或遞歸調用桶排序。
- 時間復雜度
- 最優(yōu)：Ω(n + k)
- 最差: O(n^2)
- 平均：Θ(n + k)
image
基數(shù)排序
- 基數(shù)排序類似于桶排序，將元素分發(fā)到一定數(shù)目的桶中懦砂。不同的是孕惜，基數(shù)排序在分割元素之后沒有讓每個桶單獨進行排序衫画，而是直接做了合并操作削罩。
- 時間復雜度
- 最優(yōu)：Ω(nk)
- 最差: O(nk)
- 平均：Θ(nk)
圖算法
深度優(yōu)先搜索
- 深度優(yōu)先搜索是一種先遍歷子節(jié)點而不回溯的圖遍歷算法弥激。
- 時間復雜度：O(|V| + |E|)
image
廣度優(yōu)先搜索
- 廣度優(yōu)先搜索是一種先遍歷鄰居節(jié)點而不是子節(jié)點的圖遍歷算法微服。
- 時間復雜度：O(|V| + |E|)
image
拓撲排序
- 拓撲排序是有向圖節(jié)點的線性排序以蕴。對于任何一條節(jié)點 u 到節(jié)點 v 的邊丛肮，u 的下標先于 v宝与。
- 時間復雜度：O(|V| + |E|)
Dijkstra算法
- Dijkstra 算法是一種在有向圖中查找單源最短路徑的算法习劫。
- 時間復雜度：O(|V|^2)
image
Bellman-Ford算法
- Bellman-Ford 是一種在帶權圖中查找單一源點到其他節(jié)點最短路徑的算法。
- 雖然時間復雜度大于 Dijkstra 算法须肆，但它可以處理包含了負值邊的圖桩皿。
- 時間復雜度：
- 最優(yōu)：O(|E|)
- 最差：O(|V||E|)
image
Floyd-Warshall 算法
- Floyd-Warshall 算法是一種在無環(huán)帶權圖中尋找任意節(jié)點間最短路徑的算法拒贱。
- 該算法執(zhí)行一次即可找到所有節(jié)點間的最短路徑（路徑權重和）逻澳。
- 時間復雜度：
- 最優(yōu)：O(|V|^3)
- 最差：O(|V|^3)
- 平均：O(|V|^3)
最小生成樹算法
- 最小生成樹算法是一種在無向帶權圖中查找最小生成樹的貪心算法暖呕。換言之湾揽，最小生成樹算法能在一個圖中找到連接所有節(jié)點的邊的最小子集库物。
- 時間復雜度：O(|V|^2)
image
Kruskal 算法
- Kruskal 算法也是一個計算最小生成樹的貪心算法诱告，但在 Kruskal 算法中精居，圖不一定是連通的箱蟆。
- 時間復雜度：O(|E|log|V|)
image
貪心算法
- 貪心算法總是做出在當前看來最優(yōu)的選擇空猜，并希望最后整體也是最優(yōu)的辈毯。
- 使用貪心算法可以解決的問題必須具有如下兩種特性：
- 最優(yōu)子結構
- 問題的最優(yōu)解包含其子問題的最優(yōu)解谆沃。
- 貪心選擇
- 每一步的貪心選擇可以得到問題的整體最優(yōu)解唁影。
- 最優(yōu)子結構
- 實例-硬幣選擇問題
- 給定期望的硬幣總和為 V 分，以及 n 種硬幣哟沫，即類型是 i 的硬幣共有 coinValue[i] 分嗜诀，i的范圍是 [0…n – 1]隆敢。假設每種類型的硬幣都有無限個拂蝎，求解為使和為 V 分最少需要多少硬幣尊浪？
- 硬幣：便士（1美分）拇涤，鎳（5美分）鹅士，一角（10美分），四分之一（25美分）也拜。
- 假設總和 V 為41,慢哈。我們可以使用貪心算法查找小于或者等于 V 的面值最大的硬幣卵贱，然后從 V 中減掉該硬幣的值键俱，如此重復進行编振。
- V = 41 | 使用了0個硬幣
- V = 16 | 使用了1個硬幣(41 – 25 = 16)
- V = 6 | 使用了2個硬幣(16 – 10 = 6)
- V = 1 | 使用了3個硬幣(6 – 5 = 1)
- V = 0 | 使用了4個硬幣(1 – 1 = 0)
位運算
- 位運算即在比特級別進行操作的技術臭埋。使用位運算技術可以帶來更快的運行速度與更小的內存使用。
- 測試第 k 位：s & (1 << k);
- 設置第k位：s |= (1 << k);
- 關閉第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;
運行時分析
大 O 表示
- 大 O 表示用于表示某個算法的上界镐牺，用于描述最壞的情況。
image
小 O 表示
- 小 O 表示用于描述某個算法的漸進上界旗唁，二者逐漸趨近痹束。
大 Ω 表示
- 大 Ω 表示用于描述某個算法的漸進下界祷嘶。
image
小 ω 表示
- 小 ω 表示用于描述某個算法的漸進下界论巍，二者逐漸趨近嘉汰。
Theta Θ 表示
- Theta Θ 表示用于描述某個算法的確界鞋怀，包括最小上界和最大下界焙矛。
image
以為這就結束了残腌？No, 這些知識不僅僅是停留在理論邓梅，還有代碼實現(xiàn)邑滨。
image
這其實是來自 GitHub 的一個 repo：https://github.com/kdn251/interviews
除了上述算法和數(shù)據(jù)結知識外匣距，其中還有推薦了一些算法練習網(wǎng)站、視頻教程毅待、面試寶典尸红、Google、Facebook 等知名公司面試題及解答代碼怎爵。下載實例代碼或者收藏練習網(wǎng)站鳖链。
Enjoy!
