心跳挑战

题目描述

心算项目的挑战比赛中，要求选手从 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
# 解释：不存在获取有效得分的卡牌方案。

解题思路

排序卡牌：首先对卡牌进行从大到小的排序，以便我们可以优先选择最大的卡牌。
根据排序结果，计算cnt张卡牌的总和。
寻找最小奇数和偶数：方便后续进行替换操作。
判断是否替换：根据奇偶值。

作答模板

python 模板

def maxmium_score(self, cards: List[int], cnt: int) -> int:
    """
    中间是你要实现的代码
    """
    return result

java 模板

class Solution {
        public int maxmiumScore(int[] cards, int cnt){
        // 中间是你要实现的代码
        return result;
    }
}
  ```

## 参考答案

- python

```python
from typing import List


class Solution:

    def maxmium_score(self, cards: List[int], cnt: int) -> int:
        # 1. 需要进行排序操作，从大到小排序，为了方便后续优先选择最大值
        cards.sort(reverse=True)

        # 2. 定义用来存放最终结果的变量
        result = 0

        # 3. 定义用来存放最大数字中，最小的ji和ou
        ji = ou = float('inf')

        # 4. 计算前cnt张卡牌的总和
        selected_sum = sum(cards[:cnt])

        # 5. 判断前cnt张卡片的总和是否为偶数
        if selected_sum % 2 == 0:
            return selected_sum

        # 6. 遍历前cnt张卡片，计算他们的总和，并且找出其中的最小的ji和ou数
        for i in range(cnt):
            if cards[i] % 2 == 1:
                # 奇数
                ji = cards[i]
            else:
                # 偶数
                ou = cards[i]

        # 7. 遍历剩余的卡牌（未选中的部分），通过替换
        for i in range(cnt,len(cards)):
            # 判断是奇数还是偶数
            if cards[i] % 2 == 1:
                if ou != float('inf'):
                    # 奇数
                    result = max(result,selected_sum - ou + cards[i])
            else:
                if ji != float('inf'):
                    # 偶数
                    result = max(result, selected_sum - ji + cards[i])

        # 返回最大的有效得分
        return result


if __name__ == '__main__':
    # 示例测试
    solution = Solution()
    print(solution.maxmium_score([1, 2, 8, 9], 3))  # 输出: 18
    print(solution.maxmium_score([3, 3, 1], 1))  # 输出: 0

java

package 心跳挑战;

import java.util.Arrays;

public class Solution {
    public int maxmiumScore(int[] cards, int cnt) {
        // 1.对卡牌进行排序，升序
        Arrays.sort(cards);

        // 2.初始化记录最大得分的变量
        int md = 0;

        // 3.初始化用来计算后cnt项卡片的总和
        int sum = 0;

        // 4. 定义两个变量，分别为奇数和偶数，他们是用来记录后cnt项卡片的最小值
        int ji = -1,ou = -1;

        // 5. 定义循环的终止位置
        int end = cards.length - cnt;

        //6. 遍历后cnt张卡片，为了找最小的奇数和偶数值，计算总和
        for (int i = cards.length - 1;i >= end;i--){
            // 7. 计算总和
            sum += cards[i];
            if (cards[i] % 2 == 0){
                // 偶数
                ou = cards[i];
            }else {
                // 奇数
                ji = cards[i];
            }
        }

        // 7. 判断后cnt张卡片的总和是否为偶数
        if (sum % 2 == 0 ){
            return sum;
        }

        // 8. 剩下的卡牌中找可以替换的有效得分
        for (int i = cards.length - cnt - 1;i >= 0;i--){
            if (cards[i] % 2 != 0 && ou != -1){
                md = Math.max(md,sum - ou + cards[i]);
            }else if (cards[i] % 2 == 0 && ji != -1){
                md = Math.max(md,sum - ji + cards[i]);
            }
        }


        return md;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxmiumScore(new int[]{1, 2, 8, 9}, 3)); // 输出: 18
        System.out.println(solution.maxmiumScore(new int[]{3, 3, 1}, 1));    // 输出: 0
    }
}