刷 leetcode 需要哪些基礎？

12-31

幹了快2年的J2EE開發，基本都是增刪改查，寫寫頁面和JS之類的，最近準備刷leetcode ，需要哪些基礎？打算先學些再刷題。數據結構？演算法？請指教。

先說一句：隨著Google那邊的難度的水漲船高（參考Google的APAC Test/Kickstart），LeetCode上的知識點範圍擴大不是不可能的，甚至是必然趨勢。今天一看，連LeetCode上都有線段樹/樹狀數組的題了，而且還是二維的，還有幾何的題（求凸包的裸題，啊順帶一提，我MS的manager，辛苦想了半天實習生轉正面試題，結果就想出來這麼個東西，我表示比較失望……）那這樣下去，以後冒出來二分圖匹配/網路流什麼的，似乎也沒什麼好奇怪了……

=====================更新的分割線=======================

2017.06.01 12:50

一爬起來，居然有100+的贊了，受寵若驚。懷疑是不是被最後一個題嚇到了？

這當然不是面試真題了~不過和我Google某一輪面試的觀感差不多。開門先問一個很經典、就要爛大街的並查集問題（動態加1的LeetCode 200，即LeetCode 305，其實根本不Hard，不過是這個並查集太少出題罷了），然後問，在上一問寫了會路徑壓縮+按權合併（啟發式合併）的並查集的基礎上，請加入回撤上一步操作的功能（回撤只會使用1次，不會連續使用2次或更多次，即一定會是：修改-回撤-修改）……

整場面試就這麼兩問，像高考數學一樣，遞進的兩問。

（幸好自己似乎聽說過這種東西，想起來了，不然可能栽了。）

對Google這樣的公司來說，在選擇校招/很短工作經驗的面試者的時候，出這種題可能是個必然的選擇。問經驗來看你的水平的話，肯定很不足的，那就考察思維能力和相關素質。考這個的話，我問原題，很可能還把背面經的人選進來了，那我也只能辛苦自己，（可以基於原題基礎上）想一些至少在面經中比較新的idea了。

然後題目就顯得比較過分了……比如 2016微軟探星夏令營在線技術筆試（hihocoder上的1341~1344），1341、1342還好，1343、1344就有些劇毒了。

http://hihocoder.com/problemset/problem/1343

http://hihocoder.com/problemset/problem/1344

感興趣的同學可以試試看。

至於最後一題的思路……其實中間的問題2就是提示。有2種思考方向，不妨都試試看？

更進一步的提示：能否給出一個，與坑數相關的，非指數/階乘級別時間複雜度的演算法（如果假設這裡大整數加減乘除計算操作的時間複雜度是O(1)的話）（我沒說線性哦~）？

劇透警告：已經有人在評論區給出了最後一題的原題地址和思路了。請在想到idea前，或者放棄思考前，不要去開評論區。（要完整通過（Accepted掉）原題，還涉及到離散數學/數論中逆元的知識，面試中很小可能把這個作為考點……當然，要你解釋RSA原理的這類時候例外，但這個已經是比較專門的領域了）

=====================更新的分割線=======================

我們先打住。LeetCode上提供了按Tag選題的功能，而且還提供了Tag對應的題數（有重複，一題可以打多Tag）。我們不妨看看從多到少，分別是哪些題型/知識點非常泛濫：

先說一下：有些分類（數組、字元串、數學）中的最簡單的那批題目，其實有時候應該拉出來，單獨搞一個分類，implementation（粗暴地實現），也就是說，按理說你學了一種常見語言就應該會寫的。

數據結構中，其實結構就2大類：線性的、非線性的。

線性的，按實現方式區分，連續的數組，非連續的鏈表。其中有2種特殊操作方式的，棧和隊列。

非線性的，樹形結構和圖結構。

仔細觀察，可以發現，線性結構中，數組上搞事佔了絕對大頭：數組自己這個分類就很大，然後一部分二分搜索、雙指針方法等都有不少相關題目。

非線性結構中，樹比圖的題目多，深度優先搜索比廣度優先搜索的題目多。

然後哈希表名列前茅，也沒什麼奇怪的吧……數組下標不方便用字元串？沒關係，扔進Key-Value的數據結構里去，不需要有序就哈希表Hashmap，需要有序再上基於平衡樹的map Treemap。如果要維護一個有沒有x的集合，而x範圍很大，那和map的道理類似，用相應的set就行了。

