Skip to content

以其人之道還其人之身:如何用分治法對付 LeetCode / 刷題心得跟題庫分享

  • Misc
Tags:

Intro

是的,當你看到這篇文章的時候,我還沒找到工作。因此,最近的幾個月,我如果不是在刷題,就是在沒網路的路上。

截至目前為止,我嘗試了將近 300 種不同題形的解法,有效題數是 209,約 1000 多次 commit。

刷題時間久了,對 LeetCode 這個東西不禁感到又愛又恨。甚至是恨的層次居多,為什麼?我認為有以下幾個原因:

真的用得到嗎?

當然,像 146. LRU Cache253. Meeting Rooms II 這種貼近實務的題目是再好不過了,但你不得不承認,大部分的題目還是有那麼派不上用場的意味在,那種感覺就像你在高中學了艱澀的數學理論,但並不知道怎麼在真實世界中應用它們一樣。

試想一下,你拿刷題的時間去嗑一本有關程式設計的書,或去想辦法弄些什麼專案,學到的「馬上可用的知識點」應該都比刷題多得更多。

應徵的公司在場上覆蓋三張陷阱卡,其中一張是神的宣告

你有沒有覺得,現在好多公司都好愛考刷題,先是聯繫到你,告訴你說「我覺得你很可能就是我們要找的 XXX」,然後也不跟你約時間,就丟一個考試連結給你。

然後你可能沒辦法在 20 分鐘內「把零移到前面」或找不到「買賣股票的進出點」,然後就失去了面試機會,或者再也沒有下文。這代表了一件事——開發者的價值被 LeetCode 給過度簡單地歸類了——如果你不刷題,不管你曾經開發過什麼,都不再有意義,因為你連門票都拿不到。

這種面試體驗,我至少就遇到過三次。

是的,即使你知道什麼是陣列、什麼是 swap、indexing,你也知道時間複雜度跟空間複雜度是在講什麼,但你就是想不出來怎麼把該死的 0 給移到前面去。

還記得 Homebrew 的開發者 Max Howell 因為不會翻轉二元樹被 Google 拒絕了,他氣得發了一篇反諷推文。不過他事後表明:我某種程度來說也很爛,我還是搞不太懂二元樹是什麼,但我不怪 Google 了。

這個例子可以很好地概括我目前對面試考題的想法:Get Over It。

當刷題儼然成為找工作的「內建」、必要條件,那麼也許,我們就不要再 ㄍ一ㄥ 了吧。


也是這樣由恨生愛,必須分享一下我對刷題的正向看法:

這樣也可以?可不可以不要解得那麼帥?

我覺得 LeetCode 有一個重要的價值在於「題目永遠存在著另一種解法的可能性」。

例如,當你在做 62. Unique Paths 這樣一個很明顯的 DP 問題,然後突然有人敲了你的腦袋說:「阿這就排列組合阿,什麼 DP」;又例如,當你還在一個接一個慢慢 338. Counting Bits 的時候,那個人又跳出來靠北說:「阿這就 DP 阿,還在迴圈喔」

因此,我們自然而然擁抱了一個問題的多元的觀點,而不是只用一種視角去看待。這個觀念在實務上也很重要:當你試圖解決一個問題,無論那個問題是否被解決了,總是要試圖尋找「更好的解法」,而非不知變通,只是死死抱著那個「我會的方法」。

所以,你如果在刷題,想盡辦法「榨乾」一個題目,這樣才有意義。

更深入你自以為理解的資料結構

前陣子 Apple 公佈了他們加強版的隱私權政策,震撼了廣告商,公司要在不依賴第三方 Cookie 的前提下,想辦法去識別使用者,或換句話說,讓使用者歷程不要變得過於短暫。

在這個背景之下,我跟同事臨危受命要找到可行的一個替代方案,於是我想到了 Graph,並且在以 HashMap 為基礎的資料庫上,進行「人與人之間的連結」,最後設計出的方案有點像是這樣:

image

後來我才知道這個命題的核心就是 Union Find,當時我根本不知道有 Disjoint Set 這種資料結構(或者看過就忘了),也就是說,如果我早點刷到類似的題目,我可能根本不需要搞得這麼人仰馬翻,而且還能借助既有的 path compression 跟種種優化技巧。

所以對我來說,刷題的另一個好處是「讓資料結構變成是可練習的」,上過資料結構的都知道,書本上的抽象理論很無聊、很容易忘記,在 LeetCode 上面,刷題反而變成理論的一種實際「應用」。

所以我說,那個分治法(Divide & Conquer)呢?

廢話不多說,先上圖:

image

試想一下,刷題本身未嘗也是一種演算法,我們同樣必須考慮到刷題的「效率」、以及我們的「記憶能力」。從這個角度來看,分治法也許是一個不錯的方案。

