前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >卡牌分组

卡牌分组

作者头像
OPice
发布2020-04-01 17:44:18
6030
发布2020-04-01 17:44:18
举报
文章被收录于专栏:D·技术专栏D·技术专栏

题目

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

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

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

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

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

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

条件:
- 1 <= deck.length <= 10000
- 0 <= deck[i] < 10000

解答

public static boolean hasGroupsSizeX(int[] deck) {
        int[] ints = new int[10000];
        for (int val : deck) {
            ints[val]++;
        }

        int g = 0;
        for (int val : ints) {
            if (val > 0) {
                if (g == 0) {
                    g = val;
                } else {
                    g = gcd(g, val);
                }
            }
        }
        return g >= 2;

    }

// 求两个数最大公约数的方法
    public static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

// 测试方法:
public static void main(String[] args) {
        int gcd = gcd(8, 12);
        System.out.println(gcd);
        int[] deck = {1, 1};
        boolean b = hasGroupsSizeX(deck);
        System.out.println(b);
    }

分析

第一步 将每个元素出现的次数做统计,元素的值是新数组的下标,次数是新数组的value; 然后依次计算最大公约数,最后判断最大公约数是否大于等于2。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解答
  • 分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档