然而大部分時候不需要有序的，那哈希表這種理論複雜度O（1）的東西受青睞也沒什麼奇怪的了。

演算法方向上，

動態規劃非常熱門（我覺得有些屬於遞推的題目很可能划進去了，而且這個分類這麼熱，有些出乎意料但在情理之中）。

字元串類的題目……其實啥都沾邊，暴力的實現、動態規劃的思想、字典樹這種數據結構，還有一些諸如後綴數組、KMP等演算法。

數學……看了一眼，已經有按每位算過去的數位dp/遞推了哦~當然，如果什麼時候出現了費馬小定理/中國剩餘定理什麼的，大家可以掀桌子不玩了（我的意思是，現在當然沒有，在可見的5~10年內，也不太可能有，畢竟動態規劃那邊的潛力沒挖掘完，除非崗位對數論要求高，否則沒必要做出（相當於向普通程序員出網路流/線段樹的題這種）出特定的人才學過的數論題的行為來）。

然後我們可以發現，接下去2位是二分搜索和雙指針/尺取法了。

二分搜索比較有名氣了，這個不知道請自行補課。雙指針/尺取法的思想……較新的面經書上似乎開始討論這個話題了，也可以自己搜一下。

然後深度優先搜索和廣度優先搜索，2種暴力枚舉所有情況的經典框架。不過樹上深搜相對多一點，圖上找最短路，其實可以把廣度優先搜索改一改，就行了。而且，在有些時候，可能通過不同的途徑，搜索到相同的子狀態，這時候用記憶化的方法，去除之後的重複搜索來加速（這已經變成動態規划了，不過是從要解決的目標開始的自頂向下的順序，而不是遞推解動態規劃的，從最小問題開始往上合併的自底向上了）。後面的極大極小搜索（2個人對弈遊戲，問誰會贏這種，不過一般極大極小搜索的話，數據範圍不大）也可以算在深度優先搜索裡面。

再往後，貪心的題，如果沒見過，要想出來就太看臉了，很少出；排序，單機上的，基本都是固定套路，多機上的那是另一回事了；分治是泛化的二分搜索，也就是，我不一定二分了，可能三分什麼的；圖論的，考得少主要因為，那個存儲圖的結構，哪邊寫都煩；剩下的，10題以內的，都是國內公司基本不可能去考的了。

然後還有一個分類，構造。直接說就是，分析題目意思，想出一種辦法，保證能夠滿足題目要求並實現出來。可以劃成貪心，因為大部分時候，每步操作非常簡單粗暴；但是也和那些貪心題不一樣，貪心的題，不少比較難證明正確性，構造類的相對還好一點……

==============================================================

最後提一點自己的思考？

1、Google什麼的，可能是比較合適的風向標啊？比如Google Code Jam出了一個構造類的題，然後第二年就見到2家公司校招題把這個拿出來了……而且一個題型似乎會很容易流行開來，比如區間dp類的（最早騰訊實習生，最長迴文子序列，然後Google、愛奇藝都搞了一個區間dp的題……）

2、其實面試題什麼的，不一定說要考你數據結構上/演算法上相當麻煩的部分（除非你去面對這方面有需求的崗位，比如機器學習、編譯器等），對普通程序員崗位來說，理清一個問題，盡量無錯又高效地實現出來，才是最重要的吧？

個人感覺：炫技的，看過才可能知道的那種小技巧類題目，會越來越不受待見。但是這兩類題目還是會很多的：

1、要求似乎不難，比較清晰，但是一些要注意的細節比較多。

2、需要對題目進行一定分析，才能想到解答思路的。

==============================================================

順帶附贈動態規劃/遞推類題目的完整例子一個：（反正是陳題了，哪家公司現在還抄過去，那就有點逗了）

1、如下圖，從左上角的a走到右下角的b，每一步，你只可以向右走一格或向下走一格。請問你有多少種不同的路線？（2種路線，只要不是完全重合的，就被認為不同。或者說，如果存在某一步第x步，這兩個路線中，這一步採取的行動不一樣，就被認為是不一樣的。）

2、我們來加碼了。

現在這個地圖上，還有一些坑（黑色格子），我們不能踩進去，當然也不能從坑裡走出來。

對下面這兩張圖，請單純用紙筆計算從a走到b的不同的方案數，並展示你的計算過程。

