来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hand-of-straights

题目描述

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 的组。

提示：

1 <= hand.length <= 104
0 <= hand[i] <= 109
1 <= groupSize <= hand.length

解题思路

使用贪心算法的思路，从小牌开始组顺子，如果小牌都无法组顺子，那么必定这副牌没有办法组成顺子，一直到所有的牌组成顺子为止。

使用桶排序统计这副牌的不同牌面的个数。

从小开始遍历，在小牌x数量不为0情况下，寻找区间[x + 1, x + groupSize) 的牌面个数是否小于x的数量，如果是，那么x无法组成规定的顺子，返回false，如果不是，在区间中减去x的数量同时将x数量置为0。

当遍历完毕，代表所有牌都组成了顺子，返回true。

代码展示

class Solution {

public:

    bool isNStraightHand(vector<int>& hand, int groupSize) {

        map<int, int> mapiiBucket;

        for(auto iter : hand)

        {

            mapiiBucket[iter]++;

        }

        for(auto iter: mapiiBucket)

        {

            if(iter.second > 0)

            {

                int iX = iter.second;

                mapiiBucket[iter.first] = 0;

                for(int i = 1; i < groupSize; i++)

                {

                    if(mapiiBucket[iter.first + i] < iX)

                    {

                        return false;

                    }

                    mapiiBucket[iter.first + i] -= iX;

                }

            }

        }

        return true;

    }

};

巴特西

LeetCode-846 一手顺子

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章