[Алгоритм Интервью] 914. Группировка карт - Алгоритм Евклида

алгоритм LeetCode

«Это третий день моего участия в первом испытании обновлений 2022 года. Подробную информацию о мероприятии см.:Вызов первого обновления 2022 г."

Подсчитайте количество вхождений каждого числа, а затем выясните, есть ли общий делитель между числами.

—— Горячий комментарий Leetcode по этому вопросу

предисловие

Всем привет, меня зовут Йи, и добро пожаловать на мой канал алгоритмов.

Задавайте только интересные алгоритмические вопросы, пишите только алгоритмы для интервью.

Question

914. Группировка карт

Сложность: легко

Дана колода карт, на каждой из которых написано целое число.

На этом этапе вам нужно выбрать число X, которое позволит нам разделить всю колоду на 1 или более групп по следующим правилам:

В каждом наборе есть X карт. На всех карточках в группе написано одно и то же целое число. Возвращает true, только если ваш необязательный X >= 2.

Пример :

输入：[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);
    }

Также стоит изучить метод подсчета в коде, использовать для подсчета масштаб массива гораздо проще, чем использовать Карту.

короче этот вопросотступить.

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);
    }
}

Наконец

Вроде, вроде, и TMD нравится!

Категории