打卡今日题目 经典最大公约数题目
914. 卡牌分组
做这题目之前得先知道碾转相除法。按照题目意思似乎好像和最大公约数没啥大关系，但是仔细想想，好像就是数字的个数的最大公约数如果大于2的话那就是存在，返回true，否则返回false
public boolean hasGroupsSizeX(int[] deck) {
/**
*
* 功能描述:给定一副牌，每张牌上都写着一个整数。
*
* 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
*
* 每组都有 X 张牌。
* 组内所有的牌上都写着相同的整数。
*
* @param: [deck]
* @return: boolean
* @auther: smallfish
* @date: 2020-03-27 22:05
*/
int[] b = new int[10001];
for (int i : deck) {
b[i]++;
}
int x = 0;
for(int cnt: b) {
if (cnt > 0) {
x = gcd(x, cnt);
if (x == 1) { // 如果某步中gcd是1，直接返回false
return false;
}
}
}
return x >= 2;
}
private int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
