跳至正文

每日一题——846. 一手顺子

846. 一手顺子

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

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


public class Solution {
    public bool IsNStraightHand(int[] hand, int groupSize) 
    {
        if(hand.Length % groupSize != 0)
        {
            return false;
        }
        Array.Sort(hand);
        Dictionary<int,int> cnt = new Dictionary<int,int>();
        foreach(int x in hand)
        {
            if(!cnt.ContainsKey(x))
            {
                cnt.Add(x,0);
            }
            cnt[x]++;
        }
        //哈希表统计次数
        foreach(int x in hand)
        {
            if(!cnt.ContainsKey(x))
            {
                continue;
            }
            for(int i = 0; i < groupSize; i++)
            {
                int num = x + i;
                if(!cnt.ContainsKey(num))
                {
                    return false;
                }
                cnt[num]--;
                if(cnt[num] == 0)
                {
                    cnt.Remove(num);
                }
            }
        }

        return true;
    }
}

如果不是groupsize的整数倍就直接false了

然后就是经典排序 哈希表记录每个元素出现的次数

重新遍历数组 因为咱升序排列了

所以遍历的这个元素在哈希表就一定是某个组的最小值

(因为重复的元素会在之后被哈希表剔除)

然后就判断x+1和x+2是不是也在哈希表中出现过

出现了那就把次数减一  没出现就直接false

我们就拿第一个例子举例

1 2 2 3 3 4 6 7 8

哈希表的情况是

1(1) 2(2) 3(2) 4(1) 6(1) 7(1) 8(1)

第一个x就是1

那么1次数减1 表直接移除1这个键值对

x+1是2 所以2的次数减1

x+2是3 所以3的次数减1

所以现在哈希表的情况是

2(1) 3(1) 4(1) 6(1) 7(1) 8(1)

第二个x是2

哈希表的情况就是

6(1) 7(1) 8(1)

第三个x是2 不存在哈希表中 跳过

第四个x是3 不存在跳过

第五个x是3 不存在跳过

第六个x是4 不存在跳过

第七个x是6 存在

所以哈希表这次全空了

第八个和第九个自然也找不到了

那么 经过这样的一次遍历

如果没有出现任何不能分组的情况

自然就是true了

发表评论

您的电子邮箱地址不会被公开。