Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

LeetCode 200 simple questions

Topic describes

In the challenge contest of the mental arithmetic project, contestants are required to choose CNT cards from N cards. If the sum of the CNT cards is even, the contestant’s score is “valid” and the score is the sum of the CNT cards. Given array cards and CNT, where cards[I] represents the number on the ith card. Please calculate the maximum valid score for the contestant. Returns 0 if there is no card scheme for obtaining valid points.

Example 1:

Input: cards = [1,2,8,9]; CNT = 3 Output: 18

Example 2:

Input: cards = [3,3,1]; CNT = 1 output: 0 description: there is no card scheme to obtain valid scores.

prompt

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

Their thinking

If oddcount represents the number of odd cards, oddcount must be an even number. Then cnT-ODdcount has even cards. To get the maximum combination, we just need the sum of the even numbers and the sum of the odd numbers to be maximum. Code implementation: cards in descending order, traversing the value of cards, respectively, the construction of odd and even prefix and array ODD_NUMs, even_NUMS. Then take the value of even subscript from the odd prefix and array ODd_nums. At this time, the number of even cards is CNT-ODdcount. On the premise that the number is ≥0 and less than the array length, the maximum combination in the traversal process is saved.

    def maxmiumScore(self, cards, cnt) :
        """ :type cards: List[int] :type cnt: int :rtype: int """
        cards.sort(reverse=True)
        odd_nums, even_nums = [0], [0]  # prefix and array (offset one unit to the right)
        for num in cards:
            if num & 1:
                odd_nums.append(odd_nums[-1] + num)
            else:
                even_nums.append(even_nums[-1] + num)

        res = 0
        # Take an even number of odd numbers from the original sequence
        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])  # is preceded by the largest number
        return res
Copy the code

Clocked in today, the current progress 4/200.