个人中心
gpt4 book ai didi

914. X of a Kind in a Deck of Cards 卡牌分组

转载 作者：大佬之路 更新时间：2024-01-31 14:16:06 26 4
gpt4 key购买 nike

题目地址: https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/

题目描述

Ina deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards. All the cards in each group have the same integer.

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:

1、 1<=deck.length<=10000；
2、 0<=deck[i]<10000；

题目大意

判断一堆牌能不能分成很多组，每个组是相同的元素，并且每个组最少两张牌。

解题方法

遍历

果然是个Easy的题目，很简单。

每个组的元素都是相同的情况下，分组之后每个组有多少个元素呢？

首先，要求每个组的元素都是相同的，因此元素个数最小的那个组限制了每个组的个数。

但不一定是所有元素个数的最小值，因为相同的元素可以分成很多组的，比如这个测试用例，每个组可以都是两个元素即可。

[1,1,1,1,2,2,2,2,2,2]

所以，可以用一个遍历，从2遍历到最少次数的数字中的元素个数。道理是，把最少次数在划分和不划分的情况下，看其他组能不能按照这个个数进行均分。

最坏情况下的时间复杂度是O(N^2)，空间复杂度是O(N)。

Python代码如下：

class Solution(object):
    def hasGroupsSizeX(self, deck):
        """
        :type deck: List[int]
        :rtype: bool
        """
        count = collections.Counter(deck)
        X = min(count.values())
        for x in range(2, X + 1):
            if all(v % x == 0 for v in count.values()):
                return True
        return False

1 2 3 4 5 6 7 8 9 10 11 12

最大公约数

二刷的时候想到了最大公约数解法。

最终分的组的大小是多少，就是每个数字的次数的最大公约数。

比如例子：

[1,1,2,2,2,2]

最终分成了[1,1],[2,2],[2,2]，每个组是2个数字，怎么得来的？看1出现了2次，看2出现了4次，最终的结果就是2和4的最大公约数2。

公约数能被所有的数字个数整除，所以最大的那个公约数，就是能被所有数字个数整除的最大组大小。

C++代码如下：

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> counter;
        for (int d : deck) {
            counter[d] ++;
        }
        int res = 0;
        for (auto& c : counter) {
            res = gcd(c.second, res);
        }
        return res > 1;
    }
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

26 4 0
文章推荐： 925. Long Pressed Name 长按键入
文章推荐： 917. Reverse Only Letters 仅仅反转字母
文章推荐： 906. Super Palindromes 超级回文数
文章推荐： 933. Number of Recent Calls 最近的请求次数
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com