【Ежедневный удар по алгоритму】LCP 40. Умственная арифметика

искусственный интеллект алгоритм
【Ежедневный удар по алгоритму】LCP 40. Умственная арифметика

Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.

【Ежедневные пробные серии】LeetCode200 простых вопросов

Описание темы

В соревновании по ментальной арифметике «Licco Challenge» участники должны начать с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.

Категории