珠海网站建设费用,安徽整站优化,ui是网站建设吗,新增网站 备案力扣热题#xff1a;卡牌分组
一、开篇 今天是备战蓝桥杯的第22天。这道题触及到我好几个知识盲区#xff0c;以前欠下的债这道题一并补齐#xff0c;哈希表的遍历、最大公约数与最小公倍数#xff0c;如果你还没掌握#xff0c;这道题练起来#xff01;
二、题目链接:… 力扣热题卡牌分组
一、开篇 今天是备战蓝桥杯的第22天。这道题触及到我好几个知识盲区以前欠下的债这道题一并补齐哈希表的遍历、最大公约数与最小公倍数如果你还没掌握这道题练起来
二、题目链接: 914.卡牌分组
三、题目描述
四、代码思路
1.由于需要每种卡牌的数量我们可以利用桶排或哈希表统计各种卡牌的数量下面代码使用的是哈希表。 2.题目的分组要求是每组要有相同的牌且牌的数量要大于等于2那可以想成每种卡牌之间的最大公约数大于等于2瞬间豁然开朗。 3.这样我们只需要遍历哈希表中所有的值利用求最大公约数的函数求出他们之间的最大公约数即可
五、重要知识点
遍历哈希表
MapInteger, Integer map new HashMap();
for(Map.EntryInteger, Integer entry: map.entrySet()){ //增强for循环gcd1 entry.getValue(); //gcd1获取哈希表的值gcd1 entry.getKey(); //gcd1获取哈希表的键
}最大公约数与最小公倍数 最大公约数在这个函数中如果 x 为0那么函数返回 y。否则函数将 y 和 x 传递给自身但 x 是 y 对 x 的余数。这是欧几里得算法的基本步骤。 具体原理大家就自行搜索吧总之记住这个函数最小公倍数也能很简单的推出真不错
//最大公约数
public int gcd(int x, int y){return x 0 ? y : gcd(y % x, x);
}//最小公倍数调用最大公约数函数
public int lcm(int x, int y) {return x * y / gcd(x, y); //若有负数就取绝对值
}
//担心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) {MapInteger, Integer map new HashMap();for(int num: deck) {map.put(num, map.getOrDefault(num, 0) 1);}int gcd1 -1;for(Map.EntryInteger, 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) {MapInteger, Integer map new HashMap();//创建哈希表for(int num: deck) { //遍历整个数组map.put(num, map.getOrDefault(num, 0) 1); //统计每种卡牌的数量}int gcd1 -1; //gcd1用来记录卡牌之间的最大公约数for(Map.EntryInteger, Integer entry: map.entrySet()){ //遍历整个哈希表if(gcd1 -1) gcd1 entry.getValue(); //gcd1还没有存值时存入第一种卡牌的值else gcd1 gcd(gcd1 , entry.getValue()); //利用函数求 原先所有卡牌的最大公约数 与 这个卡牌 的最大公约数}if(gcd1 2) return true; //当gcd1大于等于2时说明返回题目要求的X2,返回trueelse return false; //否则返回false}public int gcd(int x, int y){ //计算最大公约数的函数非常实用简洁return x 0 ? y : gcd(y % x, x);}
}八、结语 如果这道力扣题的分享对您有所帮助点个关注我会每天更新力扣题的讲解与大伙儿一同向前迈进
