难度:简略
给定一副牌,每张牌上都写着一个整数。
此时,你须要选定一个数字 X,使咱们能够将整副牌按下述规定分成 1 组或更多组:
每组都有 X 张牌。组内所有的牌上都写着雷同的整数。仅当你可选的 X >= 2 时返回 true。
示例:
输出:[1,2,3,4,4,3,2,1]
输入:true
解释:可行的分组是 [1,1],[2,2],[3,3],[4,4]
复制代码
Solution
通过组内所有的牌上都写着雷同的整数这句话不难发现,是否胜利分组和每次数组呈现的次数无关,那是要每个数字呈现的次数都雷同吗?
不是
只有存在公约数就行。比方 1 有 2 个,2 有 4 个,也是能够的。
所以问题转换为求公约数。是一道数学问题
求公约数置信大家上学时都学过辗转相除法,也叫欧几里得算法,那该如何用程序实现呢?
请肯定要记住这个模板。
// 辗转相除法
private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);
}
复制代码
代码中计数的办法也值得学习,巧用数组小标来计数,比应用 Map 简洁不少。
总之,这题要背下来。
Code
/**
- @author 一条 coding
*/
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
// 计数
int[] counter = new int[10000];
for (int num: deck) {counter[num]++;
}
// 求 gcd
int x = 0;
for(int cnt: counter) {if (cnt > 0) {x = gcd(x, cnt);
if (x == 1) {return false;}
}
}
return x >= 2;
}
// 辗转相除法
private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);
}
}
最初
如果你感觉此文对你有一丁点帮忙,点个赞。或者能够退出我的开发交换群:1025263163 互相学习,咱们会有业余的技术答疑解惑
如果你感觉这篇文章对你有点用的话,麻烦请给咱们的开源我的项目点点 star:http://github.crmeb.net/u/defu 不胜感激!
PHP 学习手册:https://doc.crmeb.com
技术交换论坛:https://q.crmeb.com