【LeetCode】一手顺子 Java 题解

2022 年 1 月 02 日
本文字数：980 字
阅读完需：约 3 分钟

题目描述

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

示例 1：
输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3输出：true解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
示例 2：
输入：hand = [1,2,3,4,5], groupSize = 4输出：false解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/hand-of-straights著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是数字排列题目，题意清晰明了，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
根据题意，我们可以按照朴素的算法思想求解。朴素算法有很多的重复查找下一个元素是否存在的过程。我们可以使用 hashmap 存储元素和元素的出现次数，提升查询效率。具体实现如下：

通过代码

class Solution {    public boolean isNStraightHand(int[] hand, int groupSize) {        boolean ans = true;        int n = hand.length;        if (n % groupSize != 0) {            ans = false;            return ans;        }
        Arrays.sort(hand);        Map<Integer, Integer> map = new HashMap<>(n);        for (int i = 0; i < n; i++) {            map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);        }
        for (int item : hand) {            if (map.getOrDefault(item, 0) == 0) {                continue;            }
            for (int j = 0; j < groupSize; j++) {                int next = item + j;                if (map.getOrDefault(next, 0) > 0) {                    map.put(next, map.getOrDefault(next, 0) - 1);                } else {                    ans = false;                    return ans;                }            }        }
        return ans;    }}