算法問題匯總

講一講到底如何“解決問題”，本文非常非常非常重要，是我很長一段時間的心血與積累，大家一定要耐心看完，共包含3節(jié)：

算法對個人的意義

解決問題的策略

算法問題匯總

01 PART 算法對個人的意義

在實(shí)際項(xiàng)目中，算法的使用場景有很多，如“Java8中Hashmap使用紅黑樹來實(shí)現(xiàn)”、“Redis底層使用LRU來進(jìn)做淘汰策略”、“大數(shù)據(jù)領(lǐng)域很多問題都基于TopK”、“JS原型鏈里使了類似鏈表的成環(huán)檢測”、“特別復(fù)雜的業(yè)務(wù)邏輯經(jīng)常涉及到DAG”、“MySql為什么索引要用B+樹”、“Oracle里的開窗函數(shù)如何實(shí)現(xiàn)” 等等等等，這些今天我們統(tǒng)統(tǒng)不談。而我，更多的是想和大家聊一聊，算法對個人有什么意義？

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

算法題目的程序規(guī)模大多都是比較小的，也就意味著切入點(diǎn)很小。使得每一個做題人，可以最大化的投入時間研究問題的本身。而在工作中，稍大一點(diǎn)的項(xiàng)目，基本上是沒辦法隨意改變代碼結(jié)構(gòu)的，甚至還會為了整體性能犧牲程序的簡潔與優(yōu)雅。所以算法題是可以讓你通過練習(xí)編寫出好代碼的最好的方式，沒有之一。

算法題目中基本不會有圖形化界面，只利用文本進(jìn)行輸入和輸出。你可以相當(dāng)專注的去解決問題。而在工作中，你能獲得專注去研究一個問題的機(jī)會，幾乎很難。想一想，假如你用JAVA寫一個后臺功能，其核心代碼不到10行邏輯，但是MVC得占據(jù)你三分之一工作量，定義接口占據(jù)你三分之一工作量，公司假如沒前端，再占據(jù)你三分之一工作量。整個這個過程，我有一個Amazon的朋友形容的很貼切，“掏糞”。

預(yù)測能力的構(gòu)建，在大多數(shù)算法練習(xí)平臺中，因?yàn)闀⑦\(yùn)算時間和內(nèi)存使用狀況等信息實(shí)時提供給做題人，所以做題人甚至可以一邊修改代碼，一邊觀察修改對程序產(chǎn)生的影響。這個是不得了的，在工作中，絕對不可能有這樣的機(jī)會。而在這個過程中，做題人可以提高對邏輯結(jié)構(gòu)復(fù)雜程序進(jìn)行性能預(yù)測的能力，該能力將伴隨其一身。

提升coding能力的最好方式。假如我們打王者榮耀，你要上王者，不開排位，一直打電腦，能上的去嗎？在工作中，你來回接觸的就那么幾個人，有幾個能寫出特別優(yōu)秀的代碼，見到了，那說明老天眷顧你，大部分人都見不到。但是在算法平臺的練習(xí)中，基本上我們每一個問題，我們都能看到全世界最優(yōu)秀的人提交的代碼。沒有對比，雖然不成傷害，卻更難成為進(jìn)步！只有我們?nèi)ラ喿x別人優(yōu)秀的邏輯，讀懂別人思考的過程，與全世界頂尖的程序員編寫代碼的能力進(jìn)行比較，才可以成為真正的大牛。

算法題讓你難受。用腳指頭想一個問題，在各行各業(yè)中，想成為其行業(yè)的佼佼者，是不是一定有一個難受的過程。假如天天寫CRUD，并且還得意洋洋，我用一套Generator生成只需要5分鐘，其他時間就可以打打爐石，勾搭勾搭妹子。不經(jīng)歷一個難受的過程，如何可以進(jìn)步？就連郭德綱出名之前，也在玻璃窗里被關(guān)過兩天兩夜。羅馬不是一天建成的，但是如果不修，那就永遠(yuǎn)建不成。難受就是真理，說明你正在進(jìn)步。

單測都是“騙人的”。請大家不要高估工作中QA的能力（當(dāng)然，也有牛逼的QA，我見過...），大部分的公司里，QA來做單測時，基本上是重新走了一遍開發(fā)者的邏輯。更有甚者，開發(fā)直接說出“我寫完都已經(jīng)測完了，要QA有什么用處”，其實(shí)這并不是一個段子，因?yàn)榇蟛糠諵A是做不到完美的cover業(yè)務(wù)邏輯的，換句話說，也就不可能構(gòu)建出完美的測試用例測出你代碼的問題。但是算法不是，大部分的算法平臺，都提供了實(shí)時反饋的機(jī)制，如果自己編寫的代碼可以得到快速，客觀的意見反饋，這絕對是有如神助。就好像是你打王者，旁邊有個小精靈，總是會在合適的時機(jī)告訴你，“去下路，中路沒人”，“小心草叢”。那如果不被帶飛，你信嗎？

