LeetCode 题解工作台
一手顺子
Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的 数值 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们首先判断数组 的长度是否能被 整除，如果不能整除，说明无法将数组划分成若干个长度为 的子数组，直接返回 。 接下来，我们用一个哈希表 统计数组 中每个数字出现的次数，然后对数组 进行排序。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 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 <= 1040 <= hand[i] <= 1091 <= groupSize <= hand.length
注意：此题目与 1296 重复：https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/
解题思路
方法一：哈希表 + 排序
我们首先判断数组 的长度是否能被 整除，如果不能整除，说明无法将数组划分成若干个长度为 的子数组，直接返回 。
接下来，我们用一个哈希表 统计数组 中每个数字出现的次数，然后对数组 进行排序。
然后，我们遍历排序后的数组 ，对于每个数字 ，如果 不为 ，我们枚举 到 的每个数字 ，如果 为 ，说明无法将数组划分成若干个长度为 的子数组，直接返回 。否则，我们将 减 。
遍历结束后，说明可以将数组划分成若干个长度为 的子数组，返回 。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize:
return False
cnt = Counter(hand)
for x in sorted(hand):
if cnt[x]:
for y in range(x, x + groupSize):
if cnt[y] == 0:
return False
cnt[y] -= 1
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ability to recognize and implement a greedy strategy for problem-solving.
- question_mark
Proficiency in using hash tables for counting and grouping elements efficiently.
- question_mark
Understanding the time and space trade-offs involved in array manipulation and sorting.
常见陷阱
外企场景- error
Failing to check if the groupSize divides the hand length evenly, leading to incorrect results.
- error
Not sorting the hand before attempting to form consecutive groups, causing invalid groupings.
- error
Overlooking edge cases such as very small input sizes or input arrays with repeated values.
进阶变体
外企场景- arrow_right_alt
What if the group size is 1? This would simply require checking if the hand can be rearranged into individual groups.
- arrow_right_alt
What if the hand contains large gaps between card values? This may make it impossible to form consecutive groups.
- arrow_right_alt
What if groupSize equals the length of the hand? This forces the entire hand to be checked as a single group of consecutive values.