LeetCode_贪心算法_中等_846.一手顺子

1.题目

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize。如果她可能重新排列这些牌，返回 true；否则，返回 false。

示例 1：
输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出：true
解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：
输入：hand = [1,2,3,4,5], groupSize = 4
输出：false
解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

提示：
1 <= hand.length <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/hand-of-straights
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

（1）贪心算法 & 哈希表
思路参考本题官方题解。

① Alice 手中的牌可以被重新排列成几个大小为 groupSize 的组的必要条件是数组 hand 中的元素个数必须是 groupSize 的整数倍，因此可以先对其进行简单的判断，如果不满足直接返回 false；否则继续如下步骤。

② 为了方便分组，对数组 hand 进行升序排序，并且用 hashMap 来保存数组 hand 中的元素以及对应出现的次数。

③ 遍历数组 hand，对于每一个数 x，对其进行如下判断：
1）如果 hashMap 中不包含当前数 x，则说明其已经被分好组，跳过即可；
2）如果 hashMap 中包含当前数 x（即出现次数不为 0），则为当前以 x 开头的组分配 groupSize 个连续的元素，即 [x, x + 1,…, x + groupSize - 1]，在分组的过程中，需要注意以下几点：

• 如果 x + i 不在 hashMap 中，那么说明当前组无法分配 groupSize 个连续的元素，直接返回 false；
• 如果 x + i 被分配到当前组，那么其在 hashMap 中的对应的个数减一；
• 如果 x + i 的次数被全部使用，则将其移出 hashMap；

④ 如果上述的分组过程能够顺利结束，则说明Alice 手中的牌可以被重新排列成几个大小为 groupSize 的组，最后返回 true 即可。

相似题目：LeetCode_优先级队列_回溯_659.分割数组为连续子序列

3.代码实现（Java）

//思路1————贪心算法 & 哈希表
class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int length = hand.length;
        //如果数组 hand 中的元素个数不是 groupSize 的整数倍，那么肯定不能分成若干组，使得每一组的牌数都是 groupSize
        if (length % groupSize != 0) {
            return false;
        }
        //对数组 hand 进行升序排序
        Arrays.sort(hand);
        // hashMap 保存数组 hand 中的元素以及对应出现的次数，方便后续的分组
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int x : hand) {
            hashMap.put(x, hashMap.getOrDefault(x, 0) + 1);
        }
        for (int x : hand) {
        	//如果 hashMap 中不包含当前数 x，则说明其已经被分好组，跳过即可
            if (!hashMap.containsKey(x)) {
                continue;
            }
            //为每一组分配 groupSize 个连续的元素，即[x, x + 1,..., x + groupSize - 1]
            for (int i = 0; i < groupSize; i++) {
                int num = x + i;
                //如果 num 不在 hashMap 中，那么说明当前组无法分配 groupSize 个连续的元素，故直接返回 false
                if (!hashMap.containsKey(num)) {
                    return false;
                }
                //如果 num　被分配到当前组，那么其在 hashMap 中的对应的个数减一
                hashMap.put(num, hashMap.get(num) - 1);
                //如果 num 的次数被全部使用，则将其移出 hashMap
                if (hashMap.get(num) == 0) {
                    hashMap.remove(num);
                }
            }
        }
        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
25
26
27
28
29
30
31
32
33
34
35
36
37
38