演算法學習之 Leetcode 破關總指南（二）
實戰練習與各種自我訓練方式
上一篇我們走出了新手村，也進行了基礎訓練，現在要正式踏上冒險旅途啦
實戰應用練習場 LV. 1
就跟任何遊戲一樣，在練功坊學會招式之後，靈活運用才是重點，在這個區域的題目，通常背後隱藏的概念不會太難，但就是不容易一眼看穿，解法會比上面練功坊的題目藏的更深，或需要轉更多的彎。其中有些題甚至不需要任何練功坊學到的知識也能解，也有些可能用到更困難演算法的小部分，但你不會證明也能猜到做法（例如簡單的 Greedy 題目）。
先讓我們來看個不用什麼特殊技巧，但又稍有點難度的題目
給大家一些 tasks，例如 [A, A, B, B]，你可以自由決定工作順序，每個工作花費 1 秒，但相同工作需間隔 n 秒，請問最快多久能完成。下面舉兩個符合條件的排列方式（假設 n = 2）
- A -> idle -> idle -> A -> B -> idle -> idle -> B
- A -> B -> idle -> A -> B
顯然第二種安排方式更省時，但如何在任意 tasks 與 n 都能找到最佳解呢？
面對這種問題，我們要學會忘掉所有你學會的招式，返璞歸真回到最原始的狀態。簡言之，找回面對任何問題的初心，也就是
- 觀察規律
- 分類歸納不同情境
- 對每個情境一一處理
有時間的讀者，建議可以自己先試試看，慢慢梳理出自己的邏輯，不要太快放棄，這是你面對這個區域題目的唯一方式，但也會是讓你成長最快最好的方式。如果有找到解法，應該會發現這題還真的用不上我們前面學過的任何招式，就是最基本的新手村方式即可解決，這裡也提供一篇我找到覺得寫的不錯的解題思路給大家。
而在這個區域中，也有些題目，會需要我們學過的資料結構 LV1或演算法 LV1的招式，讓我們也來看看長什麼樣子，例如
這個看似可怕的題，其實只要會 Set 的概念就可以解決，但一樣不那麼容易想到做法，有興趣的讀者可以試著想想怎樣處理他，解答可以看這邊。
再看以下這題也是經典案例
如果你前面有搞懂 Sorted Array 的 2Sum 如何用 Two Pointer 解決，那這題就是依序拿每一個數字當開頭，後面的再做一次 2Sum 而已，不過第一次看到也時常讓人卡關。
老實說這個區域的題目並不好整理，大多是 Medium，很多藏都在 Array 或 String 的 Tag 中，還有上面提到資料結構與演算法 LV 1 的 Tag 中，學習時可以先從讚數最多的做起，通常都是超級經典題，後期再試著隨機挑題。但做不出來不需要硬撐、也不用氣餒，若超過 20 min 還毫無想法時，就去看討論區吸取養分即可。
確實對很多新手來說，這會是個令人感到挫折的區域，因為你會突然發現失去了前面練功坊一步一腳印的成長階梯，有突然進入一片迷霧的感覺，題目寫的有些痛苦，且前面學過的東西也時常用不上，找不到明確的路，會讓人覺得自己一路以來的努力都有點白費。
但其實不是這樣，這裡的題目考驗的就是你的經驗跟隨機應變能力，這跟練功坊那種有一招一式的主題式練習非常不同，而是需要你野地求生的實力，要突破這關卡，請謹記我們最核心的”觀察”、”分析歸納”、”分項處理”的思維模式，不斷訓練提高自己思維的靈活與縝密程度，唯有投入時間磨練，讓你的經驗慢慢提升，一旦過了某個檻，就會突然有豁然開朗之感，從此不再害怕前往未知陌生的大漠荒野或陰暗森林。
最後，記得挑選能力範圍內的題目去挑戰
- 失敗的成長循環：隨便開一題 -> 想破頭不會做 -> 開解答看很久才看懂 -> 感到疲累 -> 沒動力再打開下一題暫時放棄 -> 很久以後又想到要練刷題 -> 隨便開一題
- 成功的成長循環：挑選能力範圍內的題目 -> 慢慢分析歸納找到思路 -> 做出來獲得滿滿的成就感 -> 很想再開一題挑戰自我 -> 尋找適合的下一題繼續挑戰
如果你長年都苦於找不到刷題動機，時不時燃起熱血想徹底搞定他，但沒多久又把這件事放一邊去，往復循環，我有另一篇專門寫如何找到動機來源的文章也可以看看。
另外，也曾有人用答對率整理出 Leetcode 題目難度表，但僅當參考就好，每個人感受到的難易度是不同的。總之，給自己一點時間停在這邊好好磨練，不要輕言放棄。
特殊模式
這是個特別的區域，有少數題目會給一些額外條件，要求你考慮時間複雜度以外的東西，就像一般遊戲中要求你三星通關或拿到隱藏寶物的感覺，而 Leetcode 的特殊要求通常是以下幾個：
- Constant Extra Space：不使用任何額外記憶體，也就是 space complexity 要是 O(1)
- One Pass：不只時間複雜度要 O(N)，還只允許跑一輪迴圈
- In-place：直接對原始 input 做改變，不回傳答案，通常也隱含 Constant Extra Space 的條件
- Integer Limit：運算中任何一刻都不可以超過 Integer 範圍
這些要求通常你不遵守 Leetcode 還是會讓你通過 (Accept)，但假如是面試時被問到，就不能這樣混過去啦，所以要額外注意。一般都是寫在題敘的最底下。經典範例題目如下
- Constant Extra Space: Single Number
- One Pass: Sort Colors
- In-place: Reverse String
- Integer Limit: Divide Two Integers
第一題 Single Number 會需要一點 Bit Manipulation 的知識，稍微難一點
第二題 Sort Color，如果你以前 quick sort 有學好，其實就是 partition 做兩次而已，但加上 one pass 的條件後就不那麼容易了，要做出 3-way partition
第三題應該相對簡單，只是要認識一下 in-place 的答題方式
而第四題 Divide Two Integers 則要考驗你對整數型別的範圍是否有足夠的敏感度，乍看之下是個超級簡單的問題，但如果細細思考，會發現有很多的麻煩在裡面，例如 input 的數值可能是 -2³¹，但假如你輕易的對他做絕對值運算，變成 2³¹ 就超出整數範圍了，算是不合格的做法。面對這種題目，假如你用 Python 或 Javascript 之類的語言，很可能會完全沒注意到這問題，因為他都內建大數運算。因此這類題目會建議用 JAVA 或 c/c++ 來做，且不能開 long 型別，要強迫自己熟悉 int 的特性。
這區域的題目，對新手來說可以先簡單認識一下就好，知道還有這些面向的考題存在，思考的過程會幫助你磨練與內化基本功，但不用太執著於一定每題都要做出來，畢竟這都算是進階要求了，可以先往後走下去，隨著你的能力慢慢提升，這些要求也會漸漸變得容易。
挑戰模式
這邊介紹的，是一些增加自我練習強度的方式，對任何題目、任何階段都適用，也就是除了單純完成題目得到 Accept 以外，你可以開始逐步增加對自己的要求，要求難度照以下為順序逐漸提高
- 無論如何給出一個暴力解，通常你會看到 Time Limit Exceeded (TLE) 代表你的暴力解成功了，只是跑太慢所以比較大的測試資料沒辦法通過，否則會先看到 Wrong Answer (WA)，代表邏輯本身是錯的
- 從 Top 100 like 裡面隨機抽題，且不去看題目的分類，前面的訓練會讓人習慣已經知道分類的情況下解題，但真實面試的時候，你是不會有這個資訊的，得靠自己的觀察力找到答案
- Submit 後若沒通過時，不要看 Leetcode 給的測資，自己去發想測試資料來找到錯誤，這會磨練你思考 corner case 的能力，畢竟 on-site 面試或 phone interview 的時候，發想測資也是面試官很愛觀察的面向之一。
- 減少嘗試按 run 的測試次數，也減少在自己 IDE 上面測試的次數，更進一步可以要求自己完全不 run code，但一次 submit 就要通過，這會大幅增加挑戰的難度，因為你必須把邏輯想得非常透徹，確保沒有任何一絲漏洞，一般公司的面試不太會要求到這樣，但練習的時候可以視為一種負重訓練，考驗自己邏輯是否完全清晰，且養成寫 code 嚴謹紮實的好習慣。而最知名的 Google 面試，就是要求面試者要在類似 Google Doc 的工具上，在無法 run code 的情境下，自己想測資，並寫出真的能跑出正確結果且無 bug 的 code，是不是很刺激？
這個區域一樣新手可以不用太執著，依照自己的能力，發現題目有點容易的時候，可以試著提高自我要求，發現題目很難的時候，就先回到最簡單的要求（給出一個暴力解）即可。
如果到這邊你都還進行順利，恭喜你，基礎的演算法考試應該都打不倒你了，可以算是一個里程碑，好好慶祝一番吧。接下來下一篇，我們要踏入進階演算法的領域，準備揮劍挑戰一個個大小 boss 級別的怪物了。
