漫畫：嘔心泣血演算法指導篇（真正的乾貨，怒懟那些說演算法沒用的人）

• 2020 年 3 月 30 日
• 筆記

• 演算法對個人的意義
• 解決問題的策略
• 演算法問題匯總

01 PART

演算法對個人的意義

在實際項目中，演算法的使用場景有很多，如「Java8中Hashmap使用紅黑樹來實現」、「Redis底層使用LRU來進做淘汰策略」、「大數據領域很多問題都基於TopK」、「JS原型鏈里使了類似鏈表的成環檢測」、「特別複雜的業務邏輯經常涉及到DAG」、「MySql為什麼索引要用B+樹」、「Oracle里的開窗函數如何實現」 等等等等，這些今天我們統統不談。而我，更多的是想和大家聊一聊，演算法對個人有什麼意義？

市面上大部分的演算法書籍，第一章介紹演算法，都會給大家列一列類似上面的那些話，或者就是使用棧或隊列來做一個引子，告訴大家演算法很重要，你得需要去學，吧啦吧啦....但是不知道大家有沒有想過這樣一個問題，演算法對於個人而言到底有什麼意義呢？如果這個問題大家陌生，那你一定會聽到有寫了幾年業務邏輯的老程式設計師，說過「我這些年從來沒有用過演算法，除了出去面試的時候」之類的話。其實，我這裡真想說一句髒話，這些思想真的是TMD害人不淺啊。甚至我懷疑大多數說這句話本身的人，有兩種：一種就是嚴重缺乏自信心，覺得自己一輩子都沒辦法學好演算法了，所以就這樣吧。第二種就是故意誤人子弟，驅動來源於自己不會，方式採用侃大山，反正忽悠一個是一個，再來身邊也沒有其他這方面厲害的朋友，說完之後自己都沒意識到哪裡有問題，卻對別人帶去很不好的影響。所以如果你今天看到我的這篇文章，我希望你能記住一世，這輩子都不要說出這種類似的話來，保持對這個學科基本的尊重，哪怕多一點點匠心精神。演算法對個人的意義如下：

• 演算法題目的程式規模大多都是比較小的，也就意味著切入點很小。使得每一個做題人，可以最大化的投入時間研究問題的本身。而在工作中，稍大一點的項目，基本上是沒辦法隨意改變程式碼結構的，甚至還會為了整體性能犧牲程式的簡潔與優雅。所以演算法題是可以讓你通過練習編寫出好程式碼的最好的方式，沒有之一。
• 演算法題目中基本不會有圖形化介面，只利用文本進行輸入和輸出。你可以相當專註的去解決問題。而在工作中，你能獲得專註去研究一個問題的機會，幾乎很難。想一想，假如你用JAVA寫一個後台功能，其核心程式碼不到10行邏輯，但是MVC得佔據你三分之一工作量，定義介面佔據你三分之一工作量，公司假如沒前端，再佔據你三分之一工作量。整個這個過程，我有一個Amazon的朋友形容的很貼切，「掏糞」。
• 預測能力的構建，在大多數演算法練習平台中，因為會將運算時間和記憶體使用狀況等資訊實時提供給做題人，所以做題人甚至可以一邊修改程式碼，一邊觀察修改對程式產生的影響。這個是不得了的，在工作中，絕對不可能有這樣的機會。而在這個過程中，做題人可以提高對邏輯結構複雜程式進行性能預測的能力，該能力將伴隨其一身。
• 提升coding能力的最好方式。假如我們打王者榮耀，你要上王者，不開排位，一直打電腦，能上的去嗎？在工作中，你來回接觸的就那麼幾個人，有幾個能寫出特別優秀的程式碼，見到了，那說明老天眷顧你，大部分人都見不到。但是在演算法平台的練習中，基本上我們每一個問題，我們都能看到全世界最優秀的人提交的程式碼。沒有對比，雖然不成傷害，卻更難成為進步！只有我們去閱讀別人優秀的邏輯，讀懂別人思考的過程，與全世界頂尖的程式設計師編寫程式碼的能力進行比較，才可以成為真正的大牛。
• 演算法題讓你難受。用腳指頭想一個問題，在各行各業中，想成為其行業的佼佼者，是不是一定有一個難受的過程。假如天天寫CRUD，並且還得意洋洋，我用一套Generator生成只需要5分鐘，其他時間就可以打打爐石，勾搭勾搭妹子。不經歷一個難受的過程，如何可以進步？就連郭德綱出名之前，也在玻璃窗里被關過兩天兩夜。羅馬不是一天建成的，但是如果不修，那就永遠建不成。難受就是真理，說明你正在進步。
• 單測都是「騙人的」。請大家不要高估工作中QA的能力（當然，也有牛逼的QA，我見過...），大部分的公司里，QA來做單測時，基本上是重新走了一遍開發者的邏輯。更有甚者，開發直接說出「我寫完都已經測完了，要QA有什麼用處」，其實這並不是一個段子，因為大部分QA是做不到完美的cover業務邏輯的，換句話說，也就不可能構建出完美的測試用例測出你程式碼的問題。但是演算法不是，大部分的演算法平台，都提供了實時回饋的機制，如果自己編寫的程式碼可以得到快速，客觀的意見回饋，這絕對是有如神助。就好像是你打王者，旁邊有個小精靈，總是會在合適的時機告訴你，「去下路，中路沒人」，「小心草叢」。那如果不被帶飛，你信嗎？

