【每日算法打卡】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^5
• 1 <= cards[i] <= 1000

解题思路

根据题目的要求需要数字总和为偶数，那么假设 oddcount 代表奇数卡牌数量，则 oddcount 的取值必须是偶数，此时就有 cnt - oddcount 个偶数卡牌。对于如何获取最大的组合，我们只需要偶数之和与奇数之和最大即可。

代码实现：对 cards 进行降序排序，遍历 cards 中的值，分别构造奇数与偶数前缀和数组 odd_nums , even_nums 。然后从奇数前缀和数组 odd_nums 中取偶数下标的值，此时偶数卡牌的数量为 cnt - oddcount ，在该数量 ≥0 且小于数组长度的前提下，保存遍历过程中的最大组合。

def maxmiumScore(self, cards, cnt):
        """
        :type cards: List[int]
        :type cnt: int
        :rtype: int
        """
        cards.sort(reverse=True)
        odd_nums, even_nums = [0], [0]  # 前缀和数组（向右偏移一个单位）
        for num in cards:
            if num & 1:
                odd_nums.append(odd_nums[-1] + num)
            else:
                even_nums.append(even_nums[-1] + num)
        res = 0
        # 原序列中取偶数个奇数
        for oddcount in range(0, len(odd_nums), 2):
            if 0 <= cnt - oddcount < len(even_nums):
                res = max(res, odd_nums[oddcount] + even_nums[cnt - oddcount])  # 前面都是最大的数
        return res
复制代码

今日打卡完成，目前进度 4/200。