头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):914. X of a Kind in a Deck of Cards》

 1月前  •   LeetCode  •     •   19  •   0

Question:

In a 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]

Solution:

此题本质上是最大公约数(gcd)问题,只不过不是求两个数的最大公约数,而是求整个数组中每个数字个数的最大公约数。如果最大公约数大于等于2则返回true,否则返回false。

JAVAclass Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int i : deck) count.put(i, count.getOrDefault(i, 0) + 1);
        for (int i : count.values()) res = gcd(i, res);
        return res > 1;
    }

    public int gcd(int a, int b) {
        return b > 0 ? gcd(b, a % b) : a;
    }
}

 

上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!