面試中純粹考算法的問(wèn)題一般是讓很多程序員朋友痛恨的，這里分享下我對(duì)于解答算法題的一些思路和技巧。

一般關(guān)于算法的文章，都是從經(jīng)典算法講起，一種一種算法介紹，見(jiàn)得算法多了，自然就有了感悟，但如此學(xué)習(xí)花費(fèi)的時(shí)間和精力卻是過(guò)于巨大，也不適合在博客里面交流。這一篇文，卻是專(zhuān)門(mén)講快捷思路的，很多人面對(duì)算法題的時(shí)候幾乎是腦子里一片空白，這一篇文章講的就是從題目下手，把毫無(wú)思路的題目打開(kāi)一個(gè)缺口的幾種常見(jiàn)技巧。

（一）由簡(jiǎn)至繁

事實(shí)上，很多問(wèn)題確實(shí)是很難在第一時(shí)間內(nèi)得到正確的思路的，這時(shí)候可以嘗試一種由簡(jiǎn)至繁的思路。首先把問(wèn)題規(guī)?？s小到非常容易解答的地步。

[題目]有足夠量的2分、5分、1分硬幣，請(qǐng)問(wèn)湊齊1元錢(qián)有多少種方法？

此題乍看上去，只會(huì)覺(jué)得完全無(wú)法入手，但是按照由簡(jiǎn)至繁的思路，我們可以先考慮極端簡(jiǎn)單的情況，假如把問(wèn)題規(guī)模縮小成:有足夠量的1分硬幣，請(qǐng)問(wèn)湊齊1分錢(qián)有多少種方法？毫無(wú)疑問(wèn)，答案是1。

得到這一答案之后，我們可以略微擴(kuò)大問(wèn)題的規(guī)模： 有足夠量的1分硬幣，湊齊2分錢(qián)有多少種方法？湊齊n分錢(qián)有多少種方法？答案仍然是1

接下來(lái)，我們可以從另一個(gè)角度來(lái)擴(kuò)大問(wèn)題，有足夠量的1分硬幣和2分硬幣，湊齊n分錢(qián)有多少種方法？這時(shí)我們手里已經(jīng)有了有足夠量的1分硬幣，湊齊任意多錢(qián)都只有1種方法，那么只用1分錢(qián)湊齊n-2分錢(qián)，有1種方法，只用1分錢(qián)湊齊n-4分錢(qián)，有1種方法，只用1分錢(qián)湊齊n-6分錢(qián)，有1種方法......

而湊齊這些n-2、n-4、n-6這些錢(qián)數(shù)，各自補(bǔ)上2分錢(qián)，會(huì)產(chǎn)生一種新的湊齊n分錢(qián)的方法，這些方法的總數(shù)+1，就是用1分硬幣和2分硬幣，湊齊n分錢(qián)的方法數(shù)了。

在面試時(shí)，立刻采用這種思路是一種非常有益的嘗試，解決小規(guī)模問(wèn)題可以讓你更加熟悉問(wèn)題，并且慢慢發(fā)現(xiàn)問(wèn)題的特性，最重要的是給你的面試官正面的信號(hào)——立即動(dòng)手分析問(wèn)題比皺眉冥思苦想看起來(lái)好得多。

對(duì)于此題而言，我們可以很快發(fā)現(xiàn)問(wèn)題的規(guī)模有兩個(gè)維度：用a1-ak種硬幣和湊齊n分錢(qián)，所以我們可以記做P(k,n)。當(dāng)我們發(fā)現(xiàn)遞歸公式 P(k,n) = P(k-1,n - ak) + P(k-1,n - 2*ak) + P(k-1,n - 3*ak) ... ... 時(shí)，這個(gè)問(wèn)題已經(jīng)是迎刃而解了

通常由簡(jiǎn)至繁的思路，用來(lái)解決動(dòng)態(tài)規(guī)劃問(wèn)題是非常有效的，當(dāng)積累了一定量簡(jiǎn)單問(wèn)題的解的時(shí)候，往往通向更高一層問(wèn)題的答案已經(jīng)擺在眼前了。

（二）一分為二