總之，正是因為演算法題目中只保留了必備的要素，捨棄了其他無關緊要的部分，所以可以對每一位做題人都構建一個學習解決問題的最佳環境，而在這個環境中的成長與提高，將對一個軟體工程師的生涯產生深遠影響，乃至一世。所以，請大家能有一顆匠心，你可以選擇不去了解學習掌握演算法，但是請不要耽誤他人進步。山高水長，江湖路遠，珍重萬千，有緣再見！

02 PART

解決問題的策略

解決簡單的問題時，直接利用已知的技術便可輕鬆解決問題。但是如果遇到難題，恐怕就需要用各種手段。管他是花貓野貓，抓住耗子都是好貓。在解決問題的策略構建中，我們首先要對問題和答案結構有一個直觀的感受，或者說猜測。如果可以把控住當前演算法的問題，具備一個什麼樣的形態，然後就可以把毫無頭緒的事情，變得有跡可循。在這樣一個過程中，一點點的積累經驗，最終就可以提升自己。

上面說的內容，玄而又玄，那到底如何來構建策略。假如我們遇到一個問題，讓我們找一個國家鐵路網中，兩個城市的最短路徑。這種問題，大家肯定首先想到的就是使用迪傑斯特拉演算法。但是如果問題變成「換乘火車次數少於N次，尋找最短路徑」，這種問題將不能直接套用最短路徑的演算法。有時候只是改變題中條件，就可以讓整個題目完全走向另一個邏輯，這就需要大家對原演算法的原理和執行過程特別了解，並且熟讀題意。所以這裡我們抽象出兩個步驟：

• 讀題
• 重構

讀題的目的，就是閱讀並理解問題。不管是是不是演算法老手，在這上面栽跟頭的絕對不是一個兩個，審題不清是所有人的共性（絕不是你的個人問題），人的天性就期望可以快速得到回饋，這是身體慾望導致的，和你看到漂亮的妹子下半身豎立本質沒有什麼區別。所以這就引出我們的解決方法 - 重構。

什麼是重構，重構其實就是一個抽象化的過程。借用我們已經掌握的數學/電腦知識，將其表達成現實世界概念。大部分的現實世界概念都是比較複雜的，我們對其抽繭剝絲，保留本質，表述成易於理解的形式。而對其重構的過程，就可以決定其程式設計的方向。舉一個最簡單的例子，比如我們要用程式碼實現一個整數平方根的開方，可以選用牛頓法或者二分法，那這兩種方法是如何被想到的。假如我們把問題重構成圖形的表達方式，就比較容易會推出牛頓法。假如我們把問題重構成已有的知識概念，自然就可以想到二分法。而如果我們把問題抽象成公式，甚至可以通過數學法來進行解題。劃重點，不同的重構方式，決定最終程式的走向。

在重構的基礎上，其實我們就可以來進行解題了。但是這裡我還要對其加一個步驟，化簡。什麼又是化簡，如何化簡？假如我們有一個題，我們有一個二維網格，裡邊有N個點，兩點的距離是X坐標和Y坐標的的和。比如坐標(5,1)和(4,7)的點間距就是1+6=7。我們要找到給出的N個點距離之和最小的新點的坐標。

題目因為本身是二維的，我們寫程式碼其實不是很好寫。所以我們可以將其化簡為一維。我們把每一個點的左邊，通過映射的方式，分別映射到 x軸 和 y軸。然後我們把問題轉化成在直線上尋找到給出點的距離之和最小的點。這就是化簡。萬物之始，大道至簡，至拙至美。生活中咱們也說透過現象看本質，放在演算法里你就不會了？

讀題-重構-化簡，下來自然就是解題了。那如何解題？這個範疇雖然很大，但也不是無跡可尋，下面兩點：

