JZX轻语：简

LeetCode 846 - 一手顺子

发表于2024年05月14日

#哈希表 #排序 #计数 #贪心

类似于题目2007，使用贪心法从小到大处理数字。先使用哈希表cnt_map对数字计数。然后从小到大遍历数字num，尝试抽取cnt_map[num]次组(num, num + 1, ..., num + groupSize - 1)，如果组内有个数字的计数小于cnt_map[num]，则无法完成题目要求，直接返回False，直至所有的牌处理完毕。

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:  # 无法刚好分成几个大小为groupSize的组
            return False
        # 先计数
        cnt_map = defaultdict(int)
        for num in hand:
            cnt_map[num] += 1
        # 从小到大抽取牌
        for key in sorted(cnt_map.keys()):
            cnt = cnt_map[key]
            if cnt == 0:
                continue
            
            # 抽出cnt组
            for i in range(1, groupSize):
                if key + i not in cnt_map or cnt_map[key + i] < cnt:  # 组内有个牌的数量不够
                    return False
                cnt_map[key + i] -= cnt
        return True

闪念标签：LC

题目链接：https://leetcode.cn/problems/hand-of-straights/