另一種思路，就是把問(wèn)題一刀斬下，把問(wèn)題分為兩半，變成兩個(gè)與原來(lái)問(wèn)題同構(gòu)的問(wèn)題，能把問(wèn)題一分為2，就能再一分為4，就能再一分為8，直到分成我們?nèi)菀捉鉀Q的問(wèn)題。當(dāng)嘗試這種思路時(shí)，其實(shí)只需要考慮兩個(gè)問(wèn)題：1.一分為二以后，問(wèn)題是否被簡(jiǎn)化了？ 2.根據(jù)一分為二的兩個(gè)問(wèn)題的解，能否方便地得出整個(gè)問(wèn)題的解？

[題目]將一個(gè)數(shù)組排序。

這個(gè)經(jīng)典算法肯定所有人都熟悉的不能再熟悉了，不過(guò)若是從頭開(kāi)始思考這個(gè)問(wèn)題，倒也不是所有人都能想出幾種經(jīng)典的排序算法之一的，這里僅僅是用來(lái)做例子說(shuō)明一分為二的思路的應(yīng)用。

最簡(jiǎn)單的一分為二，就是將數(shù)組分成兩半，分別排序。對(duì)于兩個(gè)有序數(shù)組，我們有辦法將它合并成一個(gè)有序數(shù)組，所以這個(gè)一分為二的思路是可行的，同樣對(duì)于已經(jīng)分成兩半的數(shù)組，我們還可以將這個(gè)數(shù)組分作兩半，直到我們分好的數(shù)組僅有1個(gè)元素，1個(gè)元素的數(shù)組天然就是有序的。不難看出，按這種思路我們得出的是經(jīng)典數(shù)組排序算法中的“歸并排序”。

還有另一種一分為二的思路，考慮到自然將數(shù)組分成兩半合并起來(lái)比較復(fù)雜，我們可以考慮將數(shù)組按照大于和小于某個(gè)元素分成兩半，這樣只要分別解決就可以直接連接成一個(gè)有序數(shù)組了，同樣這個(gè)問(wèn)題也是能夠再次一分為二。按照這個(gè)思路，則可以得出經(jīng)典數(shù)組排序算法中的“快速排序”。

（三）化虛為實(shí)

這種思路針對(duì)的是浮點(diǎn)數(shù)有關(guān)的特殊問(wèn)題，因?yàn)闊o(wú)論是窮舉還是二分，對(duì)于浮點(diǎn)數(shù)相關(guān)的計(jì)算問(wèn)題（尤其是計(jì)算幾何）都難以啟效，所以化虛為實(shí)，指的是把有點(diǎn)"虛"的浮點(diǎn)數(shù)，用整數(shù)來(lái)替代。具體做法是，把題目中給出的一些浮點(diǎn)數(shù)（不限于浮點(diǎn)數(shù)，我們不關(guān)心其具體大小的整數(shù)也可以）排序，然后用浮點(diǎn)數(shù)的序號(hào)代替本身來(lái)思考問(wèn)題，等到具體計(jì)算時(shí)再替換回來(lái)。

[題目]已知n個(gè)邊水平豎直的矩形（用四元組[x1,y1,x2,y2]表示），求它們的總共覆蓋面積。

因?yàn)樽鴺?biāo)可能出現(xiàn)浮點(diǎn)數(shù)，所以此題看起來(lái)十分繁復(fù)（可以實(shí)踐上面由簡(jiǎn)至繁和一分為二的思路都基本無(wú)效），略一思考，矩形的覆蓋關(guān)系其實(shí)只跟矩形坐標(biāo)的大小有關(guān)，所以我們嘗試思考將矩形的所有x值排序，然后用序號(hào)代替具體豎直，y值亦然，于是我們得到所有矩形其實(shí)處于一個(gè)2nx2n的區(qū)塊當(dāng)中，這樣我們用最簡(jiǎn)單的窮舉辦法，可以計(jì)算出每一個(gè)1x1的格子是否被覆蓋住了。至此，只要我們計(jì)算面積的時(shí)候，把格子的真實(shí)長(zhǎng)寬換算回來(lái)，就已經(jīng)得到題目的答案了。

本文是某天在QQ群里討論面試時(shí)的算法問(wèn)題時(shí)想到要寫(xiě)的，以上三種思路，是我平時(shí)遇到算法問(wèn)題的快速思考方向，并非萬(wàn)靈藥方，若是不能生效，就要靜下心來(lái)慢慢思考觀察了，考慮到面試的時(shí)候基本不會(huì)遇到高難度算法題，這幾種技巧的命中率應(yīng)該不會(huì)太低，共享給大家，希望有所幫助

最新評(píng)論