“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”
Count the number of occurrences of each number, and then find out whether there is a common divisor between the numbers
— Leetcode
preface
Hello, I’m One, welcome to my algorithm channel.
Only do interesting algorithms, only write algorithms for interviews.
Question
914. Grouping of cards
Difficulty: Easy
Given a deck of cards, each card has an integer written on it.
At this point, you need to select a number X, so that we can divide the whole deck into 1 or more groups according to the following rules:
Each group has X cards. All the cards in the group have the same integer written on them. Return true only if your optional X >= 2.
Example:
,2,3,4,4,3,2,1 input: [1] output: true explanation: feasible grouping is [1, 1], [2], [3], [4]Copy the code
Solution
The success of grouping depends on the number of occurrences of each array. Is the number of occurrences of each number the same?
not
As long as there’s a common divisor. If one has two, and two has four, that’s fine.
So the problem becomes finding common divisor. It’s a math problem
Seeking common divisor I believe you have learned to go to school division, also known as Euclid algorithm, that how to use the program to achieve it?
Be sure to keep this template in mind.
// Toss and turn division
private int gcd (int a, int b) {
return b == 0? a: gcd(b, a % b);
}
Copy the code
Code counting method is also worth learning, skillfully use the array to count, than the use of Map concise many.
Anyway, this one needs to be memorized.
Code
/ * * *@authorA coding * /
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
/ / count
int[] counter = new int[10000];
for (int num: deck) {
counter[num]++;
}
/ / the GCD
int x = 0;
for(int cnt: counter) {
if (cnt > 0) {
x = gcd(x, cnt);
if (x == 1) {
return false; }}}return x >= 2;
}
// Toss and turn division
private int gcd (int a, int b) {
return b == 0? a: gcd(b, a % b); }}Copy the code
The last
Thumbs up, thumbs up, and fucking thumbs up!