打卡今日題目 經(jīng)典最大公約數(shù)題目
914. 卡牌分組
做這題目之前得先知道碾轉(zhuǎn)相除法掀鹅。按照題目意思似乎好像和最大公約數(shù)沒啥大關(guān)系揽碘，但是仔細(xì)想想次屠，好像就是數(shù)字的個(gè)數(shù)的最大公約數(shù)如果大于2的話那就是存在，返回true雳刺，否則返回false
public boolean hasGroupsSizeX(int[] deck) {
/**
*
* 功能描述:給定一副牌劫灶，每張牌上都寫著一個(gè)整數(shù)。
*
* 此時(shí)掖桦，你需要選定一個(gè)數(shù)字 X本昏，使我們可以將整副牌按下述規(guī)則分成 1 組或更多組：
*
* 每組都有 X 張牌。
* 組內(nèi)所有的牌上都寫著相同的整數(shù)枪汪。
*
* @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) { // 如果某步中g(shù)cd是1涌穆，直接返回false
return false;
}
}
}
return x >= 2;
}
private int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
