Java | LeetCode

Задача: 994. Rotting Oranges Сложность: medium Дан m x n сетка, где каждая ячейка может иметь одно из трех значений: 0, представляющее пустую ячейку, 1, представляющее свежий апельсин, 2, представляющее гнилой апельсин. Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым. Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1. Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0;
        
        int minutes = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                for (int[] dir : directions) {
                    int ni = point[0] + dir[0], nj = point[1] + dir[1];
                    if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2;
                        freshCount--;
                        queue.offer(new int[]{ni, nj});
                    }
                }
            }
            if (!queue.isEmpty()) {
                minutes++;
            }
        }
        
        return freshCount == 0 ? minutes : -1;
    }
}

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 1244. Design A Leaderboard Сложность: medium Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста. Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

👨‍💻 Алгоритм: 1⃣addScore(playerId, score): Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение. Если игрок не существует, добавляем его с заданным счетом. 2⃣top(K): Сортируем игроков по их счету в порядке убывания. Возвращаем сумму очков K лучших игроков. 3⃣reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

import java.util.*;

public class Leaderboard {
    private Map<Integer, Integer> scores;

    public Leaderboard() {
        scores = new HashMap<>();
    }

    public void addScore(int playerId, int score) {
        scores.put(playerId, scores.getOrDefault(playerId, 0) + score);
    }

    public int top(int K) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(scores.values());
        int sum = 0;
        for (int i = 0; i < K && !maxHeap.isEmpty(); i++) {
            sum += maxHeap.poll();
        }
        return sum;
    }

    public void reset(int playerId) {
        scores.put(playerId, 0);
    }
}

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

Задача: 90. Subsets II Сложность: medium Дан массив целых чисел nums, который может содержать повторяющиеся элементы. Верните все возможные подмножества (степенной набор). Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке. Пример:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

👨‍💻 Алгоритм: 1⃣Отсортировать массив numsтак, чтобы элементы шли подряд были одинаковыми — это поможет избежать дубликатов. 2⃣Сгенерировать все возможные подмножества с помощью битовой маски от 0до 2^n - 1, где n— длина массива. 3⃣Для каждого подмножества формируем строковый «хеш» и сохраняем уже добавленные подмножества в Set, чтобы не создавать дубликаты. 😎 Решение:

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList();
        int n = nums.length;
        Arrays.sort(nums);
        int maxNumberOfSubsets = (int) Math.pow(2, n);
        Set<String> seen = new HashSet<>();

        for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
            List<Integer> currentSubset = new ArrayList();
            StringBuilder hashcode = new StringBuilder();
            for (int j = 0; j < n; j++) {
                int mask = 1 << j;
                int isSet = mask & subsetIndex;
                if (isSet != 0) {
                    currentSubset.add(nums[j]);
                    hashcode.append(nums[j]).append(",");
                }
            }
            if (!seen.contains(hashcode.toString())) {
                seen.add(hashcode.toString());
                subsets.add(currentSubset);
            }
        }

        return subsets;
    }
}

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

Курс Аналитика данных с нуля. Теперь со скидкой 50%! 🎓Получите новую профессию и постройте успешную карьеру в IT-сфере с нашим курсом Узнать больше #реклама 16+ karpov.courses О рекламодателе

Задача: 1197. Minimum Knight Moves Сложность: medium На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0]. У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении. Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует. Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

