846. Hand of Straights

leetcode medium

#array#csharp#hash-table#leetcode#medium#sort

Task

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером 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]

C# solution

matched/original

public class Solution {
    public bool IsNStraightHand(int[] hand, int groupSize) {
        if (hand.Length % groupSize != 0) {
            return false;
        }
        var cardCount = new Dictionary<int, int>();
        foreach (int card in hand) {
            if (!cardCount.ContainsKey(card)) {
                cardCount[card] = 0;
            }
            cardCount[card]++;
        }
        Array.Sort(hand);
        foreach (int card in hand) {
            if (cardCount[card] == 0) {
                continue;
            }
            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (!cardCount.ContainsKey(nextCard) || cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }
        var cardCount = new unordered_map<int, int>();
        foreach (int card in hand) {
            if (!cardCount.count(card)) {
                cardCount[card] = 0;
            }
            cardCount[card]++;
        }
        sort(hand.begin(), hand.end());
        foreach (int card in hand) {
            if (cardCount[card] == 0) {
                continue;
            }
            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (!cardCount.count(nextCard) || cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }
        return true;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

var isNStraightHand = function(hand, groupSize) {
    if (hand.length % groupSize !== 0) {
        return false;
    }

    const cardCount = new Map();
    for (let card of hand) {
        cardCount.set(card, (cardCount.get(card) || 0) + 1);
    }

    hand.sort((a, b) => a - b);

    for (let card of hand) {
        if (cardCount.get(card) === 0) {
            continue;
        }

        for (let nextCard = card; nextCard < card + groupSize; nextCard++) {
            if ((cardCount.get(nextCard) || 0) === 0) {
                return false;
            }
            cardCount.set(nextCard, cardCount.get(nextCard) - 1);
        }
    }

    return true;
};

Python solution

matched/original

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

Go solution

matched/original

import "sort"

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand) % groupSize != 0 {
        return false
    }

    cardCount := make(map[int]int)
    for _, card := range hand {
        cardCount[card]++
    }

    sort.Ints(hand)

    for _, card := range hand {
        if cardCount[card] == 0 {
            continue
        }

        for nextCard := card; nextCard < card + groupSize; nextCard++ {
            if cardCount[nextCard] == 0 {
                return false
            }
            cardCount[nextCard]--
        }
    }

    return true
}

Explanation

Algorithm

Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

Создайте карту cardCount для хранения количества каждой карты в массиве hand.

Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:

Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.

Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.

Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