Java | LeetCode

Задача: 231. Power of Two Сложность: easy Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false. Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x. Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

👨‍💻 Алгоритм: 1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки. 2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций. 3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x. 😎 Решение:

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) return false;
        long x = n;
        return (x & -x) == x;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Внимание ученики 1-11 класса и их родители! Со 2 марта стартует бесплатная 2-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 925. Long Pressed Name Сложность: easy Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты. Пример:

Input: name = "alex", typed = "aaleex"
Output: true

👨‍💻 Алгоритм: 1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно. 2⃣Пройти по набранной строке: Если символы имени и набранной строки совпадают, сдвинуть оба указателя. Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки. Если символ не совпадает и не является повторением предыдущего символа, вернуть False. После завершения цикла проверить, что все символы имени были обработаны. 3⃣Вернуть True, если все символы имени были обработаны, иначе False. 😎 Решение:

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                i++;
            } else if (j == 0 || typed.charAt(j) != typed.charAt(j - 1)) {
                return false;
            }
            j++;
        }
        return i == name.length();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer Акция до 20 февраля 00:00 Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/

Задача: №27. Remove Element Сложность: easy Дан массив nums и целое число val. Удалите все вхождения val на месте. Порядок элементов можно изменить. Верните количество элементов k, не равных val, таких что nums[0..k-1] содержат нужные значения. Пример:

Input: nums = [3,2,2,3], val = 3 Output: 2 (nums = [2,2,_,_])

👨‍💻 Алгоритм: 1⃣Завести указатель left_most_index = 0, чтобы отслеживать позицию следующего "нужного" элемента. 2⃣Пройти по всем элементам массива: - Если текущий элемент не равен val, поместить его на позицию left_most_index и сдвинуть указатель. 3⃣По завершению вернуть left_most_index, т.е. количество элементов, не равных val. 😎 Решение:

class Solution {
    public int removeElement(int[] nums, int val) {
        int left_most_index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[left_most_index++] = nums[i];
            }
        }
        return left_most_index;        
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 553. Optimal Division Сложность: medium Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой. Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4". Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным. Верните соответствующее выражение, которое имеет максимальное значение в строковом формате. Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

👨‍💻 Алгоритм: 1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе. 2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса. 3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его. 😎 Решение:

class Solution {
    private List<Integer> addStrings(List<Integer> num1, List<Integer> num2) {
        List<Integer> ans = new ArrayList<>();
        int carry = 0;
        int n1 = num1.size();
        int n2 = num2.size();

        for (int i = 0; i < Math.max(n1, n2) + 1; ++i) {
            int digit1 = i < n1 ? num1.get(i) : 0;
            int digit2 = i < n2 ? num2.get(i) : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.add(sum % 10);
        }
        return ans;
    }

    private List<Integer> multiplyOneDigit(String firstNumber, char secondNumberDigit, int numZeros) {
        List<Integer> currentResult = new ArrayList<>(Collections.nCopies(numZeros, 0));
        int carry = 0;

        for (char digit : firstNumber.toCharArray()) {
            int multiplication = (secondNumberDigit - '0') * (digit - '0') + carry;
            carry = multiplication / 10;
            currentResult.add(multiplication % 10);
        }
        if (carry != 0) {
            currentResult.add(carry);
        }
        return currentResult;
    }

    public String multiply(String firstNumber, String secondNumber) {
        if (firstNumber.equals("0") || secondNumber.equals("0")) {
            return "0";
        }

        firstNumber = new StringBuilder(firstNumber).reverse().toString();
        secondNumber = new StringBuilder(secondNumber).reverse().toString();

        List<Integer> ans = new ArrayList<>(Collections.nCopies(firstNumber.length() + secondNumber.length(), 0));

        for (int i = 0; i < secondNumber.length(); ++i) {
            ans = addStrings(multiplyOneDigit(firstNumber, secondNumber.charAt(i), i), ans);
        }

        while (ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }

        StringBuilder answer = new StringBuilder();
        for (int i = ans.size() - 1; i >= 0; --i) {
            answer.append(ans.get(i));
        }

        return answer.toString();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Завтра конец акции на возможность приобрести PRO тариф по цене одного года Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию. Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/

Задача: 460. LFU Cache Сложность: hard Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU). Реализуйте класс LFUCache: LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных. int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1. void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ. Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом. Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа. Функции get и put должны иметь среднюю временную сложность O(1). Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

👨‍💻 Алгоритм: 1⃣insert(int key, int frequency, int value): Вставить пару частота-значение в cache с заданным ключом. Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ. 2⃣int get(int key): Если ключа нет в кеше, вернуть -1. Получить частоту и значение из кеша. Удалить ключ из LinkedHashSet, связанного с частотой. Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies. Вызвать insert(key, frequency + 1, value). Вернуть значение. 3⃣void put(int key, int value): Если capacity <= 0, выйти. Если ключ существует, обновить значение и вызвать get(key). Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша. Установить minf в 1. Вызвать insert(key, 1, value). 😎 Решение:

import java.util.*;

class LFUCache {
    private Map<Integer, LinkedHashSet<int[]>> frequencies;
    private Map<Integer, int[]> cache;
    private int capacity;
    private int minf;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minf = 0;
        this.cache = new HashMap<>();
        this.frequencies = new HashMap<>();
    }

