面試中純粹考演算法的問題一般是讓很多程式員朋友痛恨的，這里分享下我對于解答演算法題的一些思路和技巧，
一般關于演算法的文章，都是從經典演算法講起，一種一種演算法介紹，見得演算法多了，自然就有了感悟，但如此學習花費的時間和精力卻是過于巨大，也不適合在博客里面交流，這一篇文，卻是專門講快捷思路的，很多人面對演算法題的時候幾乎是腦子里一片空白，這一篇文章講的就是從題目下手，把毫無思路的題目打開一個缺口的幾種常見技巧，
另外本人整理收藏了20年多家公司面試知識點整理 ，以及各種Java核心知識點免費分享給大家，我認為對面試來說是非常有用的，想要資料的話請加群1149778920 暗號： qf 來自行領取，**
（一）由簡至繁
事實上，很多問題確實是很難在第一時間內得到正確的思路的，這時候可以嘗試一種由簡至繁的思路，首先把問題規模縮小到非常容易解答的地步，
[題目]有足夠量的2分、5分、1分硬幣，請問湊齊1元錢有多少種方法？
此題乍看上去，只會覺得完全無法入手，但是按照由簡至繁的思路，我們可以先考慮極端簡單的情況，假如把問題規模縮小成:有足夠量的1分硬幣，請問湊齊1分錢有多少種方法？毫無疑問，答案是1，
得到這一答案之后，我們可以略微擴大問題的規模： 有足夠量的1分硬幣，湊齊2分錢有多少種方法？湊齊n分錢有多少種方法？答案仍然是1
接下來，我們可以從另一個角度來擴大問題，有足夠量的1分硬幣和2分硬幣，湊齊n分錢有多少種方法？這時我們手里已經有了有足夠量的1分硬幣，湊齊任意多錢都只有1種方法，那么只用1分錢湊齊n-2分錢，有1種方法，只用1分錢湊齊n-4分錢，有1種方法，只用1分錢湊齊n-6分錢，有1種方法…
而湊齊這些n-2、n-4、n-6這些錢數，各自補上2分錢，會產生一種新的湊齊n分錢的方法，這些方法的總數+1，就是用1分硬幣和2分硬幣，湊齊n分錢的方法數了，
在面試時，立刻采用這種思路是一種非常有益的嘗試，解決小規模問題可以讓你更加熟悉問題，并且慢慢發現問題的特性，最重要的是給你的面試官正面的信號——立即動手分析問題比皺眉冥思苦想看起來好得多，
對于此題而言，我們可以很快發現問題的規模有兩個維度：用a1-ak種硬幣和湊齊n分錢，所以我們可以記做P(k,n)，當我們發現遞回公式 P(k,n) = P(k-1,n - ak) + P(k-1,n - 2ak) + P(k-1,n - 3ak) … … 時，這個問題已經是迎刃而解了
通常由簡至繁的思路，用來解決動態規劃問題是非常有效的，當積累了一定量簡單問題的解的時候，往往通向更高一層問題的答案已經擺在眼前了，
（二）一分為二
另一種思路，就是把問題一刀斬下，把問題分為兩半，變成兩個與原來問題同構的問題，能把問題一分為2，就能再一分為4，就能再一分為8，直到分成我們容易解決的問題，當嘗試這種思路時，其實只需要考慮兩個問題：1.一分為二以后，問題是否被簡化了？ 2.根據一分為二的兩個問題的解，能否方便地得出整個問題的解？
[題目]將一個陣列排序，
這個經典演算法肯定所有人都熟悉的不能再熟悉了，不過若是從頭開始思考這個問題，倒也不是所有人都能想出幾種經典的排序演算法之一的，這里僅僅是用來做例子說明一分為二的思路的應用，
最簡單的一分為二，就是將陣列分成兩半，分別排序，對于兩個有序陣列，我們有辦法將它合并成一個有序陣列，所以這個一分為二的思路是可行的，同樣對于已經分成兩半的陣列，我們還可以將這個陣列分作兩半，直到我們分好的陣列僅有1個元素，1個元素的陣列天然就是有序的，不難看出，按這種思路我們得出的是經典陣列排序演算法中的“歸并排序”，
還有另一種一分為二的思路，考慮到自然將陣列分成兩半合并起來比較復雜，我們可以考慮將陣列按照大于和小于某個元素分成兩半，這樣只要分別解決就可以直接連接成一個有序陣列了，同樣這個問題也是能夠再次一分為二，按照這個思路，則可以得出經典陣列排序演算法中的“快速排序”，
（三）化虛為實
這種思路針對的是浮點數有關的特殊問題，因為無論是窮舉還是二分，對于浮點數相關的計算問題（尤其是計算幾何）都難以啟效，所以化虛為實，指的是把有點"虛"的浮點數，用整數來替代，具體做法是，把題目中給出的一些浮點數（不限于浮點數，我們不關心其具體大小的整數也可以）排序，然后用浮點數的序號代替本身來思考問題，等到具體計算時再替換回來，
[題目]已知n個邊水平豎直的矩形（用四元組[x1,y1,x2,y2]表示），求它們的總共覆寫面積，
因為坐標可能出現浮點數，所以此題看起來十分繁復（可以實踐上面由簡至繁和一分為二的思路都基本無效），略一思考，矩形的覆寫關系其實只跟矩形坐標的大小有關，所以我們嘗試思考將矩形的所有x值排序，然后用序號代替具體豎直，y值亦然，于是我們得到所有矩形其實處于一個2nx2n的區塊當中，這樣我們用最簡單的窮舉辦法，可以計算出每一個1x1的格子是否被覆寫住了，至此，只要我們計算面積的時候，把格子的真實長寬換算回來，就已經得到題目的答案了，
文末
本文以上三種思路，是我平時遇到演算法問題的快速思考方向，并非萬靈藥方，若是不能生效，就要靜下心來慢慢思考觀察了，考慮到面試的時候基本不會遇到高難度演算法題，這幾種技巧的命中率應該不會太低，共享給大家，希望有所幫助
近段時間正值找作業的最佳時間，想要獲取更多的多執行緒或與微服務相關問題還有2020最近各大廠商的面試真題的可以加群1149778920 來和我們一起分享和交流，暗號：qf
以下是部分資料截圖（所有資料均已整合成檔案，pdf壓縮打包處理），
**
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/167079.html
標籤：其他
上一篇：LintCode 278. 繪制填充 JavaScript演算法
下一篇：flash