class Solution {
    public int minKnightMoves(int x, int y) {
        int[][] offsets = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
                {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

        Deque<int[]> originQueue = new LinkedList<>();
        originQueue.addLast(new int[]{0, 0, 0});
        Map<String, Integer> originDistance = new HashMap<>();
        originDistance.put("0,0", 0);

        Deque<int[]> targetQueue = new LinkedList<>();
        targetQueue.addLast(new int[]{x, y, 0});
        Map<String, Integer> targetDistance = new HashMap<>();
        targetDistance.put(x + "," + y, 0);

        while (true) {
            int[] origin = originQueue.removeFirst();
            String originXY = origin[0] + "," + origin[1];
            if (targetDistance.containsKey(originXY)) {
                return origin[2] + targetDistance.get(originXY);
            }

            int[] target = targetQueue.removeFirst();
            String targetXY = target[0] + "," + target[1];
            if (originDistance.containsKey(targetXY)) {
                return target[2] + originDistance.get(targetXY);
            }

            for (int[] offset : offsets) {
                int[] nextOrigin = new int[]{origin[0] + offset[0], origin[1] + offset[1]};
                String nextOriginXY = nextOrigin[0] + "," + nextOrigin[1];
                if (!originDistance.containsKey(nextOriginXY)) {
                    originQueue.addLast(new int[]{nextOrigin[0], nextOrigin[1], origin[2] + 1});
                    originDistance.put(nextOriginXY, origin[2] + 1);
                }

                int[] nextTarget = new int[]{target[0] + offset[0], target[1] + offset[1]};
                String nextTargetXY = nextTarget[0] + "," + nextTarget[1];
                if (!targetDistance.containsKey(nextTargetXY)) {
                    targetQueue.addLast(new int[]{nextTarget[0], nextTarget[1], target[2] + 1});
                    targetDistance.put(nextTargetXY, target[2] + 1);
                }
            }
        }
    }
}

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Узнать больше #реклама 16+ practicum.yandex.ru О рекламодателе

📅 Осталось 7 дней до конца краудфандинга Мы на финишной прямой! Если ты планировал присоединиться, но ещё не успел, сейчас идеальный момент. Вознаграждения за поддержку: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать easyoffer 2.0 Не откладывай на последний момент 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Задача: 1250. Check If It Is a Good Array Сложность: hard Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False. Пример:

Input: nums = [12,5,7,23]
Output: true

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

import java.util.Arrays;

public class Solution {
    public boolean isGoodArray(int[] nums) {
        int gcd = nums[0];
        for (int num : nums) {
            gcd = gcd(gcd, num);
            if (gcd == 1) return true;
        }
        return gcd == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

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

Онлайн кружок Олимпиадной математики для детей "Школа ученых" приглашает дошколят и школьников 1-9 кл. в онлайн кружок Олимпиадной математики. Занятия проводятся по авторской методике в группах или индивидуально. Основная цель - научить думать. Берем всех, вне зависимости от уровня. Работаем со всеми. А самых ярких результатов добиваемся как раз с изначально "слабыми" учениками. Мы также готовим к Олимпиадам. Сейчас без них - никуда. Попасть на бюджет только по баллам ЕГЭ - сложно. Нужны победы в турнирах. Ну и, наконец, мы помогаем поступить в профильные школы и классы. Основные принципы нашей методики: задания подбираются под уровень ученика; задачи чередуются с развивающими упражнениями; объяснение материала - в процессе решения. Есть бесплатное пробное занятие. Записывайтесь! Всем, кто стартует в апреле - скидка 5%. Узнать больше #реклама 16+ igoto.su О рекламодателе

Задача: 1802. Maximum Value at a Given Index in a Bounded Array Сложность: medium Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям: - nums.length == n - nums[i] является положительным целым числом, где 0 <= i < n. - abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1. - Сумма всех элементов массива nums не превышает maxSum. - nums[index] максимально возможен. Верните значение nums[index] в построенном массиве. Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае. Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

👨‍💻 Алгоритм: 1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value. 2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1. 3⃣Верните left по завершении бинарного поиска. 😎 Решение:

class Solution {
    private long getSum(int index, int value, int n) {
        long count = 0;
        if (value > index) {
            count += (long)(value + value - index) * (index + 1) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + index - value + 1;
        }
        if (value >= n - index) {
            count += (long)(value + value - n + 1 + index) * (n - index) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + n - index - value;
        }
        return count - value;
    }

    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (getSum(index, mid, n) <= maxSum) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

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

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 1214. Two Sum BSTs Сложность: medium Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target. Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

👨‍💻 Алгоритм: 1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2. 2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2. 3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false. 😎 Решение:

class Solution {
    private void dfs(TreeNode currNode, Set<Integer> nodeSet) {
        if (currNode == null) {
            return;
        }
        dfs(currNode.left, nodeSet);
        nodeSet.add(currNode.val);
        dfs(currNode.right, nodeSet);
    }
    
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        Set<Integer> nodeSet1 = new HashSet<>();
        Set<Integer> nodeSet2 = new HashSet<>();
        dfs(root1, nodeSet1);
        dfs(root2, nodeSet2);

        for (int value1 : nodeSet1) {
            if (nodeSet2.contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }   
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 969. Pancake Sorting Сложность: medium Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов. При одном перевороте блина мы выполняем следующие шаги: Выбираем целое число k, где 1 <= k <= arr.length. Переворачиваем подмассив arr[0...k-1] (индексация с 0). Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3. Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным. Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

👨‍💻 Алгоритм: 1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0 ] (в Python). 2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего. 3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте. 😎 Решение:

class Solution {
    public List<Integer> pancakeSort(int[] A) {
        List<Integer> ans = new ArrayList<>();

        for (int valueToSort = A.length; valueToSort > 0; valueToSort--) {
            int index = find(A, valueToSort);
            if (index == valueToSort - 1) continue;
            if (index != 0) {
                ans.add(index + 1);
                flip(A, index + 1);
            }
            ans.add(valueToSort);
            flip(A, valueToSort);
        }

        return ans;
    }

    protected void flip(int[] sublist, int k) {
        int i = 0;
        while (i < k / 2) {
            int temp = sublist[i];
            sublist[i] = sublist[k - i - 1];
            sublist[k - i - 1] = temp;
            i++;
        }
    }

    protected int find(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

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

⚡ Когда говорят, что Java слишком простой язык, на сцену выходит канал Java Learning Здесь легко научиться: ▪️ Разрабатывать высоконагруженные серверные приложения ▪️ Управлять сложными базами данных ▪️ Организовывать эффективную многопоточную обработку данных ▪️ Проходить технические собеседования в ведущие IT-компании Самый необычный канал про Java, подписывайся – @Java_per_month

Суперблендер BORK заменит кухонный арсенал Профессиональный стационарный блендер с мощностью 2400 Вт справится с измельчением овощей, ягод, а также орехов и льда. Вы легко и быстро приготовите смузи, суп-пюре и вкусные десерты для всей семьи. Модель объединила сразу 2 решения: стационарную чашу объемом 2 л и съемный стакан объемом 0,7 л, который удобно брать с собой. 12 скоростей позволяют смешивать продукты любой консистенции. 5 автопрограмм помогут быстро приготовить смузи, замороженные десерты, крем-суп и ледяную крошку. Блендер оснащен умной системой охлаждения: она активируется только при повышении температуры, а не работает постоянно. Приобретайте в бутиках, на сайте и в приложении BORK. Заказать #реклама 16+ bork.ru О рекламодателе

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1017. Convert to Base -2 Сложность: medium Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0". Пример:

Input: n = 2
Output: "110"

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

public class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder res = new StringBuilder();
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res.insert(0, remainder);
        }
        return res.toString();
    }
}

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

Задача: 826. Most Profit Assigning Work Сложность: medium У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где: difficulty[i] и profit[i] — сложность и прибыль i-го задания, worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]). Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз. Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0. Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям. Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

👨‍💻 Алгоритм: 1⃣Создание и сортировка профиля работы Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности. 2⃣Обновление максимальной прибыли для каждой сложности Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли. 3⃣Вычисление максимальной прибыли Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее. 😎 Решение:

class Solution {

    public int maxProfitAssignment(
        int[] difficulty,
        int[] profit,
        int[] worker
    ) {
        List<int[]> jobProfile = new ArrayList<>();
        jobProfile.add(new int[] { 0, 0 });
        for (int i = 0; i < difficulty.length; i++) {
            jobProfile.add(new int[] { difficulty[i], profit[i] });
        }

        Collections.sort(jobProfile, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < jobProfile.size() - 1; i++) {
            jobProfile.get(i + 1)[1] = Math.max(
                jobProfile.get(i)[1],
                jobProfile.get(i + 1)[1]
            );
        }

        int netProfit = 0;
        for (int i = 0; i < worker.length; i++) {
            int ability = worker[i];

            int l = 0, r = jobProfile.size() - 1, jobProfit = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (jobProfile.get(mid)[0] <= ability) {
                    jobProfit = Math.max(jobProfit, jobProfile.get(mid)[1]);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            netProfit += jobProfit;
        }
        return netProfit;
    }

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