六六大順 能不能製造出順子? Hand of Straights 堆積/排序應用_Leetcode #846

Aditya Chinchure on Unsplash

題目敘述 Hand of Straights

給定一個整數陣列hand代表手牌點數，和參數groupSize。

請問能不能每groupSize張牌一組，每一組都拼出順子?

例如[1,2,3,4,5] 是一組 groupSize=5的順子

如果可以，返回True。

如果無解，返回False。

測試範例

Example 1:

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,2,3],[2,3,4],[6,7,8]
每一組都是三張牌的順子​

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

無解​

觀察 順子的組成

順子可以怎麼描述?

可以用最小牌+牌組長度groupSize描述

例如最小牌是1，牌組長度groupSize=5

那麼[1,2,3,4,5]就是對應的一組順子

例如最小牌是5，牌組長度groupSize=3

那麼[5,6,7]就是對應的一組順子

演算法 最小堆積/排序

紀錄每個點數的出現次數。

我們就從小到大掃描每張牌，檢查能不能組成牌組長度為groupSize的順子即可。

這邊要使用minHeap或者sort排序皆可，這邊以minHeap最小堆作為示範。

如果某一回合有缺牌湊不出來，代表無解，直接返回False即可。

程式碼 最小堆積/排序

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:

        ## Simple case:
        # Not full division of handcard
        if len(hand) % groupSize > 0:
            return False

        ## Simple case:
        # One card for each group, can be satisfied always.
        if groupSize == 1:
            return True

        ## General cases
        # Maintain a mainheap of poker card points
        heapify(hand)

        # Occurrence of each points
        cnt = Counter(hand)
        
        # Keep taking poker card if deck is not empty
        while hand:
            
            # Take current smallest card point
            cur = heappop(hand)        

            # All card of this point have been used, skip this round.
            if cnt[cur] == 0:
                continue

            # Check if we can make a straight with specified groupSize or not
            for num in range(cur, cur + groupSize):
                if cnt[num] == 0:                    
                    return False

                # used one card, update occurrence of this point
                cnt[num] -= 1

        return True               

複雜度分析

時間複雜度: O( n log n)

使用minHeap抽牌的look耗費O( n log n )時間。

如果用排序，那排序本身也耗費O( n log n )時間。

空間複雜度: O( n )

用字典去記錄每個點數的出現次數，所需空間為O(n)。

關鍵知識點

我們就從小到大掃描每張牌，檢查能不能組成牌組長度為groupSize的順子即可。

算是一道基本的流程模擬題。

Reference

[1] Hand of Straights - LeetCode