Java | LeetCode

Бесплатный курс по дизайну: веб, графический и UX/UI Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma! Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Этот курс для тебя, если ты: ✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать; ✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества; ✅ полный новичок и хочешь систему, а не хаос; ✅ хочешь начать зарабатывать удалённо. Зарегистрироваться #реклама 16+ ydaev.ru О рекламодателе

Задача: 1236. Web Crawler Сложность: medium Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы http://leetcode.com/problems и http://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы http://example.org/test и http://example.com/abc не находятся под одним и тем же именем хоста. Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

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

import java.util.*;

public interface HtmlParser {
    List<String> getUrls(String url);
}

public class Solution {
    private String extractHostname(String url) {
        return url.split("/")[2];
    }

    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String hostname = extractHostname(startUrl);
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(startUrl);
        visited.add(startUrl);
        
        while (!queue.isEmpty()) {
            String url = queue.poll();
            for (String nextUrl : htmlParser.getUrls(url)) {
                if (!visited.contains(nextUrl) && extractHostname(nextUrl).equals(hostname)) {
                    visited.add(nextUrl);
                    queue.offer(nextUrl);
                }
            }
        }
        
        return new ArrayList<>(visited);
    }
}

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

⏳ Осталось 20 мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 1287. Element Appearing More Than 25% In Sorted Array Сложность: easy Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число. Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num. 2⃣Установите target = arr.length / 4. 3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение. 😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findSpecialInteger(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        int target = arr.length / 4;
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > target) {
                return num;
            }
        }
        return -1;
    }
}

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

👩‍💻 Java вакансии всех грейдов: удалёнка, реклок, щедрый оффер! Только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения. 👩‍💻 Java 👩‍💻 Python 👩‍💻 Node.js 👣 Go 🤖 ML & DS 👩‍💻 DevOps 👩‍💻 C# 👩‍💻 Frontend 🔎 QA 🖥 SQL 👩‍💻 UX/UI 🖼️ PHP 👩‍💻 Mobile 📋 Analyst 💼 1C 👨‍✈️ CyberSec 👩‍💻 IT HR Подпишись чтобы не упустить свой шанс получить лучший оффер!

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary Сложность: easy Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника. Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты. Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0. 2⃣Итерация по зарплатам: Для каждой зарплаты добавить её к переменной sum. Обновить переменную minSalary, если текущая зарплата меньше её значения. Обновить переменную maxSalary, если текущая зарплата больше её значения. 3⃣Вычисление среднего значения: Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности. 😎 Решение:

class Solution {
    public double average(int[] salaries) {
        int minSalary = Integer.MAX_VALUE;
        int maxSalary = Integer.MIN_VALUE;
        int sum = 0;

        for (int salary : salaries) {
            sum += salary;
            minSalary = Math.min(minSalary, salary);
            maxSalary = Math.max(maxSalary, salary);
        }

        return (double)(sum - minSalary - maxSalary) / (double)(salaries.length - 2);
    }
}

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

Задача: 909. Snakes and Ladders Сложность: medium Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1. Пример:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4

👨‍💻 Алгоритм: 1⃣Представить доску в виде одномерного массива, чтобы легко определить позицию следующего хода. 2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2. В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют. 3⃣Если достижение клетки n2 невозможно, вернуть -1. 😎 Решение:

import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        
        int[] getPos(int x) {
            int quot = (x - 1) / n;
            int rem = (x - 1) % n;
            int row = n - 1 - quot;
            int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
            return new int[]{row, col};
        }
        
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0});
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int pos = curr[0];
            int steps = curr[1];
            for (int i = 1; i <= 6; i++) {
                int nextPos = pos + i;
                if (nextPos > n * n) continue;
                int[] rc = getPos(nextPos);
                int r = rc[0], c = rc[1];
                if (board[r][c] != -1) {
                    nextPos = board[r][c];
                }
                if (nextPos == n * n) {
                    return steps + 1;
                }
                if (!visited.contains(nextPos)) {
                    visited.add(nextPos);
                    queue.offer(new int[]{nextPos, steps + 1});
                }
            }
        }
        return -1;
    }
}

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 852. Peak Index in a Mountain Array Сложность: medium Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются. Верните индекс пикового элемента. Ваша задача — решить это с временной сложностью O(log(n)). Пример:

Input: arr = [0,1,0]

Output: 1

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную i и инициализируйте её значением 0. 2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1. 3⃣В противном случае, если arr[i] > arr[i + 1], верните i. 😎 Решение:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int i = 0;
        while (arr[i] < arr[i + 1]) {
            i++;
        }
        return i;
    }
}

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

⏳ 90 акционных мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 1533. Find the Index of the Large Integer Сложность: medium У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции: int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает: 1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y]. 0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y]. -1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y]. int length(): Возвращает размер массива. Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время. Верните индекс массива arr, который содержит наибольший элемент. Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

👨‍💻 Алгоритм: 1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length). 2⃣Пока length > 1: — Обновите length до length / 2. — Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1). — Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае. — Если cmp равно -1, увеличьте left на length. — Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2. 3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ. 😎 Решение:

class Solution {
    public int getIndex(ArrayReader reader) {
        int left = 0;
        int length = reader.length();
        while (length > 1) {
            length /= 2;
            int cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1);
            if (cmp == 0) {
                return left + 2 * length;
            }
            if (cmp < 0) {
                left += length;
            }
        }
        return left;
    }
}

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

