Leetcode刷題前應該具備哪些入門知識？

前文入口：

為什麼寫這篇文章？

很多人刷Leetcode之前只有非常有限的程式碼和資料結構基礎，然後想要暴力的透過刷Leetcode來迅速轉碼上岸，最後直接去大廠當碼農掙大錢。作為一個也曾經抱有此類幻想的人，本人也曾經試圖在沒有基礎情況下簡單暴力的去Leetcode刷題，然後被打擊的體無完膚，答案看不懂，別人的解釋看不懂，甚至各種教學影片都看不懂，於是直接放棄了轉碼的幻想，一段時間後不甘心拾起來又放下反反覆覆三年就過去了，現在回想下真的是耽誤了好多時間。鑑於個人的慘痛經歷，我準備把刷題之前應該先掌握的基礎知識羅列在這裡，希望對也想要刷題當碼農，尤其是

轉碼

的各位有幫助吧。如果你有一門熟悉的語言，但是沒有太多資料結構/演算法的基礎知識，把下面列舉的基礎補齊大概需要一個月左右時間。

注：第一版打算把各個資料結構的基礎以及基礎演算法羅列下來，後續打算把相關能找到的入門資料也新增上去。

語言基礎：

至少選擇一門相對熟悉的語言來刷題，雖然Leetcode上常見的開發語言都是支援的，但是個人還是建議選擇Python/ Java / C++其中一個。這幾門語言各種基礎的資料結構都比較完善，刷題時候用的人也是最多的，看答案/別人的解答時候也最容易找到參考資料。

對於你要選擇的刷題語言，起碼你需要知道程式碼是怎麼執行的，什麼是變數、迴圈、函式、類與物件等。

時間複雜度與空間複雜度基礎

：

你需要知道什麼是時間/空間複雜度， 大O是什麼意思，常見的複雜度包括哪些。如何來判斷一段程式的複雜度。

一般語言自帶的常用資料結構：

（不用語言的對應資料結構名稱可能有所差異）

列表

（list/array list/array等）。列表常見操作，以及相關的時間複雜度。

append一個元素、pop末尾元素均為O（1）

查詢某個元素的索引O（n）

雜湊（hash table）。

需要掌握以下基礎知識：

什麼是雜湊，雜湊函式是什麼，最常見的雜湊表資料結構是什麼（集合與雜湊表）

集合（set/ hashset等）。

集合一般用於幹什麼？

集合的常見操作有哪些？每個常見操作的時間複雜度是什麼？

雜湊表（Hashmap/ dict/ unordered_map等）。

雜湊表一般用於幹什麼？

雜湊表有哪些常見操作？對應的時間複雜度，空間複雜度分別是什麼？

棧

（stack）

什麼是棧？什麼是後進先出？

棧一般用於解決什麼問題？

什麼是程式棧？

你所熟悉的語言當中棧是用什麼資料結構實現的？（Python當中用list就可以代表棧）

佇列

（queue）

什麼是佇列？什麼是先進先出？

佇列一般應用在哪些場景當中？

什麼是訊息佇列？

你所熟悉的語言當中棧是用什麼資料結構實現的？（Python當中可以用deque或者queue）

堆

（heap）

什麼是堆？什麼是最大堆、最小堆？

堆一般用於解決什麼問題？

你所熟悉的語言當中堆是用什麼資料結構實現的？（Python當中堆用的是列表實現的，並且Python只有最小堆沒有最大堆）

一般語言不自帶的資料結構：

（需要自己手工建立）

連結串列

（linked list）

連結串列的節點（node）是如何實現的？

如何建立一個連結串列？

如何遍歷一個連結串列？

如何在連結串列中查詢一個元素是否存在？

如何在連結串列中新增/刪除一個元素？

二叉樹

（binary tree）

二叉樹的節點（node）是如何實現的？

如何建立一個二叉樹？

如何遍歷一個連結串列？何謂二叉樹的層序、前序、中序、後序遍歷？

二叉搜尋樹

（二叉查詢樹、binary search tree、BST）

與普通的二叉樹相比，二叉搜尋樹特點是什麼？如何證明一棵二叉樹是/不是一課二叉搜尋樹？

一個二叉樹是二叉搜尋樹 <-> 該二叉樹的中序遍歷是單調遞增的

簡單圖

（graph）

什麼是圖？什麼是有向圖（directed graph）？什麼是無向圖（undirected graph）？

圖與樹的關係是？如何知道一個圖是不是一課樹？

如何實現一個簡單圖？

應該掌握的入門演算法：

遞迴：

什麼是遞迴？

遞迴的優勢、劣勢是什麼？

遞迴三要素是什麼？

排序演算法：

快速排序如何實現？時間/空間複雜度是多少？

歸併排序如何實現？時間/空間複雜度是多少？

二分法：

二分法的基本原理是什麼？

二分法一般用於解決什麼問題？

二分法的時間複雜度是什麼？

寬度優先遍歷（寬度優先搜尋、Breadth first search、BFS）：

寬度優先遍歷的模板是什麼？

寬度優先遍歷的時間/空間複雜度是什麼？

寬度優先遍歷一顆二叉樹與一個圖的區別在哪？

寬度優先遍歷一般用於解決什麼問題？

深度優先遍歷（深度優先搜尋、Depth first search、DFS）：

深度優先遍歷的模板是什麼？

深度優先遍歷的時間/空間複雜度是什麼？

深度優先遍歷一顆二叉樹與一個圖的區別在哪？

深度優先遍歷一般用於解決什麼問題？

如果以上問題你都能回答的上來的話，那你已經可以去Leetcode的題海中徜徉了。