如何系統地學習算法?

athenacool


如果你是在校學生,最好跟著老師一步一步來,這麼學術的東西在學校裡學是最好不過的。

如果你是轉行的,建議先學習下現有的經典算法,全部學明白,再去網上搜索些大神的思路,慢慢學吧。


PPt小助手


你好我是世歡科技,很高興回答你的問題,如何系統的學習算法,我有以下幾點建議;

1.入門系列:

《算法圖解》:“像小說一樣有趣的算法入門書”,主打“圖解”,通俗易懂

《大話數據結構》:把理論講得有趣不枯燥;每個數據結構和算法,作者都結合了生活中的例子,能讓你有非常直觀的感受。

2.教科書系列:

《數據結構與算法分析》:很多大學都拿它當作教材,非常系統、全面、嚴謹,適合掌握了至少一門編程語言的同學。

作者也很貼心,這本書有三種語言的版本:《數據結構與算法分析 : C 語言描述》《數據結構與算法分析 : C++ 描述》《數據結構與算法分析 : Java 語言描述》。

3.進階之旅:

《算法導論》:有了一定基礎之後,就可以開始啃這本大部頭了。

5.擴展閱讀:

《算法之美》:算法科普,從生活中的各種問題說起:租房、談戀愛、老虎機、拍電影、面試、買彩票、各種排序、找停車位、尋找新藥、臨床試驗、奧巴馬拉贊助、預估電影票房等等,非常生活化,可以作為補充閱讀。

《算法帝國》:同樣是科普類書籍,並無涉及算法的原理與實現細節,也可以作為補充閱讀。

6.殿堂級

《計算機程序設計藝術》:包含很多卷,深度、廣度、系統性、全面性是其他所有數據結構和算法書籍都所無法相比。可以當做一種挑戰~

這是我以上所有的建議希望對你有用,還有什麼不懂可以評論或者私信我


世歡科技老田


從廣義上講,數據結構就是指一組數據的存儲結構。算法就是操作數據的一組方法。

從狹義上講,是指某些著名的數據結構和算法,比如隊列、棧、堆、二分查找、動態規劃等

一、夯實基礎

在最初的階段,算法世界的大門剛剛打開,這個時候迷茫是正常的,解決迷茫的要訣在於少想多做,勇往直前。懷著一顆"千磨萬擊還堅韌,任爾東西南北風"的恆心,爬上算法的高樓,做到"望盡天涯路"。

從一個算法萌新入門,第一步便在於打牢根基。推薦閱讀書籍:

1.《算法第 4 版》- Robert Sedgewick

適合初學者入門

2.《大話數據結構》- 程傑

3.

《算法圖解》- Aditya Bhargava

《大話數據結構》和《算法圖解》這兩本書的特點是有趣、易理解,也非常適合初學者。

4.《數據結構和算法分析- C 語言描述》- Mark Allen Weiss

需要有一定 C 語言基礎

進階:

1.《編程珠璣》- Jon Bentley

本書探討了程序設計人員面對一系列的實際問題以及解決問題的措施(解決方案的代碼以 C/C++ 語言編寫)。書中選取了許多具有典型意義的複雜編程和算法問題,並闡述和總結了許多獨特精妙的設計原則、思考和解決問題的方法以及實用的程序設計技巧。

2.《算法導論》- Cormen,T.H.

《算法導論》的特點是全面,它是一本算法的百科全書,著重在於開闊算法視野,適合有一定算法基礎後再去學習。

入門階段是看一些天賦的,花費時間因人而異,大約在 3~6 月之間,將上述提到的書籍選擇其中一本看完基本就能入門了。在這個階段中,需要了解幾類常用的算法:

1. 常用的數據結構:數組、字符串、鏈表、樹(如二叉樹)等

2. 常用的算法:分治、貪心、窮舉、動態規劃、回溯、二分算法、深度優先搜索等

可搭配力扣的題目進行練習

其中,暴力枚舉、貪心算法容易理解,可以很快上手。數論相關的算法需要用到一些數學技巧,包括位運算、冪函數、求模等等性質。二分算法和深度優先搜索算法相對有些技巧性,好在他們都有固定的模板。另外,不得不提的是,深度優先搜索算法的思想非常重要,而且深度優先搜索是動態規劃、分治和回溯的基礎,需要重點掌握。在此過程中,可以輔以力扣(LeetCode)中的簡單題目,它們往往都代表了一類經典算法,如:

70. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢?

動態規劃 算法的經典題目,通過此題目可以瞭解狀態、邊界條件、狀態轉移方程等基本概念。

112. 路徑總和

給定一個二叉樹和一個目標和,判斷該樹中是否存在根節點到葉子節點的路徑,這條路徑上所有節點值相加等於目標和。

深度優先算法 的入門題目,遞歸實現和迭代實現都不難,可以學習到深度優先算法的層層嵌套搜索、找到答案或到達邊界停止的基本解題思路。

35. 搜索插入位置

