题目地址：https://leetcode.com/problems/hand-of-straights/description/

题目描述

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

Nowshe 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，看这堆扑克牌能不能恰好全部拼成长度为W的顺子。

解题方法

这个思路可以说很暴力了。先做个统计，得出手里都有哪些牌，然后找出最小的牌，从这个牌开始长度为W的遍历，判断能否构成长度为W的顺子，就这样求下去即可，直到所有的牌都结束。

做了一个优化的地方，找出最小的牌的个数，因为这个最小的牌只能和比它大的牌构成顺子，所以我们可以在遍历的时候把后面的牌的个数全部剪掉这个数字。

代码如下：

class Solution(object):
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        cards = collections.Counter(hand)
        while cards:
            start = min(cards.keys()) 
            start_val = cards[start]
            for card in range(start, start + W):
                if card not in cards:
                    return False
                cards[card] -= start_val
                if cards[card] == 0:
                    cards.pop(card)
                elif cards[card] < 0:
                    return False
        return not cards

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

同样的做法，如果提前做一个排序还是能加快这个运算的，这样就不用每次都去求min了。里面用到的一个技巧是range(W)之后做了一个翻转，也就是说先从大的值开始减，这样能保证cards[start]不受干扰。

class Solution(object):
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        cards = collections.Counter(hand)
        for start in sorted(cards):
            if cards[start] > 0:
                for j in range(W)[::-1]:
                    if start + j not in cards:
                        return False
                    cards[start + j] -= cards[start]
                    if cards[start + j] < 0:
                        return False
        return True

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

用C++刷题的时候，使用Map保存每个数字的数量，因为map是自动排好序的。所以少了排序的步骤。统计个数之后，直接进行遍历，对于每个数字都向他后面搜索W - 1个数字。方法比较直白。

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        map<int, int> count;
        for (int h : hand) {
            ++count[h];
        }
        for (auto c : count) {
            int cur = c.first;
            int n = c.second;
            if (n > 0) {
                for (int i = 1; i < W; ++i) {
                    if (!count.count(cur + i)) {
                        return false;
                    }
                    count[cur + i] -= n;
                    if (count[cur + i] < 0)
                        return false;
                }
            }
        }
        return true;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发