846. Hand of Straights
給定一整數陣列和分組大小
回傳可否把數字分組，每一組的數字要連續
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.
思路:
先把數字出現次數記起來
找出一組裡最小的數字
把後面幾組都扣掉同樣次數，扣失敗就return false
C# code:
public class Solution
{
public bool IsNStraightHand(int[] hand, int groupSize)
{
if (hand.Length % groupSize != 0) return false;
var dict = new Dictionary<int, int>();
foreach (int key in hand)
{
if (dict.ContainsKey(key)) dict[key]++;
else dict[key] = 1;
}
var keys = dict.Keys.ToList();
keys.Sort();
foreach (int start in keys)
{
if (dict.TryGetValue(start, out int count) == false) continue;
for (int i = 0; i < groupSize; i++)
{
int key = start + i;
if (dict.ContainsKey(key) == false) return false;
dict[key] -= count;
if (dict[key] < 0) return false;
if (dict[key] == 0)
{
dict.Remove(key);
}
}
}
return true;
}
}