給定一個排序數組和一個目標值,在數組中找到目標值,並返回其索引。如果目標值不存在於數組中,返回它將會被按順序插入的位置。

二分算法 的典型題目,使用二分算法的解題模板可以輕鬆解決,二分算法的算法思想清晰明確,一通百通。

169. 求眾數

給定一個大小為 n 的數組,找到其中的眾數。眾數是指在數組中出現次數大於 的元素。你可以假設數組是非空的,並且給定的數組總是存在眾數。

分治算法 的簡單題目,如果我們知道數組左邊一半和右邊一半的眾數,我們就可以用線性時間知道全局的眾數是哪個。這道題妙就妙在可以有多種解題方式,讓初學者至少可以寫出暴力枚舉算法 AC 題目,然後再逐步深入,優化算法。

944. 刪列造序

給定由 N 個小寫字母字符串組成的數組 A,其中每個字符串長度相等。選取一個刪除索引序列,對於 A 中的每個字符串,刪除對應每個索引處的字符。 所餘下的字符串行從上往下讀形成列。假設,我們選擇了一組刪除索引 ,那麼在執行刪除操作之後, 中所剩餘的每一列都必須是 非降序 排列的,然後請你返回 的最小可能值。

這是一道 貪心算法 的簡單題目,貪心算法理解簡單,上手容易,適合作為初學者掌握的第一個算法。

時間充裕的同學可以按照下圖進行系統性地學習:

二、融會貫通

學習算法理論如同閱讀了一本武功秘籍,然而僅僅掌握理論是不夠的,接下來就要進入到實際練習階段。

實戰練習非常重要,不經過實戰練習,理論僅僅是紙上談兵。比如,不經過大量練習,永遠不會知道二分算法是多麼容易出現死循環。一個邊界條件控制不好,程序就會顯示無情的"Time Limit Exceeded"。在 20 分鐘的調試後,或許僅僅是將 while (left <= right) 改為了 while (left < right) 。程序員說到底也是手藝人,這一個字符的改動,正是"臺上一分鐘,臺下十年功"的體現,需要在大量的練習中才能理解兩者之間的不同作用。

再比如,動態規劃算法中,遞歸的函數就像是《盜夢空間》中的"夢中夢",一層套一層,又漸次展開,很難整體把控。在不斷的練習後,才會知道,動態規劃算法的重點是抓住動態轉移方程,只處理兩個狀態之間的過渡和邊界條件,慢慢"大事化小,小事化了"。

這一階段花費的時間將會很長很長,伴隨著不斷地摔倒、爬起,你會對每類算法逐漸融會貫通。好在這一階段是不看天賦只看勤奮的,每次從坑裡爬起,都是獻給成長的一份力量。推薦的進階書籍有《編程珠璣》,本書探討了程序設計人員面對一系列的實際問題以及解決問題的措施(解決方案的代碼以 C/C++ 語言編寫)。書中選取了許多具有典型意義的複雜編程和算法問題,並闡述和總結了許多獨特精妙的設計原則、思考和解決問題的方法以及實用的程序設計技巧。

在這個階段,可以嘗試練習力扣上的中等題目,中等題目基本上也只會使用一種算法,加上一些特殊的限制,好比讓你在學習了直拳的理論後衍生出左勾拳和右勾拳。推薦練習題目有:

1048. 最長字符串鏈

給出一個單詞列表,其中每個單詞都由小寫英文字母組成。如果我們可以在 word1 的任何地方添加一個字母使其變成 word2,那麼我們認為 word1 是 word2 的前身。例如,"abc" 是 "abac" 的前身。詞鏈是單詞 [word_1, word_2, ..., word_k] 組成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此類推。從給定單詞列表 words 中選擇單詞組成詞鏈,返回詞鏈的最長可能長度。

分析題目可知,要求出答案必須遍歷所有可能的詞鏈,動態規劃算法在其中起備忘錄的作用,用於記錄已經算過的答案,減少計算次數。

47. 全排列 II

給定一個可包含重複數字的序列,返回所有不重複的全排列。

這道題是 46. 全排列 的加強版,全排列 I 的題目是:給定一個 沒有重複 數字的序列,返回其所有可能的全排列。使用深度優先搜索算法即可解決。本題在其基礎上加強了難度,有兩種方法可解。第一種方法最簡單,直接用全排列 I 的答案去重即可,第二種方法是先將數組排序,全排列時遇到重複數字則跳過,這樣的剪枝優化可以減少遍歷次數,提高算法效率。

40. 組合總和 II

給定一個數組 candidates 和一個目標數 target ,找出 candidates 中所有可以使數字和為 target 的組合。candidates 中的每個數字在每個組合中只能使用一次。

深度優先搜索算法衍生出來的回溯算法,同樣用到 47 題的剪枝優化思想:相同數字只允許遞歸第一個。

89. 格雷編碼

格雷編碼是一個二進制數字系統,在該系統中,兩個連續的數值僅有一個位數的差異。給定一個代表編碼總位數的非負整數 n,打印其格雷編碼序列。格雷編碼序列必須以 0 開頭。