（允許2張圖用2種不同的思路，當然也可以用同一種思路）

3、我們繼續加碼。

這個地圖最後不只是5*5/6*6那麼小了，你需要處理最大10萬*10萬的地圖了。不過幸運的是，坑增加的不多，整個地圖上最多1000個坑。我們保證，起點a一定在左上角，終點b一定在右下角，並且a和b 2點上一定沒有坑。

請根據上述的情況，設計一個儘可能高效的演算法。（假設實現你的演算法的時候，所用的編程語言提供了非常高效的高精度計算方法，大整數計算這裡的效率損失不需要考慮）

學習CS61B，把數據結構學紮實了http://datastructur.es/sp16/

CS170https://www.youtube.com/playlist?list=PLkFD6_40KJIyWjuw0JJ0WzFlDWyVK5ZfF

了解基本的數據結構後就可以開始刷，或者邊刷邊學。重點在於堅持
我覺得這樣比較好

1. 按照AC率，從高到低，看著自己的Solved Problems漸漸變多，會有小小的成就感。

2. 刷每個Tag下的AC率最高的題，了解這個類別的套路。

3. 現在題目越來越多，很多題目都是英語閱讀理解，一大串的英文，就是說只要看懂題意，會發現其實不是很難。

4. 多總結，刷完之後肯定要歸納總結的，費曼式學習技巧（就是通過講給別人聽，寫給別人看，來學習），可以放到自己的Github上，也可以自己寫博客。

5. 除了Leetcode本身的Solution還有Discuss，我覺得這裡的代碼也可以借鑒學習haoel/leetcode 手動 @陳皓

最近和小夥伴在這裡

Leetcode - UStopia

每天刷題，有興趣可以加入我們，或者私信我微信小組。

個人經驗，刷完leetcode你也過不了谷歌中國區的面試。事實上要求很低，有些基本的理解就行，能大致判斷演算法複雜度，對分治動態規劃樹有了解就可以了。樂趣就在於思考演算法本身，不斷改進演算法的複雜度。

直接去刷吧，然後就知道自己缺啥了。

如果還不知道，看看優秀答案，對比一下自己，也就知道了。

強行安利。

最重要的不是看演算法導論，直接看你也看不懂。

看兩本數學書: 組合數學+最優化理論（運籌學）。

看完之後，再回過頭去想那些語言層面的東西，稍微積累一些題目經驗，你就到了真.程序員鄙視鏈的上層。刷起來你不心虛，腰不酸腿不疼，輕鬆不看答案激進前10%

（我能說我刷了十幾道dp，然後輕鬆pass，然後棄了嗎？）

ps.這不是廣告，那兩門課中國的佈道者是陳景潤，吳文俊，李政道等先賢大牛。所以這真心不是廣告……（廢話，我閃）

學了數據結構就差不多夠了。。。第一次刷實在不懂就看答案。。看別人怎麼分析的看懂了自己寫一遍。第一遍會特別慢，堅持下去就好。

如果題主數據結構和演算法的底子比較差，建議題主買一本《演算法競賽入門經典》紫色的那本。紫書大概看一遍，對你刷題是很有幫助的。還有就是多看別人的代碼，對比自己寫的代碼。你會發現很多奇技淫巧。

補充我推薦的那本書例子都是用c++寫的，考慮到題主主要搞java，嗯..其實思想都是相通的。

咋那麼多人推薦劉佳汝的，

我想說我一個ACMER一開始自學劉佳汝到後面都痛苦的要死（大概是動態規劃章），還是先看張新華的書入門再回來看的

工程類的演算法書不是有演算法4和演算法導論之類了嗎，演算法競賽很多奇技淫巧還用得上？

沒學過數據結構的話就學一下，再看看劉汝佳那本書，夠了

根據題主的提問，我的理解是題主之前沒有學過數據結構和演算法。如果學過的話，學的還行沒全忘了的話可以直接刷。

沒學過，但是已經流暢寫程序的人直接刷也是可以的。

然後就看你的目標是刷到什麼程度了，是自己練習一下增長一下對演算法的了解呢，還是刷到可以面進Google/Facebook這種級別公司的水平呢。

如果是前者，直接看書就可以，時間少偏向實用可以看Algorithms（中文名叫演算法概論，有JAVA有cpp可選），時間多有心情可以看著名墊桌角磚頭……演算法導論。看書的同時自己練習一下，另外習題視你目標而定也可以走過路過不要錯過。

