Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
👨💻 Алгоритм:
1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.
2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.
3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.
😎 Решение:
from collections import Counter
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize != 0:
return False
cardCount = Counter(hand)
for card in sorted(hand):
if cardCount[card] == 0:
continue
for nextCard in range(card, card + groupSize):
if cardCount[nextCard] == 0:
return False
cardCount[nextCard] -= 1
return True
Ставь 👍 и забирай 📚 Базу знаний