爱丽丝有一手(hand)由整数数组给定的牌。
现在她想把牌重新排列成组,使得每个组的大小都是 W,且由 W 张连续的牌组成。
如果她可以完成分组就返回 true,否则返回 false。
示例 1:
输入:hand = [1,2,3,6,2,3,4,7,8], W = 3
输出:true
解释:爱丽丝的手牌可以被重新排列为 [1,2,3],[2,3,4],[6,7,8]。
示例 2:
输入:hand = [1,2,3,4,5], W = 4
输出:false
解释:爱丽丝的手牌无法被重新排列成几个大小为 4 的组。
思路
使用TreeMap表示每张牌和出现的次数,每次循环W次比较排是否连续,遍历过得出现次数 - 1,如果减为0以后从map里移除。
public boolean isNStraightHand(int[] hand, int W) {
TreeMap<Integer,Integer> map = new TreeMap<>();
for (int i = 0; i < hand.length; i++) {
if (map.containsKey(hand[i])) {
map.put(hand[i],map.get(hand[i]) + 1);
}else {
map.put(hand[i],1);
}
}
while (map.size() > 0) {
int first = map.firstKey(); //因为treemap是有序的,第一个key就是最小的key,如果用hashmap还要去找最小值
for (int i = 0; i < W; i++) {
if (map.containsKey(first + i)) {
if (map.get(first + i) - 1 == 0) {
map.remove(first + i);
} else {
map.put(first + i, map.get(first + i) - 1);
}
} else {
return false;
}
}
}
return true;
}