雖然刷題一直飽受詬病，不過(guò)不可否認(rèn)刷題確實(shí)能鍛煉我們的編程能力，相信每個(gè)認(rèn)真刷題的人都會(huì)有體會(huì)?，F(xiàn)在提供在線編程評(píng)測(cè)的平臺(tái)有很多，比較有名的有 hihocoder，LintCode，以及這里我們關(guān)注的 LeetCode。

代碼提交曲線

LeetCode 是一個(gè)非常棒的 OJ（Online Judge）平臺(tái)，收集了許多公司的面試題目。相對(duì)其他 OJ 平臺(tái)而言，有著下面的幾個(gè)優(yōu)點(diǎn)：

• 題目全部來(lái)自業(yè)內(nèi)大公司的真實(shí)面試
• 不用處理輸入輸出，精力全放在解決具體問(wèn)題上
• 題目有豐富的討論，可以參考別人的思路
• 精確了解自己代碼在所有提交代碼中運(yùn)行效率的排名
• 支持多種主流語(yǔ)言：C/C++，Python, Java
• 可以在線進(jìn)行測(cè)試，方便調(diào)試

下面是我刷 LeetCode 的一些收獲，希望能夠引誘大家有空時(shí)刷刷題目。

問(wèn)題：抽象思維

波利亞用三本書：《How To Solve It》、《數(shù)學(xué)的發(fā)現(xiàn)》、《數(shù)學(xué)與猜想》）來(lái)試圖闡明人類解決問(wèn)題的一般性的思維方法，總結(jié)起來(lái)主要有以下幾種：

• 時(shí)刻不忘未知量。即時(shí)刻別忘記你到底想要求什么，問(wèn)題是什么。（動(dòng)態(tài)規(guī)劃中問(wèn)題狀態(tài)的設(shè)定）
• 試錯(cuò)。對(duì)題目這里捅捅那里搗搗，用上所有的已知量，或使用所有你想到的操作手法，嘗試著看看能不能得到有用的結(jié)論，能不能離答案近一步（回溯算法中走不通就回退）。
• 求解一個(gè)類似的題目。類似的題目也許有類似的結(jié)構(gòu)，類似的性質(zhì)，類似的解方案。通過(guò)考察或回憶一個(gè)類似的題目是如何解決的，也許就能夠借用一些重要的點(diǎn)子（比較 Ugly Number 的三個(gè)題目：263. Ugly Number， 264. Ugly Number II， 313. Super Ugly Number）。
• 用特例啟發(fā)思考。通過(guò)考慮一個(gè)合適的特例，可以方便我們快速尋找出一般問(wèn)題的解。
• 反過(guò)來(lái)推導(dǎo)。對(duì)于許多題目而言，其要求的結(jié)論本身就隱藏了推論，不管這個(gè)推論是充分的還是必要的，都很可能對(duì)解題有幫助。

刷 LeetCode 的最大好處就是可以鍛煉解決問(wèn)題的思維能力，相信我，如何去思考本身也是一個(gè)需要不斷學(xué)習(xí)和練習(xí)的技能。

此外，大量高質(zhì)量的題目可以加深我們對(duì)計(jì)算機(jī)科學(xué)中經(jīng)典數(shù)據(jù)結(jié)構(gòu)的深刻理解，從而可以快速用合適的數(shù)據(jù)結(jié)構(gòu)去解決現(xiàn)實(shí)中的問(wèn)題。我們看到很多ACM大牛，拿到題目后立即就能想出解法，大概就是因?yàn)樗麄儗?duì)于各種數(shù)據(jù)結(jié)構(gòu)有著深刻的認(rèn)識(shí)吧。LeetCode 上面的題目涵蓋了幾乎所有常用的數(shù)據(jù)結(jié)構(gòu)：

• Stack：簡(jiǎn)單來(lái)說(shuō)具有后進(jìn)先出的特性，具體應(yīng)用起來(lái)也是妙不可言，可以看看題目 32. Longest Valid Parentheses。
• Linked List：鏈表可以快速地插入、刪除，但是查找比較費(fèi)時(shí)（具體操作鏈表時(shí)結(jié)合圖會(huì)簡(jiǎn)單很多，此外要注意空節(jié)點(diǎn)）。通常鏈表的相關(guān)問(wèn)題可以用雙指針巧妙的解決，160. Intersection of Two Linked Lists 可以幫我們重新審視鏈表的操作。
• Hash Table：利用 Hash 函數(shù)來(lái)將數(shù)據(jù)映射到固定的一塊區(qū)域，方便 O(1) 時(shí)間內(nèi)讀取以及修改。37. Sudoku Solver 數(shù)獨(dú)是一個(gè)經(jīng)典的回溯問(wèn)題，配合 HashTable 的話，運(yùn)行時(shí)間將大幅減少。
• Tree：樹在計(jì)算機(jī)學(xué)科的應(yīng)用十分廣泛，常用的有二叉搜索樹，紅黑書，B+樹等。樹的建立，遍歷，刪除相對(duì)來(lái)說(shuō)比較復(fù)雜，通常會(huì)用到遞歸的思路，113. Path Sum II 是一個(gè)不錯(cuò)的開胃菜。
• Heap：特殊的完全二叉樹，“等級(jí)森嚴(yán)”，可以用 O(nlogn) 的時(shí)間復(fù)雜度來(lái)進(jìn)行排序，可以用 O(nlogk) 的時(shí)間復(fù)雜度找出 n 個(gè)數(shù)中的最大（小）k個(gè)，具體可以看看 347. Top K Frequent Elements。

算法：時(shí)間空間

我們知道，除了數(shù)據(jù)結(jié)構(gòu)，具體算法在一個(gè)程序中也是十分重要的，而算法效率的度量則是時(shí)間復(fù)雜度和空間復(fù)雜度。通常情況下，人們更關(guān)注時(shí)間復(fù)雜度，往往希望找到比 O( n^2 ) 快的算法，在數(shù)據(jù)量比較大的情況下，算法時(shí)間復(fù)雜度最好是O(logn)或者O(n)。計(jì)算機(jī)學(xué)科中經(jīng)典的算法思想就那么多，LeetCode 上面的題目涵蓋了其中大部分，下面大致來(lái)看下。

• 分而治之：有點(diǎn)類似“大事化小、小事化了”的思想，經(jīng)典的歸并排序和快速排序都用到這種思想，可以看看 Search a 2D Matrix II 來(lái)理解這種思想。
• 動(dòng)態(tài)規(guī)劃：有點(diǎn)類似數(shù)學(xué)中的歸納總結(jié)法，找出狀態(tài)轉(zhuǎn)移方程，然后逐步求解。 309. Best Time to Buy and Sell Stock with Cooldown 是理解動(dòng)態(tài)規(guī)劃的一個(gè)不錯(cuò)的例子。
• 貪心算法：有時(shí)候只顧局部利益，最終也會(huì)有最好的全局收益。122. Best Time to Buy and Sell Stock II 看看該如何“貪心”。
• 搜索算法（深度優(yōu)先，廣度優(yōu)先，二分搜索）：在有限的解空間中找出滿足條件的解，深度和廣度通常比較費(fèi)時(shí)間，二分搜索每次可以將問(wèn)題規(guī)?？s小一半，所以比較高效。
• 回溯：不斷地去試錯(cuò)，同時(shí)要注意回頭是岸，走不通就換條路，最終也能找到解決問(wèn)題方法或者知道問(wèn)題無(wú)解，可以看看 131. Palindrome Partitioning。

當(dāng)然，還有一部分問(wèn)題可能需要一些數(shù)學(xué)知識(shí)去解決，或者是需要一些位運(yùn)算的技巧去快速解決。總之，我們希望找到時(shí)間復(fù)雜度低的解決方法。為了達(dá)到這個(gè)目的，我們可能需要在一個(gè)解題方法中融合多種思想，比如在 300. Longest Increasing Subsequence 中同時(shí)用到了動(dòng)態(tài)規(guī)劃和二分查找的方法，將復(fù)雜度控制在 O(nlogn)。如果用其他方法，時(shí)間復(fù)雜度可能會(huì)高很多，這種題目的運(yùn)行時(shí)間統(tǒng)計(jì)圖也比較有意思，可以看到不同解決方案運(yùn)行時(shí)間的巨大差異，如下：

當(dāng)然有時(shí)候我們會(huì)犧牲空間換取時(shí)間，比如在動(dòng)態(tài)規(guī)劃中狀態(tài)的保存，或者是記憶化搜索，避免在遞歸中計(jì)算重復(fù)子問(wèn)題。213. House Robber II 的一個(gè)Discuss會(huì)教我們?nèi)绾斡糜洃浕阉鳒p少程序執(zhí)行時(shí)間。

