Java | LeetCode

Задача: 350. Intersection of Two Arrays II Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке. Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

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

import java.util.*;

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> counts = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        
        for (int num : nums1) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        for (int num : nums2) {
            if (counts.getOrDefault(num, 0) > 0) {
                result.add(num);
                counts.put(num, counts.get(num) - 1);
            }
        }
        
        int[] resArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resArray[i] = result.get(i);
        }
        
        return resArray;
    }
}

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

Задача: 1199. Minimum Time to Build Blocks Сложность: hard Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим. Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени. Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split. Выведите минимальное время, необходимое для строительства всех блоков. Изначально есть только один рабочий. Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int block : blocks) {
            pq.offer(block);
        }

        while (pq.size() > 1) {
            int x = pq.poll();
            int y = pq.poll();
            pq.offer(split + y);
        }

        return pq.poll();
    }
}

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

🔥 Скрытые вакансии с удаленной работой для Java разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров. 🔹 Java Jobs | Вакансии 🔸 Все каналы с вакансиями

Олимпиада Высшая проба: промышленное программирование Участвуй в олимпиаде школьников 9-11 класса по промышленному программированию от Яндекса и ВШЭ. Победителям — БВИ или 100 баллов по профильному предмету в топовых вузах России. Регистрируйся до 20 октября! Узнать больше #реклама olymp.hse.ru О рекламодателе

Задача: 759. Employee Free Time Сложность: hard Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину. Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

import java.util.*;

class Interval {
    public int start;
    public int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> intervals = new ArrayList<>();
        for (List<Interval> employee : schedule) {
            intervals.addAll(employee);
        }
        
        intervals.sort((a, b) -> Integer.compare(a.start, b.start));
        
        List<Interval> merged = new ArrayList<>();
        for (Interval interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, interval.end);
            }
        }
        
        List<Interval> freeTime = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++) {
            if (merged.get(i).start > merged.get(i - 1).end) {
                freeTime.add(new Interval(merged.get(i - 1).end, merged.get(i).start));
            }
        }
        
        return freeTime;
    }

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

Встречай смартфон Honor — с выгодой для себя! ✅ Стильный дизайн ✅ Заряд надолго ✅ Качественные фото ✅ Быстрая и плавная работа Выбирай свой Honor по привлекательной цене! Купить #реклама market.yandex.ru О рекламодателе

Задача: 634. Find the Derangement of An Array Сложность: medium В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7. Пример:

Input: n = 3
Output: 2

👨‍💻 Алгоритм: 1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:

public class Solution {
    public int countDerangements(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

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

Квартиры Петербург Новостройка Рассрочка от застройщика Жилой комплекс "Квартал Заречье" Санкт-Петербург. Колпино. 4 девятиэтажных жилых корпуса 8-этажный крытый гараж на 496 парковочных мест В живописном месте у реки Ижора. На первых этажах будут размещены магазины, кофейни, поликлиника и зона коворкинга. Перейти на сайт Финансовые услуги оказывает: ПАО «Сбербанк». Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО «СЗ «ЗАГОРОДНАЯ, 71». #реклама квартал-заречье.рф О рекламодателе

Задача: 55. Jump Game Сложность: medium Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае. Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

👨‍💻Алгоритм: 1⃣Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:

enum Index {
    GOOD,
    BAD,
    UNKNOWN,
}

public class Solution {
    Index[] memo;

    public boolean canJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }

        memo[position] = Index.BAD;
        return false;
    }

    public boolean canJump(int[] nums) {
        memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;
        return canJumpFromPosition(0, nums);
    }
}

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

Запускайте ИИ-продукты и растите как менеджер ⚡ Хотите запускать ИИ-продукты и расти как менеджер, но боитесь ошибиться на старте? Присоединяйтесь к открытому уроку и узнайте, как от бизнес-гипотезы прийти к первым измеримым результатам. 📅 8 октября в 20:00. Преподаватель OTUS разберёт: - Путь ИИ-продукта от идеи до запуска. - Как проверить бизнес-гипотезу до разработки. - Какие метрики успеха выбрать и как избежать типичных ошибок. Вы научитесь оценивать перспективность идей, формулировать гипотезы и критерии успеха, а также запускать пилоты и новые ИИ-функции. ✅ Запишитесь сейчас и станьте менеджером, который умеет запускать ИИ-продукты с нуля! Узнать больше #реклама 16+ otus.ru О рекламодателе

Задача: 1380. Lucky Numbers in a Matrix Сложность: easy Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке. Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце. Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

👨‍💻 Алгоритм: 1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax. 2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j]. 3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers. 😎 Решение:

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        
        List<Integer> rowMin = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int rMin = Integer.MAX_VALUE;
            for (int j = 0; j < M; j++) {
                rMin = Math.min(rMin, matrix[i][j]);
            }
            rowMin.add(rMin);
        }
        
        List<Integer> colMax = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            int cMax = Integer.MIN_VALUE;
            for (int j = 0; j < N; j++) {
                cMax = Math.max(cMax, matrix[j][i]);
            }
            colMax.add(cMax);
        }
        
        List<Integer> luckyNumbers = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == rowMin.get(i) && matrix[i][j] == colMax.get(j)) {
                    luckyNumbers.add(matrix[i][j]);
                }
            }
        }
        
        return luckyNumbers;
    }
}

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

Открытый урок: бизнес-логика в микросервисах Разработка в микросервисах — это не только разбиение на сервисы, но и грамотное распределение логики. 22 октября в 19:00 мск — открытый урок для разработчиков и архитекторов. Узнаете, где должна жить бизнес-логика. Запишитесь! Зарегистрироваться #реклама 16+ otus.ru О рекламодателе

