LCP 40. 心算挑战

Posted on | In
Words count in article: 304 | Reading time ≈ 1

题目

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

示例 1:

1
2
3
4
5
输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

示例2：

1
2
3
4
5
输入：cards = [3,3,1], cnt = 1

输出：0

解释：不存在获取有效得分的卡牌方案。

提示：

  • 1 <= cnt <= cards.length <= 10^5
  • 1 <= cards[i] <= 1000

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxmiumScore(int[] cards, int cnt) {
        Arrays.sort(cards);
        int sum = 0;
        int index = cards.length - 1;
        while (cnt > 0) {
            sum += cards[index--];
            cnt--;
        }
        if (sum % 2 == 0) {
            return sum;
        }
        for (int i = index; i >= 0; i--) {
            for (int j = index + 1; j < cards.length; j++) {
                sum -= cards[j];
                sum += cards[i];
                if (sum % 2 == 0) {
                    return sum;
                }
                sum -= cards[i];
                sum += cards[j];
            }
        }
        return 0;
    }
0%