欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[题记]卡牌分组-lootcode

程序员文章站 2022-05-18 23:46:22
题目:卡牌分组 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。组内所有的牌上都写着相同的整数。仅当你可选的 X >= 2 时返回 true。 示例 1: 输入:[1,2,3,4,4,3,2,1]输出:tru ......

题目:卡牌分组

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

此时,你需要选定一个数字 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 <= deck.length <= 10000
0 <= deck[i] < 10000


 

思路:

  首先根据题目条件,要求我们将牌分成一组或者多组,并且每组牌都是相同的。

  我们可以想到,如果每组只有一张牌,那么无论有多少牌,都是有符合条件的分法的。

  如果每组有两张牌,那么每一种相同牌的总数量就必须是2的倍数,才有符合条件的分法。

  如果每组有三张牌,那么每一张相同牌的总数量就必须是3的倍数,才有符合条件的分法。

 

  由此类推,我们要找的数x则是:

    ★:设集合y

  1. 所有相同牌的总数都是 y 中元素的倍数,也就是都可以整除 y 中的元素
  2.  x 则是 y 元素尽可能大的数

  很明显,y 集合则是所有相同牌数量的公约数,x 则是他们的最大公约数。

 

上代码(c):

//求最大公约数
int gcd( int x, int y ) { int tmp; while( y != 0 ) { tmp = x; x = y; y = tmp%y; } return x; } bool hasgroupssizex(int* deck, int decksize){ int count[10005] = {0}; int x = -1; for( int i = 0; i < decksize; i++ ) { count[deck[i]]++; } for( int i = 0; i < 10005; i++ ) { if( count[i] > 0 ) { if( x == -1 ) ans = count[i]; else x = gcd( ans, count[i] ); } } if( x >= 2 ) return true; return false; }

 

2020-03-27-19:03:11