九章演算法 | Google 面試題:Take Coins

九章演算法 | Google 面試題:Take Coins

來自專欄九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

有n個硬幣排成一排,每次要你從最左邊或者最右側拿出一個硬幣。總共拿k次。寫一個演算法,使能拿到的硬幣的和最大。

思路點撥

將list的前綴和求出來,然後依次枚舉右邊取x個,那麼剩下就是左邊去k - x個,用前綴和可以O(1)算出答案,所以整體複雜度為O(n)

考點分析

想清楚後可以發現不管每次從左邊還是右邊拿,最後從左邊拿的個數和從右邊拿的個數是確定的,那麼我們可以通過雙指針或者前綴和+掃描線的方式進行枚舉左右拿硬幣的個數,這樣就可以O(n)的複雜度優美的過這題了。

九章參考程序

jiuzhang.com/solution/t

推薦閱讀:

浙江大學-數據結構-選講Huffman Codes-7.4.3
浙江大學-數據結構-基本概念 什麼是數據結構-1.1.1(補前面的章節)
九章演算法 | Facebook面試題:用最少的箭刺破所有氣球
浙江大學-數據結構-小白專場:C語言實現如何建立圖-6.5.4
浙江大學-數據結構-堆排序-9.3.1

TAG:演算法 | IT行業 | 數據結構 |