    private void insert(int key, int frequency, int value) {
        frequencies.computeIfAbsent(frequency, k -> new LinkedHashSet<>()).add(new int[]{key, value});
        cache.put(key, new int[]{frequency, value});
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        int[] entry = cache.get(key);
        int frequency = entry[0];
        int value = entry[1];
        frequencies.get(frequency).remove(entry);
        if (frequencies.get(frequency).isEmpty()) {
            frequencies.remove(frequency);
            if (minf == frequency) minf++;
        }
        insert(key, frequency + 1, value);
        return value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (cache.containsKey(key)) {
            cache.get(key)[1] = value;
            get(key);
            return;
        }
        if (cache.size() == capacity) {
            int[] leastUsed = frequencies.get(minf).iterator().next();
            frequencies.get(minf).remove(leastUsed);
            if (frequencies.get(minf).isEmpty()) frequencies.remove(minf);
            cache.remove(leastUsed[0]);
        }
        minf = 1;
        insert(key, 1, value);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Нужны 7 желающих для работы с искусственным интеллектом. Работа из дома. График свободный. Пришло задание — изучили — выполнили — получили свои деньги. Деньги вы получаете в зависимости от сложности задания. Например: За задание могут платить 500-10.000 рублей. 500 рублей — это около 5-30 минут. 10 000 руб. это 5-6 часов. Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д. 💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т. Мы обучим вас сами: — 3 дня уроков по 30 минут — Домашки с проверкой и оплатой бонусами — Платим 10 тыс за каждую выполненную домашку ⚡ Набор заканчивается завтра. Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 418. Sentence Screen Fitting Сложность: medium Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом. Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

👨‍💻 Алгоритм: 1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце. 2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов. 3⃣Если следующая позиция является пробелом, увеличивайте счетчик. Если нет, уменьшайте счетчик, пока не найдете пробел, чтобы избежать разрыва слова. 😎 Решение:

public class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String sentenceStr = String.join(" ", sentence) + " ";
        int length = sentenceStr.length();
        int count = 0;
        
        for (int i = 0; i < rows; i++) {
            count += cols;
            if (sentenceStr.charAt(count % length) == ' ') {
                count++;
            } else {
                while (count > 0 && sentenceStr.charAt((count - 1) % length) != ' ') {
                    count--;
                }
            }
        }
        
        return count / length;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1257. Smallest Common Region Сложность: medium Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион. Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

👨‍💻 Алгоритм: 1⃣Построим дерево регионов, где каждый регион указывает на своего родителя. 2⃣Используя родительскую информацию, найдем путь от каждого региона до корня. 3⃣Найдем последний общий регион в путях двух заданных регионов. 😎 Решение:

import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Раньше — выгоднее. Берите календарь направлений с чек-листами, получайте скидку 5 000 ₽ за раннее бронирование от 60 000 ₽ и бронируйте отпуск, пока лучшие варианты ещё доступны. Забронировать #реклама 16+ special.travel.yandex.ru О рекламодателе

Задача: 1160. Find Words That Can Be Formed by Characters Сложность: easy Вам дан массив строк words и строка chars. Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз). Верните сумму длин всех хороших строк в words. Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

👨‍💻 Алгоритм: 1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0. 2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл. 3⃣Если good = true, добавьте длину слова к ans. Верните ans. 😎 Решение:

class Solution {
    public int countCharacters(String[] words, String chars) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : chars.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        
        int ans = 0;
        for (String word : words) {
            Map<Character, Integer> wordCount = new HashMap<>();
            for (char c : word.toCharArray()) {
                wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
            }
            
            boolean good = true;
            for (Map.Entry<Character, Integer> entry : wordCount.entrySet()) {
                if (counts.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.length();
            }
        }
        
        return ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Книжный магазин Касталия: раздел "Духовный кризис" Однажды наша жизнь становится черна, как крыло ворона; мы не в силах действовать, не в силах собраться, не в силах встать. В конце тоннеля новый тоннель, уходящий ещё глубже, в тёмную тяжесть без надежды. Нам предлагают чудесные методы, патентованные пилюли. Что-то, чтобы изгнать тень из нашей души, словно весь мир здоров и бодр, и лишь мы одни омрачены. Но мир не здоров. Природа опустошена, человечество не видит цели - и наша душа страдает вместе с душой мира. Дело не в тебе: ты почувствовал горечь безумия вокруг. Твоя депрессия - ответ на маниакальность мира. Мы предлагаем не книги, что "поставят вас на ноги", но книги прошедших свой кризис, научившихся смотреть на мир тёмным, ясным, мудрым взором. Тех, кто принял меланхолию как учителя, и обрел в ней особую, негаснущую радость. Посмотреть каталог #реклама 16+ ozon.ru О рекламодателе

Задача: 216. Combination Sum III Сложность: medium Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что: Используются только числа от 1 до 9. Каждое число используется не более одного раза. Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке. Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

👨‍💻 Алгоритм: 1⃣Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2⃣Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3⃣Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:

class Solution {
    protected void backtrack(
        int remain,
        int k,
        LinkedList<Integer> comb,
        int next_start,
        List<List<Integer>> results
    ) {
        if (remain == 0 && comb.size() == k) {
            results.add(new ArrayList<Integer>(comb));
            return;
        } else if (remain < 0 || comb.size() == k) {
            return;
        }

        for (int i = next_start; i < 9; ++i) {
            comb.add(i + 1);
            this.backtrack(remain - i - 1, k, comb, i + 1, results);
            comb.removeLast();
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        LinkedList<Integer> comb = new LinkedList<Integer>();

        this.backtrack(n, k, comb, 0, results);
        return results;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Знаешь, что отличает студента Алабуга Политех? Они не теряют время зря. Они с первого курса получают опыт и работают на проектах. - Учеба + практический опыт в компании мирового уровня - Финансовая самостоятельность - зарплата уже с первого курса! К выпуску у тебя: • диплом гос. образца • официальный трудовой стаж от 2 лет • реальный опыт работы по профессии • карьерные перспективы в одной из лучших ОЭЗ России Подавай заявку и принимай решение о будущем прямо сейчас! Перейти на сайт #реклама 16+ polytech.alabuga.ru О рекламодателе

Пожизненная PRO подписка на easyoffer по цене одного года. Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции. Запланированные новые фичи на ближайшие пол года: 1. Агрегатор вакансий 2. Улучшение резюме, чтобы проходить ATS системы 3. Генерация уникального резюме и сопроводительного письма под вакансию Покупай на https://easyoffer.ru/

Аукцион выделенных серверов! Серверы дешевеют у вас на глазах! Новые лоты каждый день, скидки до -35% на весь срок аренды. Успейте арендовать, пока лот не ушел другому! Получить предложение #реклама 16+ selectel.ru О рекламодателе

Задача: 1338. Reduce Array Size to The Half Сложность: medium Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива. Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива. Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

👨‍💻 Алгоритм: 1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа. 2⃣Отсортировать список подсчета в порядке убывания. 3⃣Удалять числа из массива, начиная с наибольшего количества вхождений, пока не будет удалено не менее половины чисел массива. Вернуть размер множества удаленных чисел. 😎 Решение:

class Solution {
    public int minSetSize(int[] arr) {
        Arrays.sort(arr);
        List<Integer> counts = new ArrayList<>();
        int currentRun = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.add(currentRun);
            currentRun = 1;
        }
        counts.add(currentRun);
        Collections.sort(counts);
        Collections.reverse(counts);
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        for (int count : counts) {
            numbersRemovedFromArr += count;
            setSize += 1;
            if (numbersRemovedFromArr >= arr.length / 2) {
                break;
            }
        }
        return setSize;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Нужны 7 желающих для работы с искусственным интеллектом. Работа из дома. График свободный. Пришло задание — изучили — выполнили — получили свои деньги. Деньги вы получаете в зависимости от сложности задания. Например: За задание могут платить 500-10.000 рублей. В зависимости от сложности. 500 рублей — это около 5-30 минут. 10 000 руб. это 5-6 часов. Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д. 💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т. Мы обучим вас сами: — 3 дня уроков по 30 минут — Домашки с проверкой ⚡ Набор заканчивается завтра. Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ neuromachina.ru О рекламодателе