LeetCode 846: Hand of Straights (Counting Map + Greedy Consecutive Chains)
LeetCode 846GreedyHash MapToday we solve LeetCode 846 - Hand of Straights.
Source: https://leetcode.com/problems/hand-of-straights/
English
Problem Summary
Given an integer array hand and an integer groupSize, determine whether you can rearrange all cards into groups where each group has exactly groupSize cards and values are consecutive.
Key Idea
If grouping is possible, the smallest remaining card must always be the start of some consecutive group. So we count frequencies, process numbers in ascending order, and greedily consume x, x+1, ..., x+groupSize-1.
Algorithm
1) If len(hand) % groupSize != 0, return false.
2) Build frequency map for all values.
3) Sort distinct values ascending.
4) For each value x, if count[x] > 0, let it be need groups to start.
5) For every y in [x, x+groupSize-1], ensure count[y] >= need, then subtract need.
6) If all succeed, return true.
Complexity
Time complexity O(n log n) (sorting). Space complexity O(n).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
int n = hand.length;
if (n % groupSize != 0) return false;
Map cnt = new HashMap<>();
for (int x : hand) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
int[] keys = cnt.keySet().stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(keys);
for (int x : keys) {
int need = cnt.getOrDefault(x, 0);
if (need == 0) continue;
for (int y = x; y < x + groupSize; y++) {
int c = cnt.getOrDefault(y, 0);
if (c < need) return false;
cnt.put(y, c - need);
}
}
return true;
}
} func isNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
cnt := map[int]int{}
for _, x := range hand {
cnt[x]++
}
keys := make([]int, 0, len(cnt))
for k := range cnt {
keys = append(keys, k)
}
slices.Sort(keys)
for _, x := range keys {
need := cnt[x]
if need == 0 {
continue
}
for y := x; y < x+groupSize; y++ {
if cnt[y] < need {
return false
}
cnt[y] -= need
}
}
return true
}class Solution {
public:
bool isNStraightHand(vector& hand, int groupSize) {
int n = (int)hand.size();
if (n % groupSize != 0) return false;
map cnt;
for (int x : hand) cnt[x]++;
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
int x = it->first;
int need = it->second;
if (need == 0) continue;
for (int y = x; y < x + groupSize; ++y) {
if (cnt[y] < need) return false;
cnt[y] -= need;
}
}
return true;
}
}; from collections import Counter
class Solution:
def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
if len(hand) % groupSize != 0:
return False
cnt = Counter(hand)
for x in sorted(cnt):
need = cnt[x]
if need == 0:
continue
for y in range(x, x + groupSize):
if cnt[y] < need:
return False
cnt[y] -= need
return Truevar isNStraightHand = function(hand, groupSize) {
if (hand.length % groupSize !== 0) return false;
const cnt = new Map();
for (const x of hand) cnt.set(x, (cnt.get(x) || 0) + 1);
const keys = Array.from(cnt.keys()).sort((a, b) => a - b);
for (const x of keys) {
const need = cnt.get(x) || 0;
if (need === 0) continue;
for (let y = x; y < x + groupSize; y++) {
const c = cnt.get(y) || 0;
if (c < need) return false;
cnt.set(y, c - need);
}
}
return true;
};中文
题目概述
给定整数数组 hand 和整数 groupSize。判断能否把所有牌重新排列成若干组，每组长度都为 groupSize，且每组内部是连续整数。
核心思路
若可行，当前最小的未使用牌一定是某一组的起点。于是用频次数组（哈希表）统计每个值出现次数，按升序遍历，从最小值开始贪心地扣减连续段 x..x+groupSize-1。
算法步骤
1）若 len(hand) % groupSize != 0，直接返回 false。
2）统计每个牌值频次。
3）将不同牌值升序排序。
4）遍历每个起点 x，若 count[x] = need > 0，表示要新开 need 组。
5）检查并扣减 x..x+groupSize-1 中每个值的频次，任意不足则失败。
6）全部扣减成功则返回 true。
复杂度分析
时间复杂度 O(n log n)（排序开销），空间复杂度 O(n)。
参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
int n = hand.length;
if (n % groupSize != 0) return false;
Map cnt = new HashMap<>();
for (int x : hand) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
int[] keys = cnt.keySet().stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(keys);
for (int x : keys) {
int need = cnt.getOrDefault(x, 0);
if (need == 0) continue;
for (int y = x; y < x + groupSize; y++) {
int c = cnt.getOrDefault(y, 0);
if (c < need) return false;
cnt.put(y, c - need);
}
}
return true;
}
} func isNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
cnt := map[int]int{}
for _, x := range hand {
cnt[x]++
}
keys := make([]int, 0, len(cnt))
for k := range cnt {
keys = append(keys, k)
}
slices.Sort(keys)
for _, x := range keys {
need := cnt[x]
if need == 0 {
continue
}
for y := x; y < x+groupSize; y++ {
if cnt[y] < need {
return false
}
cnt[y] -= need
}
}
return true
}class Solution {
public:
bool isNStraightHand(vector& hand, int groupSize) {
int n = (int)hand.size();
if (n % groupSize != 0) return false;
map cnt;
for (int x : hand) cnt[x]++;
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
int x = it->first;
int need = it->second;
if (need == 0) continue;
for (int y = x; y < x + groupSize; ++y) {
if (cnt[y] < need) return false;
cnt[y] -= need;
}
}
return true;
}
}; from collections import Counter
class Solution:
def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
if len(hand) % groupSize != 0:
return False
cnt = Counter(hand)
for x in sorted(cnt):
need = cnt[x]
if need == 0:
continue
for y in range(x, x + groupSize):
if cnt[y] < need:
return False
cnt[y] -= need
return Truevar isNStraightHand = function(hand, groupSize) {
if (hand.length % groupSize !== 0) return false;
const cnt = new Map();
for (const x of hand) cnt.set(x, (cnt.get(x) || 0) + 1);
const keys = Array.from(cnt.keys()).sort((a, b) => a - b);
for (const x of keys) {
const need = cnt.get(x) || 0;
if (need === 0) continue;
for (let y = x; y < x + groupSize; y++) {
const c = cnt.get(y) || 0;
if (c < need) return false;
cnt.set(y, c - need);
}
}
return true;
};
Comments