Re: [閒聊] 每日LeetCode
※ 引述《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
思路：
1.最簡單的作法就用一個MaxHeap，每次pull兩個元素累加第二個元素，直到pull到
指定次數，只是跑出來的時間複雜度滿爛的。
2.題目給的測資滿適合計數排序的，counting之後3ms就AC了。
Java Code：
-----------------------------------------
class Solution {
private int idx;
public int maxCoins(int[] piles) {
int res = 0;
int[] count = new int[10001];
for (int pile : piles) {
count[pile]++;
}
int size = 0;
idx = 10000;
while (size++ != piles.length/3) {
pickMax(count);
res += pickMax(count);
}
return res;
}
private int pickMax(int[] count) {
while (count[idx] == 0) {
idx--;
}
count[idx]--;
return idx;
}
}
-----------------------------------------
感覺這幾天的題目都是冒充Medium
姆咪
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700842492.A.77F.html
推
11/25 00:54,
2年前
, 1F
11/25 00:54, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 536 之 719 篇)：