? ? 力扣熱題：卡牌分組

一、開篇

?今天是備戰(zhàn)藍(lán)橋杯的第22天。這道題觸及到我好幾個知識盲區(qū)，以前欠下的債這道題一并補(bǔ)齊，哈希表的遍歷、最大公約數(shù)與最小公倍數(shù)，如果你還沒掌握，這道題練起來！

二、題目鏈接: 914.卡牌分組

三、題目描述

四、代碼思路

1.由于需要每種卡牌的數(shù)量，我們可以利用桶排或哈希表統(tǒng)計(jì)各種卡牌的數(shù)量，下面代碼使用的是哈希表。
2.題目的分組要求是每組要有相同的牌，且牌的數(shù)量要大于等于2，那可以想成每種卡牌之間的最大公約數(shù)大于等于2，瞬間豁然開朗。
3.這樣，我們只需要遍歷哈希表中所有的值，利用求最大公約數(shù)的函數(shù)求出他們之間的最大公約數(shù)即可

五、重要知識點(diǎn)

遍歷哈希表

Map<Integer, Integer> map = new HashMap<>();
for(Map.Entry<Integer, Integer> entry: map.entrySet()){ //增強(qiáng)for循環(huán)gcd1 = entry.getValue(); //gcd1獲取哈希表的值gcd1 = entry.getKey(); //gcd1獲取哈希表的鍵
}

最大公約數(shù)與最小公倍數(shù)

? 最大公約數(shù)：在這個函數(shù)中，如果 x 為0，那么函數(shù)返回 y。否則，函數(shù)將 y 和 x 傳遞給自身，但 x 是 y 對 x 的余數(shù)。這是歐幾里得算法的基本步驟。
? 具體原理大家就自行搜索吧，總之，記住這個函數(shù)，最小公倍數(shù)也能很簡單的推出，真不錯！

//最大公約數(shù)
public int gcd(int x, int y){return x == 0 ? y : gcd(y % x, x);
}//最小公倍數(shù)：調(diào)用最大公約數(shù)函數(shù)
public int lcm(int x, int y) {return x * y / gcd(x, y); //若有負(fù)數(shù)，就取絕對值
}
//擔(dān)心x*y溢出，可以寫成這樣
public int lcm(int x, int y) {int gcd = gcd(x, y);return (x / gcd) * (y / gcd) * gcd;
}

六、代碼純享版

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

七、代碼逐行解析版

class Solution {public boolean hasGroupsSizeX(int[] deck) {Map<Integer, Integer> map = new HashMap<>();//創(chuàng)建哈希表for(int num: deck) { //遍歷整個數(shù)組map.put(num, map.getOrDefault(num, 0) + 1); //統(tǒng)計(jì)每種卡牌的數(shù)量}int gcd1 = -1; //gcd1用來記錄卡牌之間的最大公約數(shù)for(Map.Entry<Integer, Integer> entry: map.entrySet()){ //遍歷整個哈希表if(gcd1 == -1) gcd1 = entry.getValue(); //gcd1還沒有存值時(shí)，存入第一種卡牌的值else gcd1 = gcd(gcd1 , entry.getValue()); //利用函數(shù)求 原先所有卡牌的最大公約數(shù) 與 這個卡牌 的最大公約數(shù)}if(gcd1 >= 2) return true; //當(dāng)gcd1大于等于2時(shí)，說明返回題目要求的X>=2,返回trueelse return false; //否則返回false}public int gcd(int x, int y){ //計(jì)算最大公約數(shù)的函數(shù)，非常實(shí)用簡潔return x == 0 ? y : gcd(y % x, x);}
}

八、結(jié)語

?如果這道力扣題的分享對您有所幫助，點(diǎn)個關(guān)注，我會每天更新力扣題的講解，與大伙兒一同向前邁進(jìn)！