Java | LeetCode
Задача: 846. Hand of Straights
Сложность: 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.
😎 Решение:
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) {
return false;
}
HashMap<Integer, Integer> cardCount = new HashMap<>();
for (int card : hand) {
int count = cardCount.getOrDefault(card, 0);
cardCount.put(card, count + 1);
}
for (int card : hand) {
int startCard = card;
while (cardCount.getOrDefault(startCard - 1, 0) > 0) {
startCard--;
}
while (startCard <= card) {
while (cardCount.getOrDefault(startCard, 0) > 0) {
for (
int nextCard = startCard;
nextCard < startCard + groupSize;
nextCard++
) {
if (cardCount.getOrDefault(nextCard, 0) == 0) {
return false;
}
cardCount.put(nextCard, cardCount.get(nextCard) - 1);
}
}
startCard++;
}
}
return true;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 424 ·