首先,你必須把好幾百個複雜的題目分成相似的子問題,然後一起去理解他們。例如,像 139. Word Break 這種題目,就至少可以分到 RecursionBreadth-First-SearchDynamic Programing 這三個子問題當中。

接下來的 Conquer 階段,我們可以視為是「內化」與「整合」,每個問題在做的過程中,依照特定的條件去歸類到不同的熟練程度:對你來說,是 easy、medium 還是 hard?

  • Easy: 可以在十分鐘內提出解決辦法並流暢地完成,且熟暗各種 edge case 與不同解法
  • Medium: 知道怎麼做,但實作的流程因為某些原因卡住,導致要花更多的時間才能完成、容易踩到 edge case 的陷阱、實作的代碼不夠精闢簡要
  • Hard: 完全沒頭緒,或是花了一個小時才能勉強湊出答案

做好分類,我們才可以有效地多練習那些不熟的題目,直到全部都變成 Easy!

在這張圖的最後,也就是我們最後的目標,其實就是面試的結果(True or False),以及能否將這些題目內化到能夠拿來運用在真實的工作場景。

LeetCode 101

寫到這裡,如果你還繼續在看的話,恭喜,你將獲得 LeetCode 新手大禮包(這裡的新手是指我)

如果你也不得不面臨刷題的窘境,那我會想要與你分享一下幾個實用的小技巧:

1. 善用清單

要以分治法實作刷題,你應該建立多個分類清單,我在下方會分享我的清單,請不吝複製貼上。

記得,各種熟練度的清單也要一併建立。

2. Premium 135美金刷下去就對了啦,不然你也是花在別的地方

課金仔可以解鎖的第一個功能是 Solution,當你不是很確定怎麼做,或是超過 20 分鐘做不出來,我會建議你不要花太多時間嘗試去解題,因為當你「執念越重」,你就會浪費更多時間,更糟糕的是,你解愈久,就會愈加深你腦海裡面對這個解法的印象,導致你每次都第一個想到這個錯誤或繞路的解法。

當你發現自己已經 TimeOut,不妨直接打開 Solution 吧,有些解法的文章的內容其實是很超值的,官方的 Solution 常常提供 1~4 種作法,你應該試著理解每種可能的解法,而不是選擇一個你最熟悉的。

如果你看完,還不是很能理解,沒關係,做過一遍,然後丟到 hard 清單,暫時先不管它。然後,這時候你可以逛逛評論區,看看別人對這些解法有什麼意見:

然後一定會有人說:

笑一個,沒事。

3. 詳細紀錄每次 commit 的心得

台幣戰士可以解鎖的第二個功能是,右側有個 Notebook 功能,你可以寫 Markdown 紀錄任何有關這題的事項(只有你能看)。至於全部的筆記,Leetcode 也可以幫你一起匯出成一份 pdf。

我會建議每次重做,都詳細紀錄你卡住的點,或是任何你想靠北的事情。好幫助你快速回朔找回記憶點。

舉幾個例子:

image

image

image

4. 反覆練習

有句諺語是這麼說的:「一個沒看過的英文單字,多看幾次就會背了。」一個好的題目應該也是一樣,只做一次是不行的。人是健忘的動物。

尤其是被那些你認為 hard 的題目,就我自己的經驗來看,其實「只做一次」是等同沒做的,你必須要在多個時空下去反覆練習,才有機會內化。讓我們一起希望他們某天能變 easy 吧。

5. 解題期間,記得 ~~ipad~~ 搭配一本程式語言的書籍一同欣賞

刷題刷累了嗎?不妨抽離一下,閱讀一下你使用的程式語言的教課書。我讀的是 Fluent Python。

做這件事對我第一個直接的幫助是,當我以前在取陣列長度,我會不確定是否要用變數儲存以免反覆計算,例如以前會寫成:

但當我知道 len() 其實是呼叫底層 CPython 的代碼,直接到物件內部取值,就再也不擔心這件事了,現在我都隨便 call len(),call 得很爽。

另外一個好處是增加你解題程式的「可閱讀性」,用 Python 刷,會發現尤其 list-comp、unpacking 的技巧十分常用,有些題目甚至也可以用到自訂的 decoratorgenerator,來取代一些難以閱讀的代碼片段。

5. 有什麼發現,就發文到 Discuss 吧

分享是一種美德,也是一種成就感。(好吧,雖然我目前的 reputation 只有 2 點)

題庫賞析

如下表,若連結錯誤或失效,請再聯繫我:

結語

「打不贏,就加入」

「刷題的終點,不是 Offer Get,而是 Real World Problem」

如果你是剛接觸 Computer Science 的先進,我的建議是,與其狂刷題,不如試著做點專案,找出你的熱情所在、以及你程式存在的意義。

至於那些已經頭洗一半的,加減刷吧。你已經沒有退路了。


最後,謝謝你抽空看完這篇文章。歡迎你一起分享你刷題的各種辛酸血淚史。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。