• 基本數據結構和演算法的掌握（略）
• 常見演算法問題的匯總

基本數據結構和演算法的掌握，這個自不必說，是人都知道，那麼常見演算法問題的匯總又是什麼，我們看下一節。

03 PART

演算法問題匯總

寫演算法最怕什麼？當然是出錯。與其重複相同的錯誤，不如從錯誤中吸取教訓。與其從自己的錯誤中吸取教訓，不如從別人的錯誤中學習經驗。總結常見的演算法問題，我總不能和你去說我們需要掌握數組、鏈表、二叉樹、Map等這些數據結構。我認為的總結，就是錯誤的總結。所以為了快速拔高大家的水準，我準備了以下這些錯誤，請一定耐心看完，反覆閱讀。

• 遞歸，防止死循環和記憶體泄露。由於遞歸需要堆棧，所以記憶體消耗要比非遞歸程式碼要大很多。而且，如果遞歸深度太大，可能系統撐不住。記憶體會存在突然飆升的情況。如果是數據錯誤導致無限循環，那問題就大了。所以這方面問題在開發的時候需要注意。
• 訪問數組越界，絕大多數的數組越界，根本原因在於對定義混淆。比如定義的時候想的是「以0起始」，但是寫的時候寫成了「以1起始」。究其根本，數組越界的問題，其實是對區間把控的問題。
• 區間表意不明。大部分的語言中，數組都以0為起始元素，但是人的思維習慣於以1為起始。那為什麼數組要以0為起始元素，歷史原因有很多，咱不說。對咱們有用的，3個。第一，因為我們選擇左閉右開區間，比如 [0,n)，我們可以很容易通過 n-0 得到數組中元素個數。這點大家要形成條件發射，看到數組，明確其個數。第二，閉區間很難去表示一個空數組，不信你試試，非常難受。第三，左閉右開的區間，迭代器只需要最少的操作符。可以讓程式碼寫起來非常的舒服，STL的演算法和容器中基本都是如此。
• 差一問題（柵欄錯誤）。建造一條直柵欄（即不圍圈），長30米、每條柵欄柱間相隔3米，需要多少條柵欄柱? 求數組 A[i]到 A[j] 的平均值，A[i] 到 A[j] 的和應該除以多少，是 j-i+1，還是 j-i？二分法中的 while 條件，到底是用 <= 還是 < ？這些都是差一問題，這類問題如何解決。利用最小的的輸入值測試程式碼的執行過程，長期反覆，達到條件反射。這個過程一定是在大量的題目練習中掌握的，如果你到目前還在糾結這個問題，請先扣心自問，是否刷過至少200道演算法題。如果沒有，請不要糾結，干就對了。如果有，來找我。
• 記憶體溢出問題。分為兩種，一種是因為運算超出變數取值範圍發生的記憶體溢出，比如二分法中的mid，就要使用 left+(right-left)>>1。另一種就是因為程式碼不嚴謹，比如遞歸沒有退出條件，while死循環，等等導致記憶體溢出。
• 初學者定義問題。比如統計26個字母出現的次數，初學者會用hashmap，其實這種已知值範圍的，定義成數組就可以了。其他類似數字0-9，每個月的天數，都是一樣的
• 寫一半忘記題意。這個根本原因還是因為思維脈絡不清晰導致的，有時候初學者還會遇到一個問題。定義一個函數，比如叫做 juge() 返回 bool 值，本來應該是判斷某條件成立時返回true，但是用的時候卻以為，在條件不成立的時候返回true，最終導致結果錯誤。
• 變數名錯誤。不管是和方法參數中的變數名稱衝突，還是因為本身表意不明，最終出現賦值錯誤，或者編譯不通過。
• 運算優先順序錯誤。比如位運算，各個語言中的優先順序定義是略有不同的。有時候需要加括弧，有時候不需要加。
• 特殊值的處理。一些找規律的題目，往往在等於0，等於1的時候，規律和其他的數不同，所以這種題目，需要對這種特殊值進行特殊處理。

以上就是我挑選過的一些具有代表性的錯誤示例（後續還會補充），同時，演算法指導篇我打算出一個系列，包括演算法中常用技巧，常見錯誤，題目常見誤導 等等，都是我的珍藏。今天的文章嘔心泣血，希望大家可以幫我轉發，我想如果你身邊有學習電腦的朋友看到，他一定會感謝你。支援我的朋友們，還沒有關注的，快點來個關注。最後，山高水長，江湖路遠，珍重萬千，下期再見！