846. Hand of Straights - Medium

前往題目

想法

• 用dp?

思路

1. 使用hashmap來儲存每個數字的個數，還有min heap來儲存最小值
2. 循環直到minheap的數字都被取光
3. 每次循環都先把最小的數字當基準點，然後再檢查這個數字的group能不能被建立
4. 能不能被建立需要以下判斷
   • hashmap中有我們要的數字
   • 取了之後，如果當前數字已經沒得取了，就看是否當前數字跟minheap的數字一樣，不一樣的話就代表沒辦法建立群組，因為缺了數字

Code

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        // Check if divisible
        if (hand.length % groupSize != 0) return false;
        
        // Count the amount of each number
        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < hand.length; ++i) {
            count.put(hand[i], count.getOrDefault(hand[i], 0) + 1);
        }

        // Use min heap
        PriorityQueue<Integer> minH = new PriorityQueue<>((a, b) -> (a - b));
        for (int key : count.keySet()) {
            minH.add(key);
        }

        // Until all the numbers are picked
        while (!minH.isEmpty()) {
            // First number of a group
            int first = minH.peek();

            // Try to make the group complete
            for (int i = first; i < first + groupSize; ++i) {
                // Must contain the number we need
                if (!count.containsKey(i)) return false;
                // Decrease the amount of number i
                count.put(i, count.get(i) - 1);
                // Check if the amount of number i reached 0
                // meaning the number should be removed from the minH
                if (count.get(i) == 0) {
                    // Current number should be identical to the minimum num
                    // of the minH, to prevent missing middle number in the group
                    if (i != minH.peek()) return false;
                    minH.poll();
                }
            }
        }
        return true;

    }
}