九章演算法 | Google 面試題:Take Coins
06-07
九章演算法 | Google 面試題:Take Coins
來自專欄九章演算法 - lintcode/leetcode題解
撰文 | JZ
專欄 | 九章演算法
題目描述
有n個硬幣排成一排,每次要你從最左邊或者最右側拿出一個硬幣。總共拿k次。寫一個演算法,使能拿到的硬幣的和最大。
思路點撥
將list的前綴和求出來,然後依次枚舉右邊取x個,那麼剩下就是左邊去k - x個,用前綴和可以O(1)算出答案,所以整體複雜度為O(n)。
考點分析
想清楚後可以發現不管每次從左邊還是右邊拿,最後從左邊拿的個數和從右邊拿的個數是確定的,那麼我們可以通過雙指針或者前綴和+掃描線的方式進行枚舉左右拿硬幣的個數,這樣就可以O(n)的複雜度優美的過這題了。
九章參考程序
https://www.jiuzhang.com/solution/take-coins/
推薦閱讀:
※浙江大學-數據結構-選講Huffman Codes-7.4.3
※浙江大學-數據結構-基本概念 什麼是數據結構-1.1.1(補前面的章節)
※九章演算法 | Facebook面試題:用最少的箭刺破所有氣球
※浙江大學-數據結構-小白專場:C語言實現如何建立圖-6.5.4
※浙江大學-數據結構-堆排序-9.3.1