Re: [閒聊] 每日LeetCode

作者: ZooseWu (N5)   2023-11-24 10:57:20
1561. Maximum Number of Coins You Can Get
桌上有3n堆金幣,你和你的兩位朋友依照下面規則拿金幣:
1.你從中選出三堆金幣
2.Alice從三堆金幣中拿數量最高的一堆金幣
3.你從剩下兩堆金幣中拿一堆金幣
4.Bob拿最後剩下的金幣
5.回到第一步
回傳你最多能獲得的金幣數量
Input: piles = [2,4,1,2,7,8]
Output: 9
你選出[2,7,8]出來,Alice拿走8個金幣,你拿走7個金幣,Bob拿走1個金幣
你選出[1,2,4]出來,Alice拿走4個金幣,你拿走2個金幣,Bob拿走1個金幣
Input: piles = [2,4,5]
Output: 4
Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18
[9,8,1]=>9=>8=>1
[7,6,2]=>7=>6=>2
[5,4,3]=>5=>4=>3
8+6+4=18
Intuition:
玩家每次可以拿到剩餘堆數中第二大堆的金幣
所以可以拿到前2/3中第偶數堆數量的金幣
Approach:
排序之後拿前2/3堆偶數堆的金幣
TS Code:
function maxCoins (piles: number[]): number {
piles.sort((a, b) => b - a)
let result = 0
for (let i = 1; i < piles.length / 3 * 2; i += 2) {
result += piles[i]
}
return result
}

Links booklink

Contact Us: admin [ a t ] ucptt.com