# 846. Hand of Straights 一手顺子

@TOC

## # 题目描述

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

## # 解题方法

``````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
``````

``````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
``````

``````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;
}
};
``````

## # 日期

2018 年 9 月 8 日 —— 美好的周末，从刷题开始 2019 年 2 月 27 日 —— 二月就要完了