Открыта регистрация на конференцию Деловая программа конференции в первый день выставки: Доклад: «Интенсив по медицинскому праву для специалистов косметологии» от Чернышук Николая Владимировича, практикующего юриста в сфере медицинского права. Доклад: «Маркетинг в косметологии 2025–2026. Личный бренд врача» от Мильковской Алины Александровны, маркетолога-стратега, контент-мейкера. В остальные дни выставки ждём вас на нашем стенде! Зарегистрироваться #реклама mrqz.me О рекламодателе

Задача: 1268. Search Suggestions System Сложность: medium Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord. Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        String prefix = "";
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            List<String> suggestions = new ArrayList<>();
            for (String product : products) {
                if (product.startsWith(prefix)) {
                    suggestions.add(product);
                    if (suggestions.size() == 3) break;
                }
            }
            result.add(suggestions);
        }
        return result;
    }
}

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

Задача: 1234. Replace the Substring for Balanced String Сложность: medium Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0. Пример:

Input: s = "QWER"
Output: 0

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

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int balancedString(String s) {
        int n = s.length();
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        int target = n / 4;

        boolean isBalanced() {
            return count.getOrDefault('Q', 0) <= target &&
                   count.getOrDefault('W', 0) <= target &&
                   count.getOrDefault('E', 0) <= target &&
                   count.getOrDefault('R', 0) <= target;
        }

        if (isBalanced()) return 0;

        int minLength = n;
        int left = 0;

        for (int right = 0; right < n; right++) {
            count.put(s.charAt(right), count.get(s.charAt(right)) - 1);
            while (isBalanced()) {
                minLength = Math.min(minLength, right - left + 1);
                count.put(s.charAt(left), count.get(s.charAt(left)) + 1);
                left++;
            }
        }

        return minLength;
    }
}

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

Задача: 202. Happy Number Сложность: easy Напишите алгоритм для определения, является ли число n счастливым. Счастливое число определяется следующим образом: 1. Начинаем с любого положительного числа и заменяем его на сумму квадратов его цифр. 2. Повторяем процесс до тех пор, пока число не станет равным 1 (где оно останется), или пока оно не зациклится бесконечно, не достигая 1. 3. Числа, для которых этот процесс заканчивается на 1, являются счастливыми. 4. Верните true, если n является счастливым числом, и false, если нет. Пример:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

👨‍💻 Алгоритм: 1⃣Определите следующее число для заданного числа n. Это можно сделать, используя операции деления и взятия по модулю, чтобы последовательно извлекать цифры из числа, пока они не закончатся, затем возводить каждую извлечённую цифру в квадрат и суммировать их. Внимательно посмотрите на код для этого, "извлечение цифр по одной" — полезная техника, которую вы будете использовать для решения множества различных задач. 2⃣Следите за цепочкой чисел и обнаруживайте, если мы вошли в цикл. Это можно сделать с помощью HashSet. Каждый раз, когда мы генерируем следующее число в цепочке, мы проверяем, есть ли оно уже в нашем HashSet. Если его нет в HashSet, мы добавляем его. Если оно уже в HashSet, это означает, что мы находимся в цикле и должны вернуть false. 3⃣Мы используем HashSet, а не Vector, List или Array, потому что мы многократно проверяем, находятся ли числа в нём. Проверка, находится ли число в HashSet, занимает время O(1), тогда как для других структур данных это занимает время O(n). Выбор правильных структур данных — важная часть решения этих задач. 😎 Решение:

class Solution {
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

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

Задача: 857. Minimum Cost to Hire K Workers Сложность: hard Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника. Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами: Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение. В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше. Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты. Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию. 2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality. 3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost. 😎 Решение:

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double totalCost = Double.MAX_VALUE;
        double currentTotalQuality = 0;
        List<Pair<Double, Integer>> wageToQualityRatio = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            wageToQualityRatio.add(new Pair<>((double) wage[i] / quality[i], quality[i]));
        }

        wageToQualityRatio.sort(Comparator.comparingDouble(Pair::getKey));
        PriorityQueue<Integer> workers = new PriorityQueue<>(Collections.reverseOrder());

        for (Pair<Double, Integer> pair : wageToQualityRatio) {
            workers.add(pair.getValue());
            currentTotalQuality += pair.getValue();

            if (workers.size() > k) {
                currentTotalQuality -= workers.poll();
            }

            if (workers.size() == k) {
                totalCost = Math.min(totalCost, currentTotalQuality * pair.getKey());
            }
        }

        return totalCost;
    }
}

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 823. Binary Trees With Factors Сложность: medium Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1. Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов. Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7. Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

👨‍💻 Алгоритм: 1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование. 2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k. 3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением. 😎 Решение:

class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        int MOD = 1_000_000_007;
        Arrays.sort(A);
        long[] dp = new long[A.length];
        Arrays.fill(dp, 1);
        Map<Integer, Integer> index = new HashMap<>();
        
        for (int i = 0; i < A.length; i++) {
            index.put(A[i], i);
        }
        
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        for (long x : dp) {
            result = (result + x) % MOD;
        }
        return (int) result;
    }

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

Задача: 404. Sum of Left Leaves Сложность: easy Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, false);
    }
    
    private int dfs(TreeNode node, boolean isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return dfs(node.left, true) + dfs(node.right, false);
    }
}

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

CRM, которая помогает управлять отделом продаж Что делает Битрикс24 CRM: – ставит задачи менеджерам автоматически – интегрируется с 1С и онлайн-кассами – показывает, где теряются деньги – возвращает клиентов и ищет повторные продажи – помогает руководителю контролировать процессы. Битрикс24 CRM работает на результат. Регистрируйтесь бесплатно Зарегистрироваться #реклама 16+ bitrix24.ru О рекламодателе