由於我之前一直強調數據結構以及算法學習的重要性,所以就有一些讀者經常問我,
一、算法最最基礎
1、時間複雜度
2、空間複雜度
一般最先接觸的就是時間複雜度和空間複雜度的學習了,這兩個概念以及如何計算,是必須學的,也是必須最先學的,主要有最大複雜度、平均複雜度等,直接通過博客搜索學習即可。
文章推薦:
算法分析神器—時間複雜度
1、線性表
列表(必學)鏈表(必學)跳躍表(知道原理,應用,最後自己實現一遍)並查集(建議結合刷題學習)不用說,鏈表、列表必須,不過重點是鏈表。
三分鐘基礎數據結構:如何輕鬆手寫鏈表?
以後有面試官問你「跳躍表」,你就把這篇文章扔給他
2、棧與隊列
棧(必學)隊列(必學)優先隊列、堆(必學)多級反饋隊列(原理與應用)特別是優先隊列,再刷題的時候,還是經常用到的,隊列與棧,是最基本的數據結構,必學。可以通過博客來學習。相關文章:
三分鐘基礎知識:什麼是棧?
二叉堆是什麼鬼?
【算法與數據結構】堆排序是什麼鬼?
3、哈希表(必學)
碰撞解決方法:開放定址法、鏈地址法、再次哈希法、建立公共溢出區(必學)布隆過濾器(原理與應用)哈希表相關的,推薦通過博客來學習,推薦文章:
Hash衝突之開放地址法
4、樹
二叉樹:各種遍歷(遞歸與非遞歸)(必學)哈夫曼樹與編碼(原理與應用)AVL樹(必學)B 樹與 B+ 樹(原理與應用)前綴樹(原理與應用)紅黑樹(原理與應用)線段樹(原理與應用)樹相關是知識還是挺多的,建議看書,可以看《算法第四版》。相關文章:
高頻面試題:什麼是B樹?為啥文件索引要用B樹而不用二叉查找樹?
【漫畫】以後在有面試官問你AVL樹,你就把這篇文章扔給他。
騰訊面試題:有了二叉查找樹、平衡樹為啥還需要紅黑樹?
【面試被虐】遊戲中的敏感詞過濾是如何實現的?
5、數組
樹狀數組矩陣(必學)樹狀數組其實我也沒學過,,,,
三、各種常見算法
1、十大排序算法
簡單排序:插入排序、選擇排序、冒泡排序(必學)分治排序:快速排序、歸併排序(必學,快速排序還要關注中軸的選取方式)分配排序:桶排序、基數排序樹狀排序:堆排序(必學)其他:計數排序(必學)、希爾排序對於十大算法的學習,假如你不大懂的話,那麼我還是挺推薦你去看書的,因為看了書,你可能不僅僅知道這個算法怎麼寫,還能知道他是怎麼來的。推薦書籍是《算法第四版》,這本書講的很詳細,而且配了很多圖演示,還是挺好懂的。
推薦文章:
必學十大經典排序算法,看這篇就夠了(附完整代碼/動圖/優質文章)(修訂版)
圖還是比較難的,不過我覺得圖涉及到的挺多算法都是挺實用的,例如最短路徑的計算等,圖相關的,我這裡還是建議看書的,可以看《算法第四版》。
漫畫:什麼是 “圖”?(修訂版)
漫畫:深度優先遍歷 和 廣度優先遍歷
漫畫:圖的 “最短路徑” 問題
漫畫:Dijkstra 算法的優化
漫畫:圖的 “多源” 最短路徑
3、搜索與回溯算法
貪心算法(必學)啟發式搜索算法:A*尋路算法(瞭解)地圖著色算法、N 皇后問題、最優加工順序旅行商問題這方便的只是都是一些算法相關的,我覺得如果可以,都學一下。像貪心算法的思想,就必須學的了。建議通過刷題來學習,leetcode 直接專題刷。
4、動態規劃
樹形DP:01揹包問題線性DP:最長公共子序列、最長公共子串區間DP:矩陣最大值(和以及積)數位DP:數字遊戲狀態壓縮DP:旅行商我覺得動態規劃是最難的一個算法思想了,記得當初第一次接觸動態規劃的時候,是看01揹包問題的,看了好久都不大懂,懵懵懂懂,後面懂了基本思想,可是做題下不了手,但是看的懂答案。一氣之下,再leetcdoe專題連續刷了幾十道,才掌握了動態規劃的套路,也有了自己的一套模板。不過說實話,動態規劃,是考的真他媽多,學習算法、刷題,一定要掌握。這裡建議先了解動態規劃是什麼,之後 leetcode 專題刷,反正就一般上面這幾種題型。後面有時間,我也寫一下我學到的套路,有點類似於我之前寫的遞歸那樣,算是一種經驗。也就是我做題時的模板,不過感覺得寫七八個小時,,,,,有時間就寫。之前寫的遞歸文章:為什麼你學不會遞歸?告別遞歸,談談我的一些經驗
5、字符匹配算法
正則表達式模式匹配:KMP、Boyer-Moore我寫過兩篇字符串匹配的文章,感覺還不錯,看了這兩篇文章,我覺得你就差不多懂 kmp 和 Boyer-Moore 了。
字符串匹配Boyer-Moore算法:文本編輯器中的查找功能是如何實現的?
6、流相關算法
最大流:最短增廣路、Dinic 算法最大流最小割:最大收益問題、方格取數問題最小費用最大流:最小費用路、消遣這方面的一些算法,我也只瞭解過一些,感興趣的可以學習下。
總結
對於上面設計到的算法,我都提供了感覺還不錯的文章,建議大家收藏,然後可以利用零碎的時間進行閱讀,有些人可能會覺得上面的算法太多,說實話,我覺得不多,特別是對於在校生的,上面涉及到的算法可以不用很懂,但至少得了解。至於書籍的話,如果你連基本數據結構都還不懂的,建議看《數據結構與算法》相關書籍,例如《大話數據結構》、《數據結構與算法分析》。如果你有一定的基礎,例如知道鏈表,棧,隊列,那麼可以看《算法第四版》,不過這本書是用 Java 實現的,不過我覺得你只要學過 C,那麼可以看的懂。
這些算法的學習,雖然你覺得學了沒有什麼用,但還是那些話,它對你的影響是潛意識的,它可以給你打下很深厚的基礎內功,如果你想走的更遠,那麼我推薦學習,標註必學的,那麼我覺得,你是真的需要抽時間來學習下,標註原理與應用的,代表你可以不知道怎麼用代碼實現,但是必得知道它的實現原理以及應用,更多算法的學習,可以持續關注我的微信公眾號勒。
作為一個非常注重計算機基礎以及算法學習的程序員,一路自學走來,看過挺多不錯的優質書籍,在這裡推薦給大家,全都是自己看過滴。
最後,很多人問我都是怎麼學習的,那我乾脆就把我看過的優質書籍貢獻出來:
計算機基礎入門推薦:《程序是怎樣跑起來的》、《網絡是怎樣連接的》、《計算機是怎樣工作的》
進一步認識計算機網絡:《計算機網絡:自頂向下》、《圖解http》
數據結構+算法入門:《數據結構與算法分析:C語言描述版》,《大話數據結構》、《阿哈算法》
算法進階:《算法第四版》、《編程之美》、《編程珠璣》
由於我是Java技術棧的,順便推薦基本Java的書籍,從左到由的順序看到
Java:《Java核心技術卷1》、《編程思想》、《深入理解Java虛擬機》、《Java編程藝術》
數據庫:《mysql必知必會》、《MySQL技術內幕:InnoDB存儲引擎》
就先介紹這麼多,這些都是最基礎最核心滴,希望對那些不知道看什書的同學有所幫助。