当前位置:网站首页>LeetCode 1561. The maximum number of coins you can get
LeetCode 1561. The maximum number of coins you can get
2022-07-06 16:42:00 【Daylight629】
1561. The maximum number of coins you can get
Yes 3n A pile of coins in different numbers , You and your friends are going to divide coins in the following way :
- In every round , You will choose arbitrarily 3 Pile coins ( Not necessarily continuous ).
- Alice The pile with the largest number of coins will be taken away .
- You will take away the pile with the second largest number of coins .
- Bob Will take the last pile .
- Repeat the process , Until there are no more coins .
Give you an array of integers piles
, among piles[i]
It's No i
The number of coins in the pile .
Returns the maximum number of coins you can get .
Example 1:
Input :piles = [2,4,1,2,7,8]
Output :9
explain : elect (2, 7, 8) ,Alice Take away 8 The pile of coins , You take it 7 The pile of coins ,Bob Take the last pile .
elect (1, 2, 4) , Alice Take away 4 The pile of coins , You take it 2 The pile of coins ,Bob Take the last pile .
The maximum number of coins you can get :7 + 2 = 9.
Consider the other case , If you choose (1, 2, 8) and (2, 4, 7) , You can only get 2 + 4 = 6 Coin , This is not the optimal solution .
Example 2:
Input :piles = [2,4,5]
Output :4
Example 3:
Input :piles = [9,8,7,6,5,1,2,3,4]
Output :18
Tips :
3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4
Two 、 Method 1
greedy , By sorting , Ahead 1/3 All are Bob Of , We reverse the order , Take the second largest pile
class Solution {
public int maxCoins(int[] piles) {
Arrays.sort(piles);
int round = piles.length / 3;
int idx = piles.length - 2;
int res = 0;
for (int i = 0; i < round; i++) {
res += piles[idx];
idx -= 2;
}
return res;
}
}
Complexity analysis
Time complexity :O(nlogn), among nn Is the length of the array divided by 3( That is, the length of the array is 3n). The time complexity of sorting is O(3nlog3n)=O(3n(log3+logn))=O(nlogn), The time complexity of traversing the array to calculate the maximum number of coins is O(n), So the total time complexity is O(nlogn).
Spatial complexity :O(logn).
边栏推荐
- 第2章 HFDS的Shell操作
- (lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
- Cmake Express
- Audio and video development interview questions
- Chapter III principles of MapReduce framework
- Codeforces Round #771 (Div. 2)
- 指定格式时间,月份天数前补零
- Soft music -js find the number of times that character appears in the string - Feng Hao's blog
- Chapter 6 datanode
- Li Kou: the 81st biweekly match
猜你喜欢
Spark independent cluster dynamic online and offline worker node
Ffmpeg command line use
第6章 Rebalance详解
Advancedinstaller installation package custom action open file
(lightoj - 1369) answering queries (thinking)
Oneforall installation and use
SQL快速入门
拉取分支失败,fatal: ‘origin/xxx‘ is not a commit and a branch ‘xxx‘ cannot be created from it
ffmpeg命令行使用
sublime text 代码格式化操作
随机推荐
Click QT button to switch qlineedit focus (including code)
Double specific tyrosine phosphorylation regulated kinase 1A Industry Research Report - market status analysis and development prospect prediction
第6章 Rebalance详解
Chapter 5 namenode and secondarynamenode
Generate random password / verification code
The concept of spark independent cluster worker and executor
Codeforces Round #771 (Div. 2)
提交Spark应用的若干问题记录(sparklauncher with cluster deploy mode)
简单尝试DeepFaceLab(DeepFake)的新AMP模型
Hbuilder x format shortcut key settings
Chapter III principles of MapReduce framework
875. Leetcode, a banana lover
Chapter 7__ consumer_ offsets topic
QT implementation fillet window
Submit several problem records of spark application (sparklauncher with cluster deploy mode)
Codeforces Round #799 (Div. 4)A~H
软通乐学-js求字符串中字符串当中那个字符出现的次数多 -冯浩的博客
Business system compatible database oracle/postgresql (opengauss) /mysql Trivia
两个礼拜速成软考中级软件设计师经验
业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事