846. 一手顺子

问题846 一手顺子 ★★☆☆☆

https://leetcode-cn.com/problems/hand-of-straights/

首先，根据题目要求，如果hand包含的元素值个数不能被groupSize整除，那么显然不能满足分组要求。那么接下来该如何判断是否能满足分组要求呢？我的直觉是先计数，统计每个元素出现的次数。然后我只能想到比较暴力的解法就是按元素值从小到大（因此计数元素个数的map需要使用TreeMap），以groupSize为单元，扣减计数。如果处理到某个元素时当前groupSize大小的单元内不足扣减，或者全部处理完后还有元素的计数大于0，那么就不能满足分组要求，否则就可以满足分组要求。按照这个思路写了一版代码，提交以后也能通过。

看了下官方题解，整体思路上有一些共通之处，但是官方题解里先排序，然后以排序后的hand为遍历对象的处理显然更好，代码更简洁更优雅一些，更能体现贪婪算法的思想。这个题目蛮有意思的，很好的体现了贪婪算法的思想。

	public boolean isNStraightHand(int[] hand, int groupSize) {
		int len = hand.length;
		if (len % groupSize != 0) {
			return false;
		}

		Arrays.sort(hand);

		Map<Integer, Integer> cnt = new HashMap<>();
		for (int val : hand) {
			cnt.put(val, cnt.getOrDefault(val, 0) + 1);
		}

		for (int val : hand) {
			boolean contains = cnt.containsKey(val);
			if (!contains) {
				continue;
			}

			for (int i = 0; i < groupSize; i++) {
				int neededVal = val + i;
				contains = cnt.containsKey(neededVal);
				if (!contains) {
					return false;
				} else {
					int valCnt = cnt.get(neededVal);
					--valCnt;
					if (valCnt > 0) {
						cnt.put(neededVal, valCnt);
					} else {
						cnt.remove(neededVal);
					}
				}
			}
		}

		return true;
	}

在 LeetCode 查看