X of a Kind in a Deck of Cards LT914
2024-09-25 15:53:44
In a deck of cards, each card has an integer written on it.
Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:
- Each group has exactly
Xcards. - All the cards in each group have the same integer.
Example 1:
Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]
Example 2:
Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.
Example 3:
Input: [1]
Output: false
Explanation: No possible partition.
Example 4:
Input: [1,1]
Output: true
Explanation: Possible partition [1,1]
Example 5:
Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]
Note:
1 <= deck.length <= 100000 <= deck[i] < 10000
Idea 1. count the occurences of each number in the deck and check if the greatest common divisor of all counts pair > 1
Time complexity: O(Nlog^2N), where N is the number of cards. gcd operation is O(log^2C) if there are C cards for number i. need to read further about it.
Space complexity: O(N)
class Solution {
int gcd(int a, int b) {
while(b != 0) {
int temp = b;
b = a%b;
a = temp;
}
return a;
}
public boolean hasGroupsSizeX(int[] deck) {
if(deck.length < 2) {
return false;
}
Map<Integer, Integer> intCnt = new HashMap<>();
for(int num: deck) {
intCnt.put(num, intCnt.getOrDefault(num, 0) + 1);
}
int preVal = -1;
for(int val: intCnt.values()) {
if(val == 1) {
return false;
}
if(preVal == -1) {
preVal = val;
}
else {
preVal = gcd(preVal, val);
if(preVal == 1) {
return false;
}
}
}
return preVal >= 2;
}
}
网上看到的超级简洁，自己的差好远，还有很长的路啊
class Solution {
int gcd(int a, int b) {
while(b != 0) {
int temp = b;
b = a%b;
a = temp;
}
return a;
}
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> intCnt = new HashMap<>();
for(int num: deck) {
intCnt.put(num, intCnt.getOrDefault(num, 0) + 1);
}
int res = 0;
for(int val: intCnt.values()) {
res = gcd(val, res);
}
return res >= 2;
}
}
最新文章
- Salesforce的sharing Rule 不支持Lookup型字段解决方案
- MyEclipse开发Java Web项目步骤
- 黑盒测试与白盒测试(Black box Testing)
- Ubuntu查看系统的信息
- struts.xml中可以使用el表达式和ognl表达式
- 【服务器环境搭建-Centos】系统分区 待续
- bzoj3798: 特殊的质数
- Android UI设计系统---LayoutParams[转]
- 【Jenkins】linux下Jenkins集成ant进行编译并发送结果
- 【vijos1642】班长的任务
- Away3d 基础 1 ---对一个简单类的解释
- 最终结算“Git Windowsclient保存username与password”问题
- android：由URL载入中ImageView
- 《JS权威指南学习总结--6.1原型》
- 文件上传----FTP部署
- DateTime.Now的一些用法
- kaptcha 验证码组件使用
- FTP publisher plugin插件
- 20175320 2018-2019-2 《Java程序设计》第8周学习总结
- Linux 环境下安装Redis的步骤