如果是後者，推薦先按照上一段找一本書看，再刷題，這樣效率才高。那些面試的演算法題，終究是考驗快速把一個已知演算法套用到問題上的能力（當然簡單耿直的面試題可能只需要你見過這類題）。需要的不是當場想出來而是之前涉獵的演算法儲量要夠才能隨時拿出來應用。那麼要做的事情就很簡單了，找本比較全面的演算法書先刷一遍書，整體有個感覺，提到一類演算法常用的都有啥複雜度是啥心裡有個感覺，再刷leetcode強化這種應用的感覺，就會更有效率（雖然lc的題我感覺都偏耿直呢……）

非CS專業或者CS專業但對計算機課程已經沒什麼概念的的，建議先看書。選定一門語言，看概念以及把書上的例子、習題寫代碼實現一遍，習題不需要全做，只要覺得自己掌握就可以了。學習了基礎知識之後再去刷題。我個人認為，有了一個大概的框架之後有了基礎再去刷題更好。推薦《劍指offer》這本書，特別適合求職用的，書裡面對演算法和數據結構的知識總結的很全面，同時，也有提供在線評測的地方：《劍指offer課後習題在線評測》，簡直 perfect!

當然，CS專業的可以直接刷題，刷題不僅是用來練習，而且可以用來學習。查漏補缺，不懂的看 LEETCODE/LINTCODE 答案解析，看了理解；如果看不懂，可以翻翻書先了解一下概念，看一下定義以及書上的簡單例題；懂了不會寫，照著答案打幾遍，然後爭取自己寫出來。套路都是這樣的，只要堅持。這樣比看了書再刷題有用，你刷了題才知道自己哪裡不會。一開始進度很慢，不要氣餒，慢慢速度會提上去的。

刷題刷到後期你會發現，刷題主要就是訓練自己的思路，看到題之後有思路就說明你刷題是有成效的。所以從一開始你就要注意總結你做過的題，多思考，特別是沒有思路的題。刷題過程中可以做筆記。入門之後也可以逛逛博客，借鑒別人的代碼，看別人是怎麼優化代碼的。最終要達到的境界是：看題有思路，解題有套路，面試無彎路。

可以看看cracking the code interview，然後直接動手即可。從簡單的開始，很快就上手了。做過多的準備那是拖延症的表現啊，很多時候就是準備太多了，還不如一言不合就是干！

如果你不是「練習」而是「學習」直接看答案吧先看懂幾天後不看答案寫這樣才有效率坐在那裡生想並不能幫助你學習

學好數據結構，建議看《大話數據結構》，之後看一些編程面試之類的書《編程之美》《cracking the coding interview》，基礎打牢了最後再刷題，事半功倍

更新：演算法導論這種書雖然很厚，但也可以翻一翻看看大致有什麼常見模型，divide-and-conquer，sorting，dynamic programming，graph traversal dfs，graph traversal bfs，binary tree search and manipulation什麼的，刷題量不是關鍵，關鍵是你是否掌握了精髓，遇到類似的題思路清晰能夠舉一反三

其實演算法和數據結構學好了就行了

我那個時候還只有300題左右

我刷了四遍lc，第一遍最慢，刷了幾個月，每天只能做出來幾道題，抓耳撓腮的想。到第四遍的時候一個禮拜能過一遍就覺得沒意思了。

重要的是刷完心虛的題要過段時間再刷。

準備下常見的數據結構和演算法，還是基本都能拼出來的，另外自己日常的代碼積累也是很重要的這個能提升寫代碼的feel，從而在答題時能在更短的時間內寫出代碼風格良好，邏輯清晰正確的代碼。

數據結構大致看看，刷Leetcode不看數據結構問題也不大。Leetcode難度一般，別給自己心裡暗示，直接刷即可！

刷完記得看看高票答案，很多高票解法相當有意思。

對於leetcode，你只需要理解數據結構和演算法就可以了！當然第一遍：實現題目功能；第二遍：優化演算法。然而面試時發現作用不大，問的最多的是操作系統和網路。哈哈

基本的就是數據結構和演算法，最重要的是智商和經驗

刷了就知道了。leetcode的好處是有難度標示，先做簡單的再做難的，不懂就上網查或者翻書吧。

不需要啥基礎啊，cs的本科直接上去敲就可以了，不會了看看別人的解決方法。沒啥的。