語(yǔ)言：各有千秋

對(duì)一個(gè)問(wèn)題來(lái)說(shuō)，解題邏輯不會(huì)因編程語(yǔ)言而不同，但是具體coding起來(lái)語(yǔ)言之間的差別還是很大的。用不同語(yǔ)言去解決同一個(gè)問(wèn)題，可以讓我們更好地去理解語(yǔ)言之間的差異，以及特定語(yǔ)言的優(yōu)勢(shì)。

速度 VS 代碼量

C++ 以高效靈活著稱，LeetCode 很好地印證了這一點(diǎn)。對(duì)于絕大多數(shù)題目來(lái)說(shuō)，c++ 代碼的運(yùn)行速度要遠(yuǎn)遠(yuǎn)超過(guò) python 以及其他語(yǔ)言。和 C++ 相比，Python 允許我們用更少的代碼量實(shí)現(xiàn)同樣的邏輯。通常情況下，Python程序的代碼行數(shù)只相當(dāng)于對(duì)應(yīng)的C++代碼的行數(shù)的三分之一左右。

以 347 Top K Frequent Elements 為例，給定一個(gè)數(shù)組，求數(shù)組里出現(xiàn)頻率最高的 K 個(gè)數(shù)字，比如對(duì)于數(shù)組 [1,1,1,2,2,3]，K=2 時(shí)，返回 [1,2]。解決該問(wèn)題的思路比較常規(guī)，首先用 hashmap 記錄每個(gè)數(shù)字的出現(xiàn)頻率，然后可以用 heap 來(lái)求出現(xiàn)頻率最高的 k 個(gè)數(shù)字。

如果用 python 來(lái)實(shí)現(xiàn)的話，主要邏輯部分用兩行代碼就足夠了，如下：

num_count = collections.Counter(nums)
return heapq.nlargest(k, num_count, key=lambda x: num_count[x])

當(dāng)然了，要想寫出短小優(yōu)雅的 python 代碼，需要對(duì) python 思想以及模塊有很好的了解。關(guān)于 python 的相關(guān)知識(shí)點(diǎn)講解，可以參考這里。

而用 C++ 實(shí)現(xiàn)的話，代碼會(huì)多很多，帶來(lái)的好處就是速度的飛躍。具體代碼在這里，建立大小為 k 的小頂堆，每次進(jìn)堆時(shí)和堆頂進(jìn)行比較，核心代碼如下：

// Build the min-heap with size k.
for(auto it = num_count.begin(); it != num_count.end(); it++){
  if(frequent_heap.size() < k){
      frequent_heap.push(*it);
  }
  else if(it->second >= frequent_heap.top().second){
      frequent_heap.pop();
      frequent_heap.push(*it);
  }
}

語(yǔ)言的差異

我們都知道 c++ 和 python 是不同的語(yǔ)言，它們有著顯著的區(qū)別，不過(guò)一不小心我們就會(huì)忘記它們之間的差別，從而寫出bug來(lái)。不信？來(lái)看 69 Sqrt(x)，實(shí)現(xiàn) int sqrt(int x)。這題目是經(jīng)典的二分查找（當(dāng)然也可以用更高級(jí)的牛頓迭代法），用 python 來(lái)實(shí)現(xiàn)的話很容易寫出 AC 的代碼。

如果用 C++ 的話，相信很多人也能避開求中間值的整型溢出的坑：int mid = low + (high - low) / 2;，于是寫出下面的代碼：

int low = 0, high = x;
while(low <= high){
  // int mid = (low+high) / 2,  may overflow.
  int mid = low + (high - low) / 2;
  if(x>=mid*mid && x<(mid+1)*(mid+1)) return mid;
  else if(x < mid*mid)  high = mid - 1;
  else low = mid + 1;
}

很可惜，這樣的代碼仍然存在整型溢出的問(wèn)題，因?yàn)閙id*mid 有可能大于 INT_MAX，正確的代碼在這里。當(dāng)我們被 python 的自動(dòng)整型轉(zhuǎn)換寵壞后，就很容易忘記c++整型溢出的問(wèn)題。

