小白一路走来,连续刷题三年,谈谈我的算法学习经验
數據結構與算法應該算是一個比較難的模塊,從小白一路走過來,從大一連續刷過好幾年題,看過挺多書,踩過挺多坑,也漲了一些經驗,姑且在這里分析一波對數據結構與算法 的學習經驗,請耐心看完,相信對你會有所幫助。
對于初學者來說,我認為選擇一本合適、不錯的算法書是非常非常重要的,從大一到現在我也看過不少的算法書,當然在學習算法的過程中也走過不少坑,刷了很少題,總結了不少經驗,下面說說
我的一些經驗吧,請耐心看完,相信一定對你有所幫助。
書籍視頻推薦
小白入門:書單、視頻推薦
數據結構與算法相關的書籍應該是我看的最多的一種數據吧,從大一到現在,從未間斷過,下面就介紹下從大一到現在都看過哪些自認為優秀的書籍,注意,我不知道適不適合你,但我覺得看的過程中很舒服。
1、數據結構與算法分析(c 語言描述版)
我相信大部分人大學看的教程都是清華大學出版社嚴蔚敏寫的那本書,說實話,作為初學者,那本書我沒能堅持看下去,可能比較適合大佬看吧。我自己買了一本《數據結構與算法分析(c 語言描述版)》,挺薄的,不過感覺很棒,這本書讓我學到了很多,個人感覺也挺容易懂的,代碼實現是采用 C 語言來實現的,不是偽代碼,如果你想學習數據結構,我覺得這本書是個不錯的選擇。班級里有挺多人看了《大話數據結構》,挺他們說也挺不錯,不過我沒看過。
2、挑戰程序設計競賽
這邊書也是大一時看的,學習算法,刷一些題是必須的,所謂3分理論7分實踐。如果你想刷題,我挺推薦這本書,里面分初級、中級到高級。雖然每道題沒有講的特別詳細,但當時都看懂了,真心不錯。不過高級那部分我是沒看,初級和中級看著挺舒服。也是學到挺多的,推薦給大家。
3、算法(第四版)
這本書估計是賣的最火的一本書吧,采用 Java 語言來實現的,不過在看這本書之前,我覺得你得要有一定的算法基礎,例如你得知道啥是隊列,啥是棧。我不認為這是本入門書籍,所以,你可以先學習
我上門推薦的那些書,有一定的基礎之后,再來學習這本。這本書主要是用大量的圖片來演示算法,讓人覺得比較友好。
4、編程之美
不用說,很美,這本書是我今年剛入手看的,只能用強烈推薦來形容,在這本書里,學到了挺多技巧,里面列舉的題也不是特別難,目前看了 80%,真香。剛開始我聽別人說如果要準備面試谷歌什么的建議看,我以為很難,遲遲沒買來看,不過,我看的過程中,感覺還好,相信你也能看的懂,想學習算法、刷題的,強烈推薦。
5、編程珠璣
這本老早就聽別人說過了,去年看的,不過也是看了80%左右,和編程之美一樣,強烈推薦,這本書里的題,說實話,感覺比編程之美有意思,
當然,數據結構與算法的還有很多優秀的書籍,我自己也看過不少,不過以上這些,我覺得很不錯。自己也買過算法導論等,不過,沒看的下去。
這些我也都準備了電子書籍,
不過我發現放百度鏈接容易失效,如果你感興趣的話,或許可以關注我的公眾號:苦逼的碼農,回復“電子書”獲取。
2、視頻介紹
作為初學者,學習算法是一個相對比較艱難的過程,比起看書,可能看視頻會相對好理解點,當然,這里引人而異,有些人喜歡看書不喜歡看視頻,這里主要是根據你自身來選擇了。
說起視頻,我自己看的也不多,我是屬于喜歡看書的那一種,不過我覺得這些這些視頻還不錯,推薦給大家。
1、牛客網有個初級和進階班的視頻,我覺得很不錯,不過我看過進階班的,初級班的沒看過,感覺還不錯,截圖如下:
2、直通bat班:這個我覺得也不錯,也是適合新手入門的那種
這些視頻我都有保存在我的百度云盤,不過可能涉及的版權問題,一下子就鏈接失效,所以就不直接貼地址了,感興趣的可以在我的公眾號:苦逼的碼農,回復“數據結構與算法”
來獲取。
當然,而已非常歡迎大家關注我的公眾號,我的公眾號主要寫算法、計算機基礎、Java等相關文章,已經有 100 多篇原創文章了,總結了很多與算法相關的技巧。好多文章被各大公眾號轉載。
刷題幾年,學習算法經驗分享
上面只是介紹了一些書籍和視頻,從另一個角度講,書籍和視頻只是一個工具,從大一學習算法到現在,刷了很多題,也是積累了一些經驗,下面跟大家分享下我的經驗吧,請耐心看完,相信你會有所收獲
切勿盲目刷題:刷題前的知識積累
說實話,想要提高自己的算法,我覺得就是腳踏實地著多動手去刷題,多刷題。
但是,如果你是小白,也就是說,你連常見的數據結構,如鏈表、樹以及常見的算法思想,如遞歸、枚舉、動態規劃這些都沒學過,那么,我不建議你盲目瘋狂著去刷題的。而是先去找本書先去學習這些必要的知識,然后再去刷題。
因為,如果這些基礎都不懂的話,估計一道題做了幾個小時,然后看答案都不不懂,做題沒有任何思路,這是很難受的。久而久之,估計沒啥動力了,我剛開始就是這樣,一道題答案看一天,然而還是不大懂,什么回溯啊,暴力啊,還不知道是啥意思。
也就是說,假如你要去諸如leetcode這些網站刷題,那么,你要先具備一定的基礎,這些基礎包括:
1、常見數據結構:鏈表、樹(如二叉樹)。(是的,鏈表和二叉樹是重點,圖這些可以先放著)
2、常見算法思想:貪婪法、分治法、窮舉法、動態規劃,回溯法。(貪婪、窮舉、分治是基礎,動態規劃有難度,可以先放著)
以上列出來的算是最基本的吧。就是說你刷題之前,要把這些過一遍再去刷題。如果你連這些最基本的都不知道的話,那么你再刷題的過程中,會很難受的,思路也會相對比較少。
總之,千萬不要急,先把這些基本的過一遍,力求理解,再去刷題。這些知識點,我上面已經給你們推薦了對應的書籍和視頻了,就不繼續說了。
所以你們千萬別指望以為自己把這些思想學完之后刷題會很牛,只有多刷題,只有多動手實踐,你的靈敏度才會提高起來。
總結下:
提高數據結構與算法沒啥捷徑,最好的捷徑就是多刷題。但是,刷題的前提是你要先學會一些基本的數據結構與算法思想。
AC不是目的,我們要追求完美
如何刷題?如何對待一道算法題?
我覺得,在做題的時候,一定要追求完美,千萬不要把一道題做出來之后,提交通過,然后就趕緊下一道。我認為這意義不大,因為一道題的解法太多了,有些解法態粗糙了,我們應該要尋找最優的方法。
算法能力的提升和做題的數量是有一定的關系,但并不是線性關系。也就是說,在做題的時候,要力求一題多解,如果自己實在想不出來其他辦法了,可以去看看別人是怎么做的,千萬不要覺得模仿別人的做法是件丟人的事。
我做題的時候,我一看到一道題,可能第一想法就是用很粗糙的方式做,因為很多題采用暴力法都會很容易做,就是時間復雜度很高。之后,我就會慢慢思考,看看有沒其他方法來降低時間復雜度或空間復雜度。最后,我會去看一下別人的做法,當然,并不是每道題都會這樣執行。
衡量一道算法題的好壞無非就是時間復雜度和空間復雜度,所以我們要力求完美,就要把這兩個降到最低,令他們相輔相成。
我舉道例題吧:
問題: 一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法?
這道題我在以前的分章分析過,不懂的可以先看下之前寫的:遞歸與動態規劃---基礎篇1
方法1::暴力遞歸
這道題不難,或許你會采取下面的做法:
public static int solve(int n){if(n == 1 || n == 2){return n;}else if(n <= 0){return 0;}else{return solve(n-1) + solve(n-2);} }這種做法的時間復雜度很高,指數級別了。但是如果你提交之后僥幸通過了,然后你就接著下一道題了,那么你就要好好想想了。
方法二:空間換時間
力求完美,我們可以考慮用空間換時間:這道題如何你去仔細想一想,會發現有很多是重復執行了。所以可以采取下面的方法:
//用一個HashMap來保存已經計算過的狀態 static Map<Integer,Integer> map = new HashMap(); public static int solve(int n){if(n <= 0)return 0;else if(n <= 2){return n;}else{//是否計算過if(map.containsKey(n)){return map.get(n);}else{int m = solve(n-1) + solve(n-2);map.put(n, m);return m;}} }這樣,可以大大縮短時間。也就是說,當一道題你做了之后,發現時間復雜度很高,那么可以考慮下,是否有更好的方法,是否可以用空間換時間。
方法三:斐波那契數列
實際上,我們可以把空間復雜度弄的更小,不需要HashMap來保存狀態:
public static int solve(int n){if(n <= 0)return 0;if(n <= 2){return n;}int f1 = 0;int f2 = 1;int sum = 0;for(int i = 1; i<= n; i++){sum = f1 + f2;f1 = f2;f2 = sum;}return sum; }我弄這道題給你們看,并不是在教你們這道題怎么做,而是有以下目的:
1、在刷題的時候,我們要力求完美。
2、我想不到這些方法啊,怎么辦?那么你就可以去看別人的做法,之后,遇到類似的題,你就會更有思路,更知道往哪個方向想。
3、可以從簡單暴力入手做一道題,在考慮空間與時間之間的衡量,一點點去優化。
挑戰自己,跳出舒適區
什么叫舒適區?在刷題的時候,可能有一類題是你比較懂的,你每次一看就有思路,然后半個小時就擼好代碼,提交代碼,然后通過了,然后,哇,又多刷了一道題,心里很舒服。
但是,記住,前期你可以多刷這種題練手,提升自己的樂趣,但,我還是建議你慢慢跳出舒適區,去做一些自己不擅長的題,并且找段時間一直刷這種題。例如,我覺得我在遞歸方面的題還是挺強的,
但是,我對動態規劃的題,很菜,每次都要想好久,每次遇到這種題都有點害怕,沒什么信心。不過有段時間我覺得只刷動態規劃的題,直接在 leetcode 選定專題,連續做了七八十道,剛開始很難受,
后來就慢慢知道了套路了,一道題從兩三個小時最后縮到半小時,簡單的十幾分鐘就搞定。感覺自己對這類型的題也不懼怕的。
所以,建議你,一定要學好跳出自己的舒適區。
推薦一些刷題網站
我一般是在leetcode和牛客網刷題,感覺挺不錯,題目難度不是很大。
在牛客網那里,我主要刷劍指Offer,不過那里也有個在線刷leetcode,不過里面的題量比較少。牛客網刷題有個非常方便的地方就是有個討論區,那里會有很多大佬分享他們的解題方法,不用我們去百度找題解。所以你做完后,實在想不出,可以很方便著去看別人是怎么做的。
至于leetcode,也是大部分題目官方都有給出答案,也是個不錯的刷題網站。你們可以兩個挑選一個,或者兩個都刷。
當然,還有其他刷題的網站,不過,其他網站沒刷過,不大清除如何。
至于leetcode,有中文版和英文版,個人建議英文版,英文版里面有各種大佬的解法分析。
leetcode有中文版
英文版
根據自己的興趣選。
學習一些解題技巧
說實話,有些題在你沒看別人的解法前,你好不知道有這么美妙優雅的解法,看了之后,臥槽,居然還可以這樣。而我們在刷題的過程中,就要不斷累積這些技巧,當你累計多了,你就會形成一種
神經反應,一下子就想到了某種方法。解題技巧很多,例如數組下標法、位圖法、雙指針等等,我自己也分享過一篇總結一些算法技巧的文章。給你舉個例子吧,有時候有些技巧真讓你大喊“臥槽”。
1、找出沒有重復的數
給你一組整型數據,這些數據中,其中有一個數只出現了一次,其他的數都出現了兩次,讓你來找出一個數 。
這道題可能很多人會用一個哈希表來存儲,每次存儲的時候,記錄 某個數出現的次數,最后再遍歷哈希表,看看哪個數只出現了一次。這種方法的時間復雜度為 O(n),空間復雜度也為 O(n)了。
然而我想告訴你的是,采用位運算來做,絕對高逼格!
我們剛才說過,兩個相同的數異或的結果是 0,一個數和 0 異或的結果是它本身,所以我們把這一組整型全部異或一下,例如這組數據是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出現了一次,其他都出現了兩次,把他們全部異或一下,結果如下:
由于異或支持交換律和結合律,所以:
1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。
也就是說,那些出現了兩次的數異或之后會變成0,那個出現一次的數,和 0 異或之后就等于它本身。就問這個解法牛不牛逼?所以代碼如下
int find(int[] arr){int tmp = arr[0];for(int i = 1;i < arr.length; i++){tmp = tmp ^ arr[i];}return tmp; }時間復雜度為 O(n),空間復雜度為 O(1),而且看起來很牛逼。
2、m的n次方
如果讓你求解 2 的 n 次方,并且不能使用系統自帶的 pow 函數,你會怎么做呢?這還不簡單,連續讓 n 個 m 相乘就行了,代碼如下:
int pow(int n){int tmp = 1;for(int i = 1; i <= n; i++) {tmp = tmp * m;}return tmp; }不過你要是這樣做的話,我只能呵呵,時間復雜度為 O(n) 了,怕是小學生都會!如果讓你用位運算來做,你會怎么做呢?
我舉個例子吧,例如 n = 13,則 n 的二進制表示為 1101, 那么 m 的 13 次方可以拆解為:
m^1101 = m^0001 * m^0100 * m^1000。
我們可以通過 & 1和 >>1 來逐位讀取 1101,為1時將該位代表的乘數累乘到最終結果。直接看代碼吧,反而容易理解:
int pow(int n){int sum = 1;int tmp = m;while(n != 0){if(n & 1 == 1){sum *= tmp;}tmp *= tmp;n = n >> 1;}return sum; }時間復雜度近為 O(logn),而且看起來很牛逼。
給你算法技巧,當然也可以關注我的公眾號:苦逼的碼農,專注與分享算法、計算機基礎等相關文章,已有100多篇原創,歡迎來撩。
推薦閱讀:一些常用的算法技巧總結
例如在刷題的時候,我們要學會巧用雙指針、數組下標法、位運算等等技巧來解決問題,可能會有意想不到的效果。我給你再找點我之前寫文章的一些例子吧:
分享一道解法巧妙的算法題
【算法技巧】位運算裝逼指南
這是個長期累積的過程,我自己也精彩在我的公眾號里分享一些解題的文章,感興趣的可以關注我的公眾號:苦逼的碼農。
再說數據結構發重要性
前面我主要是說了我平時都是怎么學習算法的。在數據結構方法,我只是列舉了你們一定要學習鏈表和樹(二叉堆),但這是最基本的,刷題之前要掌握的,對于數據結構,我列舉下一些比較重要的:
1、鏈表(如單向鏈表、雙向鏈表)。
2、樹(如二叉樹、平衡樹、紅黑樹)。
3、圖(如最短路徑的幾種算法)。
4、隊列、棧、矩陣。
對于這些,自己一定要動手實現一遍。你可以看書,也可以看視頻,新手可以先看視頻,不過前期可以看視頻,之后我建議是一定要看書。
例如對于平衡樹,可能你跟著書本的代碼實現之后,過陣子你就忘記,不過這不要緊,雖然你忘記了,但是如果你之前用代碼實現過,理解過,那么當你再次看到的時候,會很快就記起來,很快就知道思路,而且你的抽象能力等等會在不知不覺中提升起來。之后再學習紅黑樹啊,什么數據結構啊,都會學的很快。
最最重要
動手去做,動手去做,動手去做。重要的話說三遍。
千萬不要找了一堆資源,訂好了學習計劃,我要留到某某天就來去做.....
千萬不要這樣,而是當你激情來的時候,就馬上去干,千萬不要留到某個放假日啊什么鬼了,很多這種想法的人,最后會啥也沒做的。
也不要覺得要學習的有好多啊,不知道從哪學習起。我上面說了,可以先學習最基本的,然后刷題,刷題是一個需要長期堅持的事情,一年,兩年。在刷題的過程中,可以穿插和學習其他數據結構。
大家也可以關注我的公眾號:苦逼的碼農,在我的公眾號里,我也分享了很多與數據結構算法相同的文章,而且也分享了很多解題技巧。目前已分析了 100 多篇原創文章,下面是一些我覺得
很不錯的文章,強烈建議閱讀:
鏈表的重要性不言而喻,如果你把我分享的這10道題都搞懂了,那么你在鏈表方面算過關的了:
【鏈表問題】如何優雅著反轉單鏈表
【鏈表問題】打卡6:三種方法帶你優雅判斷回文鏈表
【鏈表問題】打卡9:將單鏈表的每K個節點之間逆序
【鏈表問題】刪除單鏈表中的第K個節點
鏈表問題】環形單鏈表約瑟夫問題
就不一道道列出來了,一共挑選了10還不錯的文章
十道鏈表打卡匯總
我還講解了一些常用數據結構與算法思想,每篇都通俗易懂著講解了,被各種號所轉發
1、為什么你學不會遞歸?告別遞歸,談談我的一些經驗
2、十大排序重要性不言而喻,文章還附帶了動畫、講解文章,代碼
必學十大經典排序算法,看這篇就夠了(附完整代碼/動圖/優質文章)(修訂版)
3、總結了刷題過程中常用的技巧,推薦閱讀:一些常用的算法技巧總結
4、用漫畫的形式講解了AVL樹:【漫畫】以后在有面試官問你AVL樹,你就把這篇文章扔給他。
5、大量圖講解了堆的各種操作:【算法與數據結構】堆排序是什么鬼?
索性把寫的一些文章鏈接都分享一波,大家可以挑感興趣的看算法與數據結構系列文章
也非常歡迎大家關注公眾號「苦逼的碼農」里面已有100多篇原創文章,我也分享了很多視頻、書籍的資源,以及開發工具,歡迎各位的關注,第一時間閱讀我的文章。
如果你覺得這篇內容對你挺有啟發,我想邀請你幫我三個忙,讓更多的人看到這篇文章:
1、點贊,讓更多的人也能看到這篇內容(收藏不點贊,都是耍流氓 -_-)
2、關注我和專欄,讓我們成為長期關系
3、關注公眾號「苦逼的碼農」,主要寫算法、計算機基礎之類的文章,里面已有100多篇原創文章
大部分的數據結構與算法文章被各種公眾號轉載相信一定能讓你有所收獲
我也分享了很多視頻、書籍的資源,以及開發工具,歡迎各位的關注我的公眾號:苦逼的碼農,每周推送幾篇原創文章,相信 會讓你有所收獲。
轉載于:https://www.cnblogs.com/kubidemanong/p/10996134.html
總結
以上是生活随笔為你收集整理的小白一路走来,连续刷题三年,谈谈我的算法学习经验的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 记一次诡异的SpringMVC中拦截路径
- 下一篇: 0x57~0x59