leetcode914-卡牌分组

原题

给定一副牌,每张牌上都写着一个整数。

此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组:

  • 每组都有 X 张牌。
  • 组内所有的牌上都写着相同的整数。
    仅当你可选的 X >= 2 时返回 true

示例 1:

输入: [1,2,3,4,4,3,2,1] 输出: true
解释: 可行的分组是 [1,1],[2,2],[3,3],[4,4]

示例 2:

输入: [1,1,1,2,2,2,3,3] 输出: false
解释: 没有满足要求的分组。

示例 3:

输入: [1] 输出: false
解释: 没有满足要求的分组。

示例 4:

输入: [1,1] 输出: true
解释: 可行的分组是 [1,1]

示例 5:

输入: [1,1,2,2,2,2] 输出: true
解释: 可行的分组是 [1,1],[2,2],[2,2]

提示:

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

解法

思想

哈希表获取所有数的出现次数,这些数字的最大公约数不小于2

代码

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i:deck){
            map.put(i,map.getOrDefault(i,0)+1);
        } 
        Integer count = null;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(count == null){
                if(entry.getValue()==1){
                    return false;
                }else{
                    count = entry.getValue();
                }
            }else{
                count = gcd(count,entry.getValue());
                if(count<2) return false;
            }
        }
        return true;
    }

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode914-%e5%8d%a1%e7%89%8c%e5%88%86%e7%bb%84/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月26日 22:31
下一篇 2020年3月27日

相关推荐

  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0170
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0360
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0140
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0130
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0170
  • 剑指offer03-数组中重复的数字

    原题(来源Leetcode) 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,…

    算法 2020年3月13日
    0140
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    080

发表回复

登录后才能评论