一手顺子
难度:
标签:
题目描述
代码结果
运行时间: 59 ms, 内存: 17.3 MB
/*
* 思路:
* 使用 Java Stream 对输入数组进行排序和计数。
* 然后使用一个 TreeMap 记录每个牌的数量。
* 遍历 TreeMap 的每个条目,如果某个数字的数量大于零,
* 检查其后连续的 groupSize 个数字的数量是否足够,
* 如果不够则返回 false,否则减少这些数字的数量。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) {
return false;
}
Map<Integer, Long> countMap = Arrays.stream(hand)
.boxed()
.collect(Collectors.groupingBy(e -> e, TreeMap::new, Collectors.counting()));
for (Map.Entry<Integer, Long> entry : countMap.entrySet()) {
long count = entry.getValue();
if (count > 0) {
for (int i = 1; i < groupSize; i++) {
if (countMap.getOrDefault(entry.getKey() + i, 0L) < count) {
return false;
}
countMap.put(entry.getKey() + i, countMap.get(entry.getKey() + i) - count);
}
}
}
return true;
}
}
解释
方法:
首先,检查是否可以将手中的牌分成等大小的组,即手中的牌的数量必须是 groupSize 的整数倍。接下来,使用一个计数器 cnts 来统计每张牌出现的次数。然后,对计数器的键(也就是牌的数值)进行排序,依次检查每个数值作为起点的 groupSize 张连续牌是否存在且数量足够。如果存在连续的 groupSize 张牌,则从计数器中减去相应的数量,表示这些牌已经被使用。最后,如果所有的牌都能按要求分组,则返回 true,否则返回 false。
时间复杂度:
O(nlogn)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在算法中第一步就要检查`len(hand) % groupSize != 0`?这个条件失败意味着什么?
▷🦆
在计数器`cnts`中,当发现某个数值`start`的牌的数量为零时,为什么可以直接跳过不处理?
▷🦆
在连续检查`groupSize`张牌的过程中,为什么直接使用`if cnts[end] < c`来判断而不是先检查`end`是否存在于`cnts`中?
▷🦆
如果`groupSize`大于手中牌的种类数量,这种情况下算法是否还能正确执行?
▷