Re: [閒聊] 每日LeetCode
看板Marginalman作者sustainer123 (caster )時間2年前 (2023/11/24 14:44)推噓1(1推 0噓 0→)留言1則, 1人參與討論串535/719 (看更多)
※ 引述《ZooseWu (動物園 公告)》之銘言：
: 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
: }
Python Code:
class Solution:
def maxCoins(self, piles: List[int]) -> int:
l = len(piles)
new_piles = sorted(piles)[l//3:]
result = 0
for i in range(0,len(new_piles),2):
result += new_piles[i]
return result
解法差不多
就每次取最大次大與最小
次大加總即答案
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.235.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700808278.A.593.html
推
11/24 14:50,
2年前
, 1F
11/24 14:50, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 535 之 719 篇)：