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

##代码

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
}