除了臭名昭著的整型溢出問(wèn)題，c++ 和 python 在位運(yùn)算上也有著一點(diǎn)不同。以 371 Sum of Two Integers 為例，不用 +, - 實(shí)現(xiàn) int 型的加法 int getSum(int a, int b)。其實(shí)就是模擬計(jì)算機(jī)內(nèi)部加法的實(shí)現(xiàn)，很明顯是一個(gè)位運(yùn)算的問(wèn)題，c++實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，如下：

int getSum(int a, int b) {
    if(b==0){
        return a;
    }
    return getSum(a^b, (a&b)<<1);
}

然而用 python 的話，情況變的復(fù)雜了很多，歸根到底還是因?yàn)?python 整型的實(shí)現(xiàn)機(jī)制，具體代碼在這里。

討論：百家之長(zhǎng)

如果說(shuō) LeetCode 上面的題目是一塊塊金子的話，那么評(píng)論區(qū)就是一個(gè)點(diǎn)綴著鉆石的礦山。多少次，當(dāng)你絞盡腦汁終于 AC，興致勃發(fā)地來(lái)到評(píng)論區(qū)準(zhǔn)備吹水。結(jié)果迎接你的卻是大師級(jí)的代碼。于是，你高呼：尼瑪，竟然可以這樣！然后閉關(guān)去思考那些優(yōu)秀的代碼，順便默默鄙視自己。

除了優(yōu)秀的代碼，有時(shí)候還會(huì)有直觀的解題思路分享，方便看看別人是如何解決這個(gè)問(wèn)題的。@MissMary在“兩個(gè)排序數(shù)組中找出中位數(shù)”這個(gè)題目中，給出了一個(gè)很棒的解釋：Share my o(log(min(m,n)) solution with explanation，獲得了400多個(gè)贊。

你也可以評(píng)論大牛的代碼，或者提出改進(jìn)方案，不過(guò)有時(shí)候可能并非如你預(yù)期一樣改進(jìn)后代碼會(huì)運(yùn)行地更好。在 51. N-Queens 的討論 Accepted 4ms c++ solution use backtracking and bitmask, easy understand 中，@binz 在討論區(qū)中納悶自己將數(shù)組 vector<int> （取值非零即一）改為 vector<bool> 后，運(yùn)行時(shí)間變慢。@prime_tang 隨后就給出建議說(shuō)最好不要用 vector<bool>，并給出了兩個(gè) StackOverflow 答案。

當(dāng)你逛討論區(qū)久了，你可能會(huì)有那么一兩個(gè)偶像，比如@StefanPochmann。他的一個(gè)粉絲 @agave 曾經(jīng)問(wèn) StefanPochmann 一個(gè)問(wèn)題：

Hi Stefan, I noticed that you use a lot of Python tricks in your solutions, like "v += val," and so on... Could you share where you found them, or how your learned about them, and maybe where we can find more of that? Thanks!

StefanPochmann 也不厭其煩地給出了自己的答案：

@agave From many places, though I'd say I learned a lot on CheckiO and StackOverflow (when I was very active there for a month). You might also find some by googling python code golf.

原來(lái)大神也是在 StackOverflow 上修煉的，看來(lái)需要在 為什么離不開 StackOverflow 中添加一個(gè)理由了：因?yàn)?StefanPochmann 都混跡于此。

類似這樣友好，充滿技術(shù)味道的討論，在 LeetCode 討論區(qū)遍地都是，絕對(duì)值得我們?nèi)ズ煤锰皆L。

成長(zhǎng)：大有益處

偶爾會(huì)聽旁邊人說(shuō) XX 大牛 LeetCode 刷了3遍，成功進(jìn)微軟，還拿了 special offer！聽起來(lái)好像刷題就可以解決工作問(wèn)題，不過(guò)要知道還有刷5遍 LeetCode 仍然沒(méi)有找到工作的人呢。所以，不要想著刷了很多遍就可以找到好工作，畢竟比你刷的還瘋狂的大有人在（開個(gè)玩笑）。

不過(guò)，想想前面列出的那些好處，應(yīng)該值得大家抽出點(diǎn)時(shí)間來(lái)刷刷題了吧。

更多閱讀

跟波利亞學(xué)解題
為什么我反對(duì)純算法面試題
聊聊刷題
如何看待中國(guó)學(xué)生為了進(jìn) Google、微軟等企業(yè)瘋狂地刷題？
LeetCode 編程訓(xùn)練
國(guó)內(nèi)有哪些好的刷題網(wǎng)站?