[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.

Constraints:

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

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

一手顺子。

题意是给一个数组，里面存的是整数；同时给一个参数W。请问给的数组是否可以被分成W个数组，同时每个数组都是由连续递增的数字组成的。

这个题的思路别想复杂了。首先需要对数组排序，同时需要对数组的所有元素用hashmap进行统计。比如第一个例子，排序之后长这样，

[1,2,3,6,2,3,4,7,8] ->[1,2,2,3,3,4,6,7,8]

然后对于每一个数字N，我们要找的是是否存在数字N + 1，同时N + 1出现的次数仍然大于0，如果不满足则直接返回false。如果满足，则接着去检查N + 2， N + 3，直到N + W。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public boolean isNStraightHand(int[] hand, int W) {
 3         // corner case
 4         if (hand.length % W != 0) {
 5             return false;
 6         }
 7 
 8         // normal case
 9         HashMap<Integer, Integer> map = new HashMap<>();
10         for (int num : hand) {
11             map.put(num, map.getOrDefault(num, 0) + 1);
12         }
13         Arrays.sort(hand);
14         for (int i = 0; i < hand.length; i++) {
15             if (map.get(hand[i]) == 0) {
16                 continue;
17             }
18             int cur = hand[i];
19             int end = cur + W;
20             while (cur < end) {
21                 int count = map.getOrDefault(cur, 0);
22                 if (count == 0) {
23                     return false;
24                 }
25                 map.put(cur, count - 1);
26                 cur++;
27             }
28         }
29         return true;
30     }
31 }

JavaScript实现

 1 /**
 2  * @param {number[]} hand
 3  * @param {number} W
 4  * @return {boolean}
 5  */
 6 var isNStraightHand = function (hand, W) {
 7     if (hand.length % W !== 0) {
 8         return false;
 9     }
10 
11     let cards = {};
12     hand.forEach((card) => {
13         cards[card] ? cards[card]++ : (cards[card] = 1);
14     });
15 
16     for (let i = 0; i < hand.length; i++) {
17         if (cards[hand[i] - 1] > 0 || !cards[hand[i]]) {
18             continue;
19         }
20         let min = hand[i];
21         let j = 0;
22         while (j < W) {
23             if (cards[min] > 0) {
24                 cards[min]--;
25                 min++;
26             } else {
27                 return false;
28             }
29             j++;
30         }
31     }
32     return true;
33 };