動態規劃 算法的實際應用之一。

79. 單詞搜索

給定一個二維網格和一個單詞,找出該單詞是否存在於網格中。單詞必須按照字母順序,通過相鄰的單元格內的字母構成,其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

深度優先搜索的中級應用,使用單獨數組標記已使用過的元素,這也是 DFS 中較為常見的做法,難點在於將標記數組復原的時機,需要反覆練習,熟練掌握。

當你把每一類算法的中等題目刷起來得心應手時,不妨開始嘗試困難題目的練習。困難題目總是融合兩種或兩種以上算法,或是加深難度的經典算法,如二維甚至三維動態規劃。練習困難題目好比同時用上左勾拳和掃堂腿,不僅讓思維酣暢淋漓,在每次 AC 之後還會帶來無與倫比的成就感。推薦練習題目有:

679. 24 點遊戲

你有 4 張寫有 1 到 9 數字的牌。你需要判斷是否能通過 ,,,,, 的運算得到 24。

只有 4 張牌,且只能執行 4 種操作。即使所有運算符都不進行交換,最多也只有 12 * 6 * 2 * 4 * 4 * 4 = 9216 種可能性,這使得我們可以嘗試所有這些可能,如果用深度優先搜索算法則需要費一番功夫。

124. 二叉樹中的最大路徑和

給定一個非空二叉樹,返回其最大路徑和。本題中,路徑被定義為一條從樹中任意節點出發,達到任意節點的序列。該路徑至少包含一個節點,且不一定經過根節點。

首先,考慮實現一個簡化的函數:計算每個節點及其子樹對路徑和的最大貢獻。再考慮第二點:最大路徑不一定包括根節點。這意味著我們在每一步都檢查哪種選擇更好:是繼續當前路徑或者以當前節點作為最高節點計算新的路徑。

410. 分割數組的最大值

給定一個非負整數數組和一個整數 m,你需要將這個數組分成 m 個非空的連續子數組。設計一個算法使得這 m 個子數組各自和的最大值最小。

二分算法和貪心算法的綜合練習,仔細分析可知其單調關係:數組和的最大值越小,分組數越大。並且數組和的範圍是可以確定的。根據此特性,可以將題目轉換為:當子數組的和最大為 maxSum 時,至少需要分多少組,能否在最多 m 組的限制範圍內完成分割。在每次分割時,採用貪心策略,儘可能多的放置元素,直到一組放不下,再另起一組。如果滿足分割條件,記錄當前值,利用二分法,縮小子數組總和。否則擴大子數組總和,直到找到最佳答案。

三、推陳出新

事實上,大量程序員停留在第二重境界就無法再進一步。當提到某一類算法時,你可以說:"我知道"、"我會用"、"踩過坑",但能說出"我完全理解其思想"、甚至"我能想辦法改進"的人卻很少很少。這一步彷彿武學中的攻守之道,當你掌握到這一層,便可不再拘泥於一刀一劍、一招一式,如金書中所說:飛花摘葉皆可傷人、草木竹石均可為劍。

開創算法的過程是艱難又孤獨的。每一個經典算法的誕生都伴隨著"一將功成萬骨枯"。比如現在我們在很多語言中都可以直接調用實現快速排序,而在快速排序算法出現之前,曾有一段時間僅有冒泡、選擇、插入三種排序算法。直到1959年,希爾提出"希爾排序"算法,或許現在知道此算法的人已經很少了。但它是首個突破了複雜度的排序算法,它的基本算法思想如下:

選擇一個增量序列t1,t2,…,tk,其中 ti > tj, tk = 1; 按增量序列個數k,對序列進行k 趟排序; 每趟排序,根據對應的增量ti,將待排序列分割成若干長度為 m 的子序列,分別對各子表進行直接插入排序。僅增量因子為1 時,整個序列作為一個表來處理,表長度即為整個序列的長度。

動圖演示如下:

希爾排序算法較為晦澀難懂,而且並不是最優的排序算法,現在已經被後來的快速排序算法給淘汰了。然而不可否認希爾對排序算法的演進具有開創性貢獻,在攀越算法高峰的路上,每一步都走得戰戰兢兢,我們只有銘記這些偉大的引路人,以此激勵自己不斷前行。

算法世界不盡完美。不僅有經典算法在前奠基,後起之秀遺傳算法、深度學習算法也熠熠生輝。算法世界還有許多"所羅門王的寶藏",一直靜靜地守候在"燈火闌珊處",等待著人們去發掘。

四、學習方法

我給大家整理了一個學習計劃,可以保存下圖進行學習:

現在網上有很多資源、博客、論壇可供我們更方便地學習知識片段。然而這種類似兵來將擋、水來土掩般的學習方法雖然有用,卻並不特別的好。這裡推薦大家在網上尋找一些系統的學習教程,以幫助自己由淺入深,一路成長。

五、真題演練

理論學習了還是要多刷題,實際操作才能真正運用。(引用自網絡)


分享到:


相關文章: