演算法學習之-Leetcode-破關總指南（一）

新手村與基本功訓練

Arthur Lin

Published in

AppWorks School

10 min readNov 14, 2021

Background vector created by upklyak — www.freepik.com

學習演算法對很多非本科系的工程師來說，一直是個令人頭痛的東西，畢竟新手期的工作幾乎都用不上，但一旦要面試進階一點的職位，又特別愛考，有的考簡單有的考難，你也猜不到會遇到什麼，如果沒刷什麼題，就只能祈禱拜託不要考我這個其他考什麼都好。

但每次終於下定了決心，報了幾堂線上課程要來好好搞懂他，卻又意志力不足，往往看沒幾堂就放棄了。就算好不容易上完了，打開 Leetcode 後又是打擊信心的開始，幾乎每一題都毫無頭緒，就算勉強看懂之後，換一題還是又只能乾瞪眼，覺得自己活像個笨蛋。

以上，全都是我曾經走過的路

當時已工作 4, 5 年，還連 Binary Search 都不太會寫的我，為了想挑戰海外工作，硬着頭皮奮力刷了大半年的題，終於開始感受到小小的成就，也順利拿到日本獨角獸新創公司的 Offer。之後又過了段時間，在一個特別的機會，上了全台灣最強 CP 競賽老師半年多紮實的家教訓練課程，終於對演算法這門學科有了深刻的認識，也刷題刷出了興趣，後續一邊教學生一邊持續練習， Leetcode Contest 的名次逐漸進步到 Top 1％之內，終於在 2022 下半年，一口氣同時拿到了台灣 Google 與美國 Amazon 的 Offer，有興趣看面試分享的可以點下面連結。

拿到 Google & Amazon Offer 的面試之旅（一）

拿到 Google & Amazon Offer 的面試之旅（二）

回想一路走來，覺得刷 Leetcode 的過程，其實很像玩遊戲練等一般，剛開始什麼都不會，遇到什麼怪當然都是被 KO，但隨著升級路上不斷拿到新道具，也不斷提升操作的熟練度之後，就能不斷挑戰越來越厲害的怪物。

今天就想來和大家分享，如何像玩遊戲升級的角度，來看待 Leetcode 的不同關卡，同時也是給大家一份面試準備的總指南，讓所有想在這方面成長的工程師，可以有一條比較明確的練習升級道路，同時也附上一些我寫過或蒐集過不錯的教材文章連結。如此一來，不管你是想純靠自己自學的免費玩家，還是正在煩惱要報名什麼課程當台幣戰士，這系列都可以讓你更確定自己的位置大概在哪，也更清楚下一步該怎麼走。

現在，就讓我們一起來破關吧！

首先給大家看一下我心目中的 Leetcode 關卡地圖

新手村

對任何一個軟體工程師來說，都是從這邊出發的，在這裏，你需要會的就是最基礎的程式概念

輸入、輸出
整數、浮點數、字串、陣列、雙重陣列
判斷式 if / else
迴圈 for loop / while loop
函數 function()
變數值與記憶體位址的概念
十進位與二進位轉換的基本概念
時間複雜度、空間複雜度的基本概念與 Big-O Notation

如果你已經是一個軟體工程師，基本上應該最少 1～6 都很熟才對，7, 8 也不會太難。如果你是完全白紙的初學者，那最簡單的學習方式，就是去諸如 Coursera, Udacity, Udemy, Treehouse, Hahow, HiSKIO, … 等等平台，先找個評價好、看得舒服的程式語言線上教材跑一遍即可。

至於程式語言的選擇，如果你已經有熟練的語言，繼續使用即可，不用特意為了刷題更換，除非你的目標公司有限定語言。如果是白紙新手，比較推薦的是 Python 或 JAVA，畢竟這兩個語言工具庫完整，且用他們寫題的人數極為眾多，很容易找到範例教材，對卡關的新手很有幫助，且工作上也非常實用。至於 c/c++ 雖然也是很合適的刷題用語言，甚至是演算法競賽最大宗語言，但進入障礙稍高，非本科的新手工程師在工作中用上的機會也偏低。Javascript 與 go 則是缺少一些好用的資料結構工具庫，但初學來說是沒有影響的，所以也可以拿來當入門，但進階以後，會需要自己實作這些資料結構來用。

最後提醒大家，雖然新手村看似簡單，但卻是所有演算法學習的核心基礎，有很多難題其實需要的也就只是這邊提到的技術而已，但非常考驗你拆解與分析問題的能力，還有實作出想法的能力。其實我認爲這才是演算法考試真正的價值所在，能赤裸的看出一個工程師最重要的兩大能力”分析問題”與”將理論化為實作”。而接下來要開始介紹的常見資料結構與演算法，則比較像是一個個過往資訊領域大師的智慧結晶，透過學習他們找到的經典套路，來快速解決相似的問題。

資料結構練功坊 LV. 1

學習演算法前，一定得對基礎的資料結構有一定程度的理解，可以把他們想成遊戲中必備的基礎道具，你得先蒐集並理解他們的特性，之後才能好好派上用場。

Shield vector created by freepik — www.freepik.com

如果你已經是新手工程師，或許很多東西你早就已經天天在使用，卻很少認真去探討他們的各種特性，現在就是搞懂他們的時候了

Array
Hash Table
Set
Stack
Queue
Linked List（先懂基本操作即可）
Binary Tree（先懂基本 DFS/BFS 即可）

認識一個新資料結構，我們要關注的就是他各種操作的時間複雜度，最基本的操作如下

insert
delete
find（找到某個值的位置）
peek（查看某位置的值）
check exist（確認值是否存在）

注意，即使是相同操作，但在不同位置上，時間複雜度都不同

例如 Array 你在最尾端 (tail) 做 insert 會是 O(1)，但在頭部 (head) 或中間（middle）去做 insert，就會變成 O(N) 了

再例如對無排序 Array 詢問某個 value 是否存在的時間複雜度是 O(N)，但對 Set 詢問 value 是否存在，或對 Hash Table 詢問 key 是否存在，都是 O(1)。

這些差異在資料很小的時候都無感，第一但資料量大起來就天差地遠了，而演算法就是一門在尋求效能最大化的學問，當然你得對每個資料結構的特性瞭若指掌。這邊有個整理好的總表可以看，而每個語言也能找到更詳細的介紹，例如 Python 可以看這邊

但如果一口氣看過去，新手也不會有什麼感覺，更不該用背的。最好的學習方式，就是一個一個主題去研究，每看懂一個，就找相對應的基礎題目做嘗試，實驗你學到的理論，學習方法大致如下

依據每個關鍵字，挑選一個適合你的教材，足夠你理解各種基礎操作的時間複雜度即可，先不需要看到太過深入，例如以 Hash Table 來說，這篇教材就是我覺得滿適合這個階段需要理解的程度。
Hackerearth 的資料結構 Tutorial 寫的也非常好，大部分基礎可以看這邊，也有配上練習題目
都看完後，去 Leetcode 上找對應的基礎題，驗證你學到的東西

找題目的方法，就是找同名 Tag 中的 Easy 題，然後從 Top 100 Likes 開始。之所以要找基礎題，是要讓你能更專注在資料結構本身特性的掌握上。這階段找太過變化或刁鑽的題目，會讓你的重點偏掉，學到一些很華麗的技巧，但也不知道怎麼用，久了就忘光而已。

以下來舉幾個基礎題的例子：

Hash Table: Two Sum
Set: Intersection of Two Arrays
Stack: Valid Parentheses
Linked List: Merge two sorted linked list
Binary Tree: Maximum Depth of Binary Tree

由於 Array 太過廣泛，幾乎任何題目都會用上，而 Queue 則是到後面 Tree 與 Graph 的章節才比較常用上，因此這邊先不特別列題目了。

記得一個重點：這個階段，寫題目的重點是幫助自我檢核，確認該主題的內容是否有掌握好即可。

不要硬去挑戰難題然後又硬要自己想出來才肯罷休，這樣的學習效率會很差，甚至學不到重點反而歪掉。也不用太強求要把每個資料結構理解到最底層去，例如如何用 Linked List 處理 Hash Table 的碰撞問題，對這階段來說就有點超出範圍了，有大致理解他們各種操作的時間複雜度特性後，就可以先往下一關邁進了。