這是昨天面試百度時(shí)碰到的一道算法題：任意數(shù)分三組，使得每組的和盡量相等（感謝博友提供的關(guān)于該問題的相關(guān)資料 劃分問題）。由于時(shí)間倉(cāng)促，加之面試時(shí)頭昏腦漲，這道題沒做出來(lái)甚至沒有給出思路，這讓我多少有些遺憾和不甘。因?yàn)樽罱佑|算法的東西較多而且本身對(duì)算法感興趣，所以回家之后絞盡腦汁想把這題做出來(lái)。其實(shí)剛看到這題時(shí)感覺不難，但是因?yàn)閿?shù)字個(gè)數(shù)及數(shù)值的不確定，我感覺這題越想越難。昨天一晚上沒有睡好，甚至做夢(mèng)都在想這題！
今天上午在多個(gè)群里問了這題，都沒有給出思路，真是絕望至極。很多人都說(shuō) n/3 的思路，其實(shí)這種思路一開始就是死胡同。本人屬于那種不會(huì)輕言放棄之人，哈哈。本人多年經(jīng)驗(yàn)得出一結(jié)論：只要認(rèn)真思考，有耐心，很多問題都能迎刃而解。每次遇到難纏的問題，我都會(huì)抓耳撓腮，而一旦解決，又會(huì)手舞足蹈。跑遠(yuǎn)了，言歸正傳，中午正準(zhǔn)備趴在工位上休息，眼睛掃了掃筆記本，瞬間茅塞頓開。真是踏破鐵鞋無(wú)覓處，得來(lái)全不費(fèi)工夫！果不其然，算法就是窗戶紙！
我先說(shuō)一下我的思路，首先一定要先排序，這也是解決問題的關(guān)鍵。然后降序排序后的前三個(gè)數(shù)各分一組（根據(jù)博友的評(píng)論，此處是問題所在，前三個(gè)數(shù)也有可能屬于同一組，暫時(shí)沒有想到好方法），把剩余數(shù)往三個(gè)數(shù)上疊加。我最開始的思路也是如此，問題在于分組個(gè)數(shù)不確定，出現(xiàn)極端大的數(shù)怎么辦，怎么疊加？那層窗戶紙就是將剩余數(shù)中的最大值加到前三個(gè)數(shù)的最小值上，然后重排序，繼續(xù)疊加，直到數(shù)組個(gè)數(shù)剩三個(gè)為止！不知道這樣說(shuō)好不好理解，比如以下數(shù)組:
[3, 8, 20, 15, 60, 1, 32]; // 分組流程分解，根據(jù)博友評(píng)論，此方法屬于貪心算法，只是局部求解：
// 1.從大到小排序
[60, 32, 20, 15, 8, 3, 1] // 2.剩余數(shù)疊加
[60, 32, 35(20+15), 8, 3, 1] // 3.重排序
[60, 35, 32, 8, 3, 1] // 4.再疊加
[60, 35, 40(32+8), 3, 1] // 5.重排序
[60, 40, 35, 3, 1] // 6.
