class Solution {
public:
int maxmiumScore(vector<int>& cards, int cnt) {
}
};
LCP 40. 心算挑战
「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。
给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
示例 1：
输入：
cards = [1,2,8,9], cnt = 3输出：
18解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。
示例 2：
输入：
cards = [3,3,1], cnt = 1输出：
0解释：不存在获取有效得分的卡牌方案。
提示：
1 <= cnt <= cards.length <= 10^51 <= cards[i] <= 1000原站题解
java 解法, 执行用时: 94 ms, 内存消耗: 56.8 MB, 提交时间: 2023-09-27 14:42:51
class Solution {
public int maxmiumScore(int[] cards, int cnt) {
Arrays.sort(cards);
int len=cards.length;
int sum=0;
int count=0;
for(int i=len-1;i>=0;i--)
{
if(count==cnt)
break;
sum+=cards[i];
count++;
}
if(sum%2==0)
return sum;
int m=len-1-cnt;
int min=Integer.MAX_VALUE;
for(int i=len-cnt;i<len;i++)
{
for(int j=m;j>=0;j--)
{
if(cards[i]%2==0&&cards[j]%2!=0){
min=Math.min(cards[i]-cards[j],min);
break;
}
else if(cards[j]%2==0&&cards[i]%2!=0){
min=Math.min(cards[i]-cards[j],min);
break;
}
}
}
if(min==Integer.MAX_VALUE)
return 0;
else
return sum-min;
}
}
cpp 解法, 执行用时: 352 ms, 内存消耗: 187.8 MB, 提交时间: 2023-09-27 14:41:42
class Solution {
public:
int maxmiumScore(vector<int>& cards, int cnt) {
sort(cards.begin(), cards.end(), greater<int>());
int n = cards.size();
vector<int> odd(1), even(1);
for(int i = 0; i < n; i++){
if(cards[i] & 1){
odd.push_back(odd.back() + cards[i]);
}else{
even.push_back(even.back() + cards[i]);
}
}
int ret = 0, maxv = 0;
for(int i = 0; i < odd.size(); i += 2){
if(cnt - i >= 0 && cnt - i < even.size()){
ret = max(ret, odd[i] + even[cnt - i]);
}
}
return ret;
}
};
python3 解法, 执行用时: 676 ms, 内存消耗: 26.2 MB, 提交时间: 2023-09-27 14:40:24
class Solution:
def maxmiumScore(self, cards: List[int], cnt: int) -> int:
cards.sort(reverse=True)
odd, even = [0], [0] # 前缀和数组（向右偏移一个单位）
for card in cards:
if card & 1:
odd.append(odd[-1] + card)
else:
even.append(even[-1] + card)
# 枚举奇数个数
ans = 0
for k in range(0, len(odd), 2): # 原序列中取偶数个奇数
if 0 <= cnt - k < len(even): # 原序列中取足够个偶数
ans = max(ans, odd[k] + even[cnt-k]) # 排序后前面的数字是最大的，O(1)得到它们的和
return ans
golang 解法, 执行用时: 404 ms, 内存消耗: 8.1 MB, 提交时间: 2023-09-27 14:39:52
func maxmiumScore(cards []int, cnt int) (ans int) {
sort.Sort(sort.Reverse(sort.IntSlice(cards)))
sum := 0
for _, v := range cards[:cnt] {
sum += v
}
if sum&1 == 0 {
return sum
}
// 在 cards[cnt:] 中找一个最大的且奇偶性和 x 不同的元素，替换 x
replace := func(x int) {
for _, v := range cards[cnt:] {
if v&1 != x&1 {
ans = max(ans, sum-x+v)
break
}
}
}
replace(cards[cnt-1]) // 替换 cards[cnt-1]
for i := cnt - 2; i >= 0; i-- {
if cards[i]&1 != cards[cnt-1]&1 { // 找一个最小的且奇偶性不同于 cards[cnt-1] 的元素，将其替换掉
replace(cards[i])
break
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 436 ms, 内存消耗: 8.5 MB, 提交时间: 2021-09-22 15:17:06
func maxmiumScore(cards []int, cnt int) int {
sort.Slice(cards, func(i, j int) bool {
return cards[i] > cards[j]
})
odd, even := []int{0}, []int{0}
for _, card := range cards {
if card & 1 == 1 {
odd = append(odd, odd[len(odd)-1] + card)
} else {
even = append(even, even[len(even)-1] + card)
}
}
ans := 0
for k := 0; k < len(odd); k += 2 {
if cnt >= k && cnt < len(even) + k {
ans = max(ans, odd[k] + even[cnt-k])
}
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}