mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
68 lines
1.9 KiB
Markdown
68 lines
1.9 KiB
Markdown
# [846. Hand of Straights](https://leetcode.com/problems/hand-of-straights/)
|
||
|
||
## 题目
|
||
|
||
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
|
||
|
||
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
|
||
|
||
**Example 1**:
|
||
|
||
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 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], groupSize = 4
|
||
Output: false
|
||
Explanation: Alice's hand can not be rearranged into groups of 4.
|
||
|
||
**Constraints:**
|
||
|
||
- 1 <= hand.length <= 10000
|
||
- 0 <= hand[i] <= 1000000000
|
||
- 1 <= groupSize <= hand.length
|
||
|
||
## 题目大意
|
||
|
||
Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
|
||
|
||
给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。
|
||
|
||
## 解题思路
|
||
|
||
贪心算法
|
||
|
||
- 对hand升序排序
|
||
- 对hand内数字进行哈希计数（key:数字，value:数量）
|
||
- 遍历hand中的数字，以数量大于1的数字作为顺子开头，寻找顺子后续元素，若无法找到完整顺子则返回false
|
||
- 所有数字都能找到完整顺子返回true
|
||
|
||
##代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import "sort"
|
||
|
||
func isNStraightHand(hand []int, groupSize int) bool {
|
||
mp := make(map[int]int)
|
||
for _, v := range hand {
|
||
mp[v] += 1
|
||
}
|
||
sort.Ints(hand)
|
||
for _, num := range hand {
|
||
if mp[num] == 0 {
|
||
continue
|
||
}
|
||
for diff := 0; diff < groupSize; diff++ {
|
||
if mp[num+diff] == 0 {
|
||
return false
|
||
}
|
||
mp[num+diff] -= 1
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
``` |