Задача: 991. Broken Calculator Сложность: medium Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно: Умножить число на экране на 2, или Вычесть 1 из числа на экране. Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе. Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

public class Solution {
    public int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

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

Ключевое ИБ-событие года SOC Forum — одно из крупнейших событий в сфере ИБ, которое проходит в рамках Российской недели кибербезопасности. ✅ Здесь встречаются эксперты, представители бизнеса и госструктур, чтобы обсудить ключевые вызовы отрасли. Событие, которое нельзя пропустить. Для тех, кто не может присутствовать лично, будет запущена онлайн-трансляция: 👌 Переключайтесь между залами. 👌 Выбирайте только актуальные для вас выступления. 👌 Задавайте вопросы спикерам в прямом эфире. 👌 Участвуйте в интерактивах. И все это не выходя из дома. Зарегистрируйтесь, и мы напомним о старте трансляции и пришлем ссылку, чтобы вы ничего не пропустили. Узнать больше #реклама 16+ registration.forumsoc.ru О рекламодателе

Задача: 1345. Jump Game IV Сложность: hard Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива. За один шаг вы можете прыгнуть с индекса i на индекс: - i + 1, где: i + 1 < arr.length. - i - 1, где: i - 1 >= 0. - j, где: arr[i] == arr[j] и i != j. Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива. Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени. Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм: 1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов. 2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя. 3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь. 😎 Решение:

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
        }

        List<Integer> curs = new LinkedList<>();
        curs.add(0);
        Set<Integer> visited = new HashSet<>();
        int step = 0;

        while (!curs.isEmpty()) {
            List<Integer> nex = new LinkedList<>();

            for (int node : curs) {
                if (node == n - 1) {
                    return step;
                }

                for (int child : graph.get(arr[node])) {
                    if (!visited.contains(child)) {
                        visited.add(child);
                        nex.add(child);
                    }
                }

                graph.get(arr[node]).clear();

                if (node + 1 < n && !visited.contains(node + 1)) {
                    visited.add(node + 1);
                    nex.add(node + 1);
                }
                if (node - 1 >= 0 && !visited.contains(node - 1)) {
                    visited.add(node - 1);
                    nex.add(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
}

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

Программируешь? Участвуй в олимпиаде Высшая проба Сделай шаг в IT вместе с Яндексом и ВШЭ — прими участие в олимпиаде по промышленному программированию! Победителям — БВИ или 100 баллов по профильному предмету в лучших вузах России. Регистрируйся до 20 октября! Узнать больше #реклама olymp.hse.ru О рекламодателе

Задача: 247. Strobogrammatic Number II Сложность: medium Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм: 1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:

import java.util.*;

class Solution {
    List<List<Character>> reversiblePairs = Arrays.asList(
        Arrays.asList('0', '0'), Arrays.asList('1', '1'), 
        Arrays.asList('6', '9'), Arrays.asList('8', '8'), Arrays.asList('9', '6')
    );
    
    public List<String> generateStroboNumbers(int n, int finalLength) {
        if (n == 0) {
            return Arrays.asList("");
        }
        
        if (n == 1) {
            return Arrays.asList("0", "1", "8");
        }
        
        List<String> prevStroboNums = generateStroboNumbers(n - 2, finalLength);
        List<String> currStroboNums = new ArrayList<>();
        
        for (String prevStroboNum : prevStroboNums) {
            for (List<Character> pair : reversiblePairs) {
                if (pair.get(0) != '0' || n != finalLength) {
                    currStroboNums.add(pair.get(0) + prevStroboNum + pair.get(1));
                }
            }
        }
        
        return currStroboNums;
    }
    
    public List<String> findStrobogrammatic(int n) {
        return generateStroboNumbers(n, n);
    }
}

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

REKONFA: что интересного вас ждёт 15 октября 15 октября встречаемся на REKONFA — большой конференции Яндекс Рекламы. На сцене: — Глеб Доброрадных — о рекламном рынке и эффективности в сложных условиях — Алексей Штоколов — о новых продуктах и технологиях — Лиза Смирнова — о 360°-форматах и новых точках контакта — Александр Пушной — о человеке и ИИ — Александр Умаров — о персональном подходе, который помогает влюблять клиентов в бренд — Яна Чурикова — об актуальных задачах предпринимателей — Татьяна Мужицкая — о целях и энергии — Антон Беляев — об индивидуальности и проектах, которые любят зрители Вне сцены — зона продуктов Яндекс Рекламы, три игры, викторина, зоны Яндекс Ярда и eLama и нетворкинг. 15 октября, Москва, ВТБ Арена и онлайн. Участие бесплатное. Зарегистрироваться #реклама 16+ ya.rekonfa.ru О рекламодателе

Аренда и размещение серверов в дата-центрах Москвы ITSOFT оказывает услуги коммерческого дата-центра в Москве. 👌Аренда физических выделенных серверов (Dedicated Servers) в готовых конфигурациях и в рамках индивидуальных сборок. 👌Colocation и аренда серверных стоек. 👌Предоставление инфраструктурных ИТ-решений для физических лиц и корпоративных клиентов. 👌Предоставление высокоскоростных каналов передачи данных. Узнать цену

Задача: 1339. Maximum Product of Splitted Binary Tree Сложность: medium Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным. Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после. Пример:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

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

class Solution {

    private List<Integer> allSums = new ArrayList<>();

    public int maxProduct(TreeNode root) {
        long totalSum = treeSum(root);
        long best = 0;
        for (long sum : allSums) {
            best = Math.max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }

    private int treeSum(TreeNode subroot) {
        if (subroot == null) return 0;
        int leftSum = treeSum(subroot.left);
        int rightSum = treeSum(subroot.right);
        int totalSum = leftSum + rightSum + subroot.val;
        allSums.add(totalSum);
        return totalSum;
    }
}

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