這是昨天面試百度時碰到的一道算法題：任意數(shù)分三組，使得每組的和盡量相等（感謝博友提供的關于該問題的相關資料 劃分問題）。由于時間倉促，加之面試時頭昏腦漲，這道題沒做出來甚至沒有給出思路，這讓我多少有些遺憾和不甘。因為最近接觸算法的東西較多而且本身對算法感興趣，所以回家之后絞盡腦汁想把這題做出來。其實剛看到這題時感覺不難，但是因為數(shù)字個數(shù)及數(shù)值的不確定，我感覺這題越想越難。昨天一晚上沒有睡好，甚至做夢都在想這題！
今天上午在多個群里問了這題，都沒有給出思路，真是絕望至極。很多人都說 n/3 的思路，其實這種思路一開始就是死胡同。本人屬于那種不會輕言放棄之人，哈哈。本人多年經(jīng)驗得出一結(jié)論：只要認真思考，有耐心，很多問題都能迎刃而解。每次遇到難纏的問題，我都會抓耳撓腮，而一旦解決，又會手舞足蹈。跑遠了，言歸正傳，中午正準備趴在工位上休息，眼睛掃了掃筆記本，瞬間茅塞頓開。真是踏破鐵鞋無覓處，得來全不費工夫！果不其然，算法就是窗戶紙！
我先說一下我的思路，首先一定要先排序，這也是解決問題的關鍵。然后降序排序后的前三個數(shù)各分一組（根據(jù)博友的評論，此處是問題所在，前三個數(shù)也有可能屬于同一組，暫時沒有想到好方法），把剩余數(shù)往三個數(shù)上疊加。我最開始的思路也是如此，問題在于分組個數(shù)不確定，出現(xiàn)極端大的數(shù)怎么辦，怎么疊加？那層窗戶紙就是將剩余數(shù)中的最大值加到前三個數(shù)的最小值上，然后重排序，繼續(xù)疊加，直到數(shù)組個數(shù)剩三個為止！不知道這樣說好不好理解，比如以下數(shù)組:
[3, 8, 20, 15, 60, 1, 32]; // 分組流程分解，根據(jù)博友評論，此方法屬于貪心算法，只是局部求解：
// 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.
延伸閱讀
- ssh框架
2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍牙鎖
2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe
2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標分割】
2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞
2017-07-26
- 從棧不平衡問題 理解 calling convention
2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明
2017-07-26
- Swift實現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解
2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應用分析
2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二)
2017-07-26
學習是年輕人改變自己的最好方式