前言
作為一名非科班出身的程式員,我是參加工作之後才開始接觸算法,學算法至今有将近五年的時間,期間輸出文字約 100 多萬,從算法小白到寫出百萬閱讀的算法文章,這一路曆程,有心酸也有掌聲。
過往曆曆在目,沒有誰比我更了解算法小白的焦慮與迷茫。
每每在公衆号背景看到讀者留言求教時,我都在想:我能為他們做點什麼。
我決定把我曾經踩過的坑以及總結出來的經驗毫無保留的分享給你,希望能為你撥開迷霧。
這些經驗并不會适合每個人,但或許也能對你有所啟發。
今天這篇文章聊的話題就是新手如何有效的刷算法題(LeetCode)。
如果你想要開始刷題,那麼第一步就是:打開 LeetCode 官網,點選标簽,選擇一道順眼的題目開始刷。
注意,在這過程中,不要左思右盼,不要去搜尋與思考到底是刷 LeetCode 好還是去牛客網刷劍指 Offer 好。
我作為一名算法小白的時候,就犯了這個錯誤:在粗略的了解基本的資料結構與算法後,準備開始刷題,總想着找一個最有效最好的刷題平台。
一會在 LeetCode 題解區逛逛,一會在牛客網看看面經,結果就是整個人煩躁不安,焦慮迷茫,題沒有刷幾道,羨慕嫉妒恨卻增加了幾分:别人的代碼怎麼這麼簡潔 ?别人的 Offer 怎麼這麼亮眼?
經過痛定思定之後,我開始自我剖析自己想好好刷題卻無效的原因:
1、沒有接受自己是算法小白的事實
我那時候隻是按圖索骥般的稍微系統的接觸了基礎資料結構與算法知識,根本沒有真正的利用這些知識去處理問題。
在刷題的過程中,總想證明自己可以的,别人可以寫成簡潔高效的解題方法,我也要!于是去不停的找題證明自己,結果就是越刷越沒有效果,自己根本就看不懂題目考察的資料結構與思想。
整個人完全奔潰,不刷題了,不準備算法面試了,不準備跳槽了!
後來我不停的告誡自己:作為一名非科班的程式員,肯定比不上他們呀,如果随随便便的學了一點就能刷題順利,那别人大學四年不白學了!
是以前期先接受自己的思考方式,暴力解法其實也是一種有效的解法。
2、沒有合理的刷題
我隻是盲目的追求刷題的數量,即使刷了 200 道,腦中依舊一團漿糊。
後來才明白,吃透一道題目比亂刷十道題目更有價值。
經過不斷的摸索與試驗,形成了自己的一套刷題路徑。
- 自己的解法
- 網上好的解法
- 自己的解法可以優化的地方
- 不停的優化
- 尋找相同的題型
- 總結
每一個題目都經過至少一遍這樣的疊代,徹底吃透一道題進而掌握一種題型。
以一道極其簡單的動态規劃題為例 ,LeetCode 第 70 号問題:爬樓梯。
當時的我根本不知道動态規劃的相關概念,什麼狀态,什麼轉移方程,通通沒聽過。
沒錯,當時就那麼菜!
二話不說,直接使用暴力解法。
class Solution {
public int climbStairs(int n) {
return calcWays(n);
}
private int calcWays( int n ){
if ( n == 1) return 1;
if ( n == 2) return 2;
return calcWays(n-1) + calcWays(n-2);
}
}
很明顯,無腦的遞歸暴力解法包含了大量的重複計算,送出上去直接标紅提示超出時間限制。
後來看了網上高票答案的分析,知道了備忘錄的概念,于是很容易寫出優化後的代碼。
//采用備忘錄的方式來存子問題的解以避免大量的重複計算
class Solution {
int[] memo;
public int climbStairs(int n) {
memo = new int[n+1];
return calcWays(n);
}
private int calcWays( int n ){
if ( n == 1) return 1;
if ( n == 2) return 2;
if (memo[n] == 0)
memo[n] = calcWays(n-1) + calcWays(n-2);
return memo[n];
}
}
再後來,發現備忘錄是自頂 向下的方式,稍許變動,修改為自低 向上的遞推方式就是動态規劃的形式。
class Solution {
public int climbStairs(int n) {
int[] memo = new int[n+1];
memo[0] = 1;
memo[1] = 1;
for(int i = 2 ; i <= n; i++){
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
}
按照這樣的刷題路徑下來,發現對這類題型有了初步的思考途徑,有了發力點,再也不會一籌莫展:看題懵逼半小時,Coding 隻會按空格。
徹底搞懂這題後,就需要找到類似的題型,然後不斷的重複練習:最小路徑和、整數拆分、完全平方數、解碼方法、不同路徑、不同路徑 II。
通過這些練習,尋找題目中的共同點,為什麼這類題型都可以這樣思考呢?
慢慢的,知道了最優子結構、狀态轉移方程、重疊子問題的概念,不知不覺動态規劃的知識點已經掌握了 80%。
再遇到更高難度的動态規劃的題目時,心裡也明白,一時半會沒做成無法就是最優子結構、狀态轉移方程、重疊子問題沒有理清楚。
這樣長期堅持下來,接觸新的題型時也可以從容不迫的思考。
後記
如果說成為大神有什麼訣竅的話,那就是相信時間的力量,每天進步一點就夠了!