LeetCode.914-一副牌中的X(X of a Kind in a Deck of Cards)
这是悦乐书的第352次更新,第377篇原创
01 看题和准备
今天介绍的是LeetCode
算法题中Easy
级别的第214
题(顺位题号是914
)。在一副牌中,每张牌上都写有一个整数。
当且仅当您可以选择X >= 2
时才返回true
,以便可以将整个牌组分成一组或多组牌,其中:
每组都有
X
张牌。每组中的所有牌都具有相同的整数。
例如:
输入:[1,2,3,4,4,3,2,1]
输出:true
说明:可能的分区[1,1],[2,2],[3,3],[4,4]
输入:[1,1,1,2,2,2,3,3]
输出:false
说明:没有可能的分区。
输入:[1]
输出:false
说明:没有可能的分区。
输入:[1,1]
输出:true
说明:可能的分区[1,1]
输入:[1,1,2,2,2,2]
输出:true
说明:可能的分区[1,1],[2,2],[2,2]
注意:
1 <= deck.length <= 10000
0 <= deck[i] <10000
02 第一种解法
题目的意思是将数组deck中的元素进行分组,值相等的划分为同一组,每一组中的元素个数都相等,且大于等于2。我们可以使用一个HashMap
,以deck
中的元素为key
,以其出现次数为value
,对HashMap
的value
值进行遍历。
最理想的情况,HashMap
中只有一组key-value
,但测试用例中肯定不会这么轻易让你AC。来看几组例子分析下规律:
{1,1,1,2,2,2,3,3}
{{1,1,1},{2,2,2},{3,3}} --> {3,3,2}
{1,1,2,2,2,2,3,3,3,3,3,3}
{{1,1},{2,2,2,2},{3,3,3,3,3,3}} --> {2,4,6}
第一个例子中,他们的最大公约数为1,即分组的组数存在奇偶分布的情况。
第二个例子中,他们的最大公约数为2,即分组的组数都是偶数,并且对于其中的4个2和6个3,是还可以继续拆分的,4个2拆成两组2个2,6个3拆成三组2个3。
因此,我们只需要判断HashMap
中每对数据的最大公约数是不是等于1即可。
public boolean hasGroupsSizeX(int[] deck) {
if (deck.length < 2) {
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : deck) {
map.put(num, map.getOrDefault(num, 0)+1);
}
int count = 0;
for (Integer value : map.values()) {
if (value < 2) {
return false;
}
if (count == 0) {
count = value;
} else {
if (count != value) {
int gcd = 1;
for (int i=1; i<= count || i<=value; i++) {
if (count%i == 0 && value%i == 0) {
gcd = i;
}
}
if (gcd == 1) {
return false;
}
}
}
}
return true;
}
03 第二种解法
思路和第一种解法一样,只是将其中部分代码抽离了出来,并且简化了一些if-else
判断。
public boolean hasGroupsSizeX2(int[] deck) {
if (deck.length < 2) {
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : deck) {
map.put(num, map.getOrDefault(num, 0)+1);
}
int min = 10001;
for (Integer num : map.values()) {
min = Math.min(min, num);
}
if (min == 1) {
return false;
}
for (Integer num : map.values()) {
if (getGCD(min, num) == 1) {
return false;
}
}
return true;
}
public int getGCD(int a, int b) {
int gcd = 1;
for (int i=1; i<= a || i<=b; i++) {
if (a%i == 0 && b%i == 0) {
gcd = i;
}
}
return gcd;
}
04 第三种解法
因为限定了数组deck
中元素值范围,因此我们可以使用一个整型数组count
来计算deck
中各元素的出现次数,然后遍历count
中的元素,求出他们的最大公约数,只要有一对数的最大公约数等于1,就直接返回false。
public boolean hasGroupsSizeX3(int[] deck) {
int[] count = new int[10001];
for (int num : deck) {
count[num]++;
}
int temp = -1;
for (int num : count) {
if (num > 0) {
if (num < 2) {
return false;
}
if (temp == -1) {
temp = num;
} else {
if (getGCD(temp, num) == 1) {
return false;
}
}
}
}
return true;
}
public int getGCD(int a, int b) {
int gcd = 1;
for (int i=1; i<= a || i<=b; i++) {
if (a%i == 0 && b%i == 0) {
gcd = i;
}
}
return gcd;
}
05 第四种解法
对第三种解法,我们还可以再优化下,将求最大公约数的方法独立处理,并且用递归处理。
public boolean hasGroupsSizeX4(int[] deck) {
int[] count = new int[10001];
for (int num : deck) {
count[num]++;
}
int tem = count[deck[0]];
for (int num : count) {
if (num > 0) {
tem = gcd(tem, num);
}
}
return tem > 1;
}
/**
* 利用递归求a和b的最大公约数
* @param a
* @param b
* @return
*/
public int gcd(int a, int b) {
return a == 0 ? b : gcd(b%a, a);
}
06 小结
算法专题目前已连续日更超过六个月,算法题文章220+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
最新文章
- NorthWind 数据库整体关系
- C++多线程3
- hdu 1233 还是畅通工程 解题报告
- javascript强制转换详解
- [转载]如何申请淘宝app_key、app_secret、SessionKey?
- 《深入Java虚拟机学习笔记》- 第18章 finally子句
- 利用if else 判断方程有几个根
- Mathlab编程-微积分在Matlab中的解法
- Android(java)学习笔记223:上下文的区分
- C51-keil编译常见错误和警告处理53
- NeHe OpenGL lession 4
- _00024 尼娜抹微笑伊拉克_云计算ClouderaManager以及CHD5.1.0群集部署安装文档V1.0
- thinkphp 3.2 模型的使用示例
- DispatcherTimer和Timer(计时器)
- python模拟shell执行脚本
- 《android开发艺术探索》读书笔记(六)--Drawable
- 利用SSL-Change Cipher Spec传递信息
- P1577 切绳子
- 常被问到的十个 Java 面试题
- Java创建对象的4种方式
热门文章
- [uboot] (第三章)uboot流程——uboot-spl代码流程 后续2018版本分析
- Spring使用@AspectJ开发AOP(零配置文件)
- 前端js之BOM和DOM操作
- 计算机网络(十三),Socket编程实现TCP和UDP
- IE大文件断点续传
- CodeForces 352C Jeff and Rounding
- CodeForces&ndash;471D--MUH and Cube Walls(KMP)
- C++入门经典-例4.3-函数的递归调用之汉诺塔问题
- Miniui 表单验证
- 套接字选项 之 SO_REUSEADDR &;&; SO_REUSEPORT