題目敘述 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的順子即可。
算是一道基本的流程模擬題。