總之，正是因?yàn)樗惴}目中只保留了必備的要素，舍棄了其他無關(guān)緊要的部分，所以可以對每一位做題人都構(gòu)建一個學(xué)習(xí)解決問題的最佳環(huán)境，而在這個環(huán)境中的成長與提高，將對一個軟件工程師的生涯產(chǎn)生深遠(yuǎn)影響，乃至一世。所以，請大家能有一顆匠心，你可以選擇不去了解學(xué)習(xí)掌握算法，但是請不要耽誤他人進(jìn)步。山高水長，江湖路遠(yuǎn)，珍重萬千，有緣再見！

02 PART 解決問題的策略

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

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

讀題

重構(gòu)

讀題的目的，就是閱讀并理解問題。不管是是不是算法老手，在這上面栽跟頭的絕對不是一個兩個，審題不清是所有人的共性（絕不是你的個人問題），人的天性就期望可以快速得到反饋，這是身體欲望導(dǎo)致的，和你看到漂亮的妹子下半身豎立本質(zhì)沒有什么區(qū)別。所以這就引出我們的解決方法 - 重構(gòu)。

什么是重構(gòu)，重構(gòu)其實(shí)就是一個抽象化的過程。借用我們已經(jīng)掌握的數(shù)學(xué)/計(jì)算機(jī)知識，將其表達(dá)成現(xiàn)實(shí)世界概念。大部分的現(xiàn)實(shí)世界概念都是比較復(fù)雜的，我們對其抽繭剝絲，保留本質(zhì)，表述成易于理解的形式。而對其重構(gòu)的過程，就可以決定其程序設(shè)計(jì)的方向。舉一個最簡單的例子，比如我們要用代碼實(shí)現(xiàn)一個整數(shù)平方根的開方，可以選用牛頓法或者二分法，那這兩種方法是如何被想到的。假如我們把問題重構(gòu)成圖形的表達(dá)方式，就比較容易會推出牛頓法。假如我們把問題重構(gòu)成已有的知識概念，自然就可以想到二分法。而如果我們把問題抽象成公式，甚至可以通過數(shù)學(xué)法來進(jìn)行解題。劃重點(diǎn)，不同的重構(gòu)方式，決定最終程序的走向。

在重構(gòu)的基礎(chǔ)上，其實(shí)我們就可以來進(jìn)行解題了。但是這里我還要對其加一個步驟，化簡。什么又是化簡，如何化簡？假如我們有一個題，我們有一個二維網(wǎng)格，里邊有N個點(diǎn)，兩點(diǎn)的距離是X坐標(biāo)和Y坐標(biāo)的的和。比如坐標(biāo)(5,1)和(4,7)的點(diǎn)間距就是1+6=7。我們要找到給出的N個點(diǎn)距離之和最小的新點(diǎn)的坐標(biāo)。

題目因?yàn)楸旧硎嵌S的，我們寫代碼其實(shí)不是很好寫。所以我們可以將其化簡為一維。我們把每一個點(diǎn)的左邊，通過映射的方式，分別映射到 x軸 和 y軸。然后我們把問題轉(zhuǎn)化成在直線上尋找到給出點(diǎn)的距離之和最小的點(diǎn)。這就是化簡。萬物之始，大道至簡，至拙至美。生活中咱們也說透過現(xiàn)象看本質(zhì)，放在算法里你就不會了？

讀題-重構(gòu)-化簡，下來自然就是解題了。那如何解題？這個范疇雖然很大，但也不是無跡可尋，下面兩點(diǎn)：

基本數(shù)據(jù)結(jié)構(gòu)和算法的掌握（略）

常見算法問題的匯總

基本數(shù)據(jù)結(jié)構(gòu)和算法的掌握，這個自不必說，是人都知道，那么常見算法問題的匯總又是什么，我們看下一節(jié)。

03 PART 算法問題匯總

寫算法最怕什么？當(dāng)然是出錯。與其重復(fù)相同的錯誤，不如從錯誤中吸取教訓(xùn)。與其從自己的錯誤中吸取教訓(xùn)，不如從別人的錯誤中學(xué)習(xí)經(jīng)驗(yàn)?？偨Y(jié)常見的算法問題，我總不能和你去說我們需要掌握數(shù)組、鏈表、二叉樹、Map等這些數(shù)據(jù)結(jié)構(gòu)。我認(rèn)為的總結(jié)，就是錯誤的總結(jié)。所以為了快速拔高大家的水準(zhǔn)，我準(zhǔn)備了以下這些錯誤，請一定耐心看完，反復(fù)閱讀。

遞歸，防止死循環(huán)和內(nèi)存泄露。由于遞歸需要堆棧，所以內(nèi)存消耗要比非遞歸代碼要大很多。而且，如果遞歸深度太大，可能系統(tǒng)撐不住。內(nèi)存會存在突然飆升的情況。如果是數(shù)據(jù)錯誤導(dǎo)致無限循環(huán)，那問題就大了。所以這方面問題在開發(fā)的時候需要注意。

訪問數(shù)組越界，絕大多數(shù)的數(shù)組越界，根本原因在于對定義混淆。比如定義的時候想的是“以0起始”，但是寫的時候?qū)懗闪恕耙?起始”。究其根本，數(shù)組越界的問題，其實(shí)是對區(qū)間把控的問題。

區(qū)間表意不明。大部分的語言中，數(shù)組都以0為起始元素，但是人的思維習(xí)慣于以1為起始。那為什么數(shù)組要以0為起始元素，歷史原因有很多，咱不說。對咱們有用的，3個。第一，因?yàn)槲覀冞x擇左閉右開區(qū)間，比如 [0,n)，我們可以很容易通過 n-0 得到數(shù)組中元素個數(shù)。這點(diǎn)大家要形成條件發(fā)射，看到數(shù)組，明確其個數(shù)。第二，閉區(qū)間很難去表示一個空數(shù)組，不信你試試，非常難受。第三，左閉右開的區(qū)間，迭代器只需要最少的操作符?？梢宰尨a寫起來非常的舒服，STL的算法和容器中基本都是如此。

差一問題（柵欄錯誤）。建造一條直柵欄（即不圍圈），長30米、每條柵欄柱間相隔3米，需要多少條柵欄柱? 求數(shù)組 A[i]到 A[j] 的平均值，A[i] 到 A[j] 的和應(yīng)該除以多少，是 j-i+1，還是 j-i？二分法中的 while 條件，到底是用 <= 還是 < ？這些都是差一問題，這類問題如何解決。利用最小的的輸入值測試代碼的執(zhí)行過程，長期反復(fù)，達(dá)到條件反射。這個過程一定是在大量的題目練習(xí)中掌握的，如果你到目前還在糾結(jié)這個問題，請先扣心自問，是否刷過至少200道算法題。如果沒有，請不要糾結(jié)，干就對了。如果有，來找我。

內(nèi)存溢出問題。分為兩種，一種是因?yàn)檫\(yùn)算超出變量取值范圍發(fā)生的內(nèi)存溢出，比如二分法中的mid，就要使用 left+(right-left)>>1。另一種就是因?yàn)榇a不嚴(yán)謹(jǐn)，比如遞歸沒有退出條件，while死循環(huán)，等等導(dǎo)致內(nèi)存溢出。

初學(xué)者定義問題。比如統(tǒng)計(jì)26個字母出現(xiàn)的次數(shù)，初學(xué)者會用hashmap，其實(shí)這種已知值范圍的，定義成數(shù)組就可以了。其他類似數(shù)字0-9，每個月的天數(shù)，都是一樣的

寫一半忘記題意。這個根本原因還是因?yàn)樗季S脈絡(luò)不清晰導(dǎo)致的，有時候初學(xué)者還會遇到一個問題。定義一個函數(shù)，比如叫做 juge() 返回 bool 值，本來應(yīng)該是判斷某條件成立時返回true，但是用的時候卻以為，在條件不成立的時候返回true，最終導(dǎo)致結(jié)果錯誤。

變量名錯誤。不管是和方法參數(shù)中的變量名稱沖突，還是因?yàn)楸旧肀硪獠幻鳎罱K出現(xiàn)賦值錯誤，或者編譯不通過。

運(yùn)算優(yōu)先級錯誤。比如位運(yùn)算，各個語言中的優(yōu)先級定義是略有不同的。有時候需要加括號，有時候不需要加。

特殊值的處理。一些找規(guī)律的題目，往往在等于0，等于1的時候，規(guī)律和其他的數(shù)不同，所以這種題目，需要對這種特殊值進(jìn)行特殊處理。

以上就是我挑選過的一些具有代表性的錯誤示例（后續(xù)還會補(bǔ)充），同時，算法指導(dǎo)篇我打算出一個系列，包括算法中常用技巧，常見錯誤，題目常見誤導(dǎo) 等等，都是我的珍藏。今天的文章嘔心泣血，希望大家可以幫我轉(zhuǎn)發(fā)，我想如果你身邊有學(xué)習(xí)計(jì)算機(jī)的朋友看到，他一定會感謝你。支持我的朋友們，還沒有關(guān)注的，快點(diǎn)來個關(guān)注。最后，山高水長，江湖路遠(yuǎn)，珍重萬千，下期再見！