题目描述：

LeetCode 846. Hand of Straights

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

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

Note:

1. 1 <= hand.length <= 10000
2. 0 <= hand[i] <= 10^9
3. 1 <= W <= hand.length

题目大意：

给定一副扑克牌，判断其是否可以分成若干组，使得每一组包含W张连续排列的牌。

解题思路：

时间复杂度：O(N^2 / W)

用字典handDict统计各张牌的个数

每次从handDict中最小的key开始枚举W个元素，若发现不存在的元素，则返回False

否则返回True

Python代码：

class Solution(object):
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        handDict = collections.Counter(hand)
        while handDict:
            mink = min(handDict.keys())
            for y in range(mink, mink + W):
                if not handDict[y]: return False
                handDict[y] -= 1
                if not handDict[y]: del handDict[y]
        return True

 

本文链接：http://bookshadow.com/weblog/2018/06/03/leetcode-hand-of-straights/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码