leetcode
leetcode 751 ~ 800
一手顺子

一手顺子

难度:

标签:

题目描述

代码结果

运行时间: 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`?这个条件失败意味着什么?
检查`len(hand) % groupSize != 0`是为了确保手中的牌能够被完全分成大小为`groupSize`的组。如果这个条件失败,即`len(hand)`不能被`groupSize`整除,这意味着牌的总数不能均匀分配成所需的组大小,因此无法形成所需的顺子组,直接返回`false`是为了提前结束程序,避免无谓的计算。
🦆
在计数器`cnts`中,当发现某个数值`start`的牌的数量为零时,为什么可以直接跳过不处理?
当`cnts[start]`的计数为零时,表示这张牌已经被完全用于之前的组合或者本来就不存在这张牌。因此,没有必要再考虑以这张牌作为新组的起始牌,可以直接跳过,以提高算法的效率。
🦆
在连续检查`groupSize`张牌的过程中,为什么直接使用`if cnts[end] < c`来判断而不是先检查`end`是否存在于`cnts`中?
在Python中,使用`Counter`对象时,尝试访问`Counter`中不存在的键将返回0,而不是引发错误。因此,在这种情况下直接检查`cnts[end] < c`既可以判断牌的数量是否足够,也能处理牌不存在的情况。这样做简化了代码,避免了不必要的键存在性检查。
🦆
如果`groupSize`大于手中牌的种类数量,这种情况下算法是否还能正确执行?
如果`groupSize`大于手中牌的种类数量,算法仍然可以正确执行,但结果会是`false`。因为在这种情况下,无法找到足够的连续数值来形成一个有效的组。算法会在尝试构建第一个组时因找不到足够的连续牌而失败,从而返回`false`。

相关问题