LCP 40. 心算挑战

参考LCP 40. 心算挑战。

题目

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

输入：cards = [1,2,8,9], cnt = 3
输出：18
解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。
输入：cards = [3,3,1], cnt = 1
输出：0
解释：不存在获取有效得分的卡牌方案。
提示：

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

解题思路

• 排序+贪心：因为排序后不影响结果,可以先排序,然后就可以使用贪心解决了。

排序+贪心

class Solution {
    public int maxmiumScore(int[] cards, int cnt) {
        //排序+贪心
        Arrays.sort(cards);
        int n = cards.length;
        int ans = 0,min1 = 0,min2 = 0,ans1 = 0,ans2 = 0;
        for(int i = n-1; i >= 0; i--) {
            if(n-i <= cnt){ //计数cnt个
                ans += cards[i];
                //记录最小的两个奇数和偶数
                if(cards[i]%2 == 0) min2 = cards[i];
                else min1 = cards[i];
                if(n-i == cnt && ans%2 == 0) return ans;
            }else {
                if(min1 > 0 && ans1 == 0 && cards[i]%2 == 0) {
                    ans1 = ans-min1+cards[i];
                }
                if(min2 > 0 && ans2 == 0 && cards[i]%2 == 1){
                    ans2 = ans-min2+cards[i];
                }
                if(ans1 > 0 && ans2 > 0) break;
            }
        }
        if(ans1 > 0 || ans2 > 0) {
            ans = Math.max(ans1,ans2);
        }
        return ans%2 == 0? ans : 0;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为卡片数目,一重循环遍历。
• 空间复杂度：O(logn)，排序栈空间。