✅ Решение задачи 373

Time: O(k log(n))
Space: O(n + k)

💡 Идея
🟦Если перебирать все возможные пары, мы получили бы сложность O(n²), поэтому воспользуемся тем фактом, что массивы отсортированы и будем генерировать только те пары, которые потенциально могут входить в k наименьших, складывая их в PriorityQueue в формате массива {sum, nums1_i, nums2_i}

🟦Сначала добавляем в очередь только пары, состоящие из каждого элемента nums1 и первого элемента nums2, таким образом формируя всех начальных кандидатов на минимальные пары

🟦В цикле, пока k > 0:
➖извлекаем пару с наименьшей суммой и добавляем в результат

➖добавляем следующую пару с тем же элементом из nums1, но со следующим элементом из nums2:
▫если nums2[j] уже дал минимальную пару, то следующий кандидат — это nums2[j+1]

➖уменьшаем k

🟦Таким образом, очередь динамически поддерживает только те пары, которые могут быть среди k наименьших, что дает эффективный алгоритм

👩‍💻 Java Algo | #solution373

🟡Medium
1834. Single-Threaded CPU

Company: 🔍📱📱

📝Дано n задач tasks, где tasks[i] = {enqueueTime_i, processingTime_i} — время поступления задачи enqueueTime и время ее обработки processingTime.

У вас есть однопоточный процессор, который может обрабатывать максимум одну задачу одновременно и действует следующим образом:

➖если ЦП простаивает и есть доступные задачи, он выберет задачу с наименьшим временем обработки. Если несколько задач имеют одинаковое наименьшее время обработки, он выберет задачу с наименьшим индексом
➖после запуска задачи ЦП будет обрабатывать ее всю без остановки
➖ЦП может завершить задачу, а затем мгновенно начать новую

Верните порядок, в котором процессор будет обрабатывать задачи

Объяснение для примера 1:

- В момент времени = 1 задача 0 доступна для обработки. Доступные задачи = {0}.

- Также в момент времени = 1 простаивающий ЦП начинает обработку задачи 0. Доступные задачи = {}.

- В момент времени = 2 задача 1 доступна для обработки. Доступные задачи = {1}.

- В момент времени = 3 задача 2 доступна для обработки. Доступные задачи = {1, 2}.

- Также в момент времени = 3 ЦП завершает задачу 0 и начинает обработку задачи 2, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 4 задача 3 доступна для обработки. Доступные задачи = {1, 3}.

- В момент времени = 5 ЦП завершает задачу 2 и начинает обработку задачи 3, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 6 ЦП завершает задачу 3 и начинает обработку задачи 1. Доступные задачи = {}.

- В момент времени = 10 ЦП завершает задачу 1 и переходит в режим ожидания.

💡: отсортируйте массив по времени поступления с сохранением индексов и используйте очередь для выбора доступной задачи с наименьшим временем выполнения

#leetcode1834 | #medium #priorityqueue

✅ Решение задачи 1834

Time: O(n log(n))
Space: O(n)

💡 Идея
🟦В начале создадим новый массив sorted, в который скопируем все задачи, добавляя к каждой её исходный индекс, а затем отсортируем его по времени поступления задачи

🟦Также создадим PriorityQueue, в которой будем хранить задачи, упорядоченные по времени выполнения и исходному индексу в случае равенства processingTime

🟦Далее выполняем основной цикл, пока все задачи не будут обработаны или пока в очереди есть задачи:
➖если очередь пуста и текущий момент времени меньше времени поступления следующей задачи, «перематываем» время вперёд на момент поступления этой задачи

➖затем, пока есть задачи, доступные к текущему моменту времени, добавляем их в очередь

➖после этого извлекаем задачу с наименьшим временем выполнения и текущее время увеличиваем на ее processingTime, а ее индекс записывается в массив результата

🟦Таким образом, алгоритм симулирует процесс выполнения задач, учитывая и поступление, и приоритет выполнения

👩‍💻 Java Algo | #solution1834

🔴Hard
632. Smallest Range Covering Elements from K Lists

Company: 📕🏢✴️

📝Дано k списков целых чисел, отсортированных в неубывающем порядке. Найдите наименьший диапазон, включающий хотя бы одно число каждого из k списков.

Диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c если b - a == d - c

💡: используя очередь, передвигайте указатель в списке с наименьшим текущим элементом, чтобы пытаться сузить диапазон

#leetcode632 | #hard #priorityqueue

✅ Решение задачи 632

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Для нахождения самого узкого диапазона используем PriorityQueue, в которую изначально помещаем первый элемент каждого списка вместе с индексом списка и позицией внутри него. Также сохраняем максимальное значение среди этих первых элементов, чтобы можно было отслеживать текущий диапазон

🟦Далее запускаем основной цикл, пока в очереди есть по одному элементу из каждого списка, то есть пока все списки представлены:
➖извлекаем минимальный элемент из очереди, то есть элемент, который определяет левую границу нового диапазона

➖затем обновляем текущий диапазон, если новый оказался уже

➖далее пытаемся улучшить результат и проверяем, есть ли следующий элемент в списке, из которого мы достали текущий минимальный

➖если есть — добавляем его в очередь и параллельно сравниваем с максимальным

🟦В результате эффективно получаем самый узкий диапазон, который покрывает хотя бы один элемент из каждого списка

👩‍💻 Java Algo | #solution632

🔴Hard
2402. Meeting Rooms III

Company: 📱🚖📕

📝Дано n комнат, пронумерованных от 0 до n - 1.

Вам дан массив meetings, где meetings[i] = [start_i, end_i) — время встречи в течение полузакрытого интервала. Все значения start уникальны.

Встречи распределяются по комнатам следующим образом:

➖каждая встреча будет проходить в неиспользуемой комнате с наименьшим номером
➖если свободных комнат нет, встреча будет отложена до тех пор, пока не освободится комната
➖если комната становится неиспользуемой, ее следует отдать отложенной встрече, начинавшейся раньше

Верните номер комнаты, в которой было больше всего встреч. Если ответов несколько, верните комнату с наименьшим номером

Объяснение для примеров:

Пример 1.
- В момент времени 0 обе комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 1 не используется только комната 1. Вторая встреча начинается в комнате 1.
- В момент времени 2 используются обе комнаты. Третья встреча задерживается.
- В момент времени 3 используются обе комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 1. Третья встреча начинается в комнате 1 на период времени [5,10).
- В момент времени 10 заканчиваются встречи в обеих комнатах. Четвертая встреча начинается в комнате 0 на период времени [10,11).
В обеих комнатах 0 и 1 было проведено по 2 встречи, поэтому мы возвращаем 0.

Пример 2.
- В момент времени 1 все три комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 2 комнаты 1 и 2 не используются. Вторая встреча начинается в комнате 1.
- В момент времени 3 не используется только комната 2. Третья встреча начинается в комнате 2.
- В момент времени 4 используются все три комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 2. Четвертая встреча начинается в комнате 2 на период времени [5,10).
- В момент времени 6 используются все три комнаты. Пятая встреча задерживается.
- В момент времени 10 заканчиваются встречи в комнатах 1 и 2. Пятая встреча начинается в комнате 1 на период времени [10,12).
В комнате 0 была проведена 1 встреча, а в комнатах 1 и 2 — по 2, поэтому мы возвращаем 1.

💡: используйте две очереди: первая отслеживает номера свободных комнат, вторая — время окончания проходящих встреч и комнату, в которой они находятся

#leetcode2402 | #hard #priorityqueue

✅ Решение задачи 2402

Time: O(m log(m))
Space: O(m + n)

💡 Идея
🟦Сначала сортируем meetings по времени начала, чтобы обрабатывать события в хронологическом порядке

🟦Далее используем две приоритетные очереди: free для хранения свободных комнат по их индексам и used для занятых комнат с информацией о времени освобождения и номере комнаты

🟦Проходим по всем встречам и для каждой:
➖сначала освобождаем комнаты, в которых встречи уже закончились: текущее время больше или равно времени окончания встречи в очереди used

➖если есть свободные комнаты, встреча назначается в первую свободную по индексу (free.peek())

➖если свободных комнат нет — время начала текущей встречи переносится на ближайшее время освобождения одной из комнат (used.peek())

➖в массиве freq подсчитываем частоту использования комнат, увеличивая счетчик по индексу комнаты

🟦После обработки всех встреч с помощью функции getMaxFreq проходим по массиву freq и находим комнату, которая использовалась чаще всего:

private int getMaxfreq(int[] freq) {
int max = 0;
int room = -1;

for (int i = 0; i < freq.length; i++) {
if (freq[i] > max) {
max = freq[i];
room = i;
}
}

return room;
}

👩‍💻 Java Algo | #solution2402

🔴Hard
295. Find Median from Data Stream

Company: 📕📱🚖

📝Реализуйте класс MedianFinder:

▫MedianFinder() инициализирует MedianFinder объект
▫void addNum(int num) добавляет целое число num из потока данных в структуру данных
▫double findMedian() возвращает медиану всех элементов на данный момент

Медиана — это среднее значение в упорядоченном целочисленном списке. Если размер списка четный, медиана — это среднее значение двух средних значений

💡: используйте две очереди — для левой и правой половины потока чисел

#leetcode295 | #hard #priorityqueue

✅ Решение задачи 295

Time: O(log(n))
Space: O(n)

💡 Идея
🟦Для реализации используем две приоритетные очереди: left — содержащую левую половину чисел с приоритетом на большие значения, right — содержащую правую половину чисел с приоритетом на меньшие значения

🟦Благодаря такому разделению медиана всегда будет находиться либо на вершине одной из очередей, либо как среднее значение между вершинами двух очередей

🟦При добавлении нового числа всегда сначала кладем его в left, затем выполняем корректировку:
➖если верхнее значение left больше наименьшего значения right или если разница в размерах куч превышает 1 — элементы перемещаются между очередями для поддержания баланса

🟦Медиану определяем в зависимости от размера очередей:
➖если обе кучи равны по размеру, медиана — это среднее значение двух центральных элементов (вершин очередей)
➖если одна очередь больше другой по размеру, медиана — это вершина большей очереди

🟦Благодаря сбалансированной структуре, поиск медианы занимает O(1), а добавление числа — O(log n), что делает алгоритм эффективным для больших потоков данных

👩‍💻 Java Algo | #solution295

➡ Стартуем тему Backtracking

Представь, что ты оказался в огромном замке, полном дверей, коридоров и развилок. Твоя цель — найти комнату с сокровищем. У тебя с собой блокнот и карандаш, но нет карты.

Каждый раз, когда ты доходишь до развилки, ты записываешь в блокнот:

"Я сейчас в коридоре A, и уже пошёл в дверь 1 из 3 возможных."

Если за этой дверью тупик — ты возвращаешься назад, смотришь в блокнот и говоришь:

"Хм, я был в коридоре A и пробовал дверь 1. Попробую теперь дверь 2."

Идёшь туда, снова записываешь шаг, и так далее.

Так и работает Backtracking в программировании:
▫ты пробуешь решение
▫если оно не подходит — возвращаешься назад, отменяешь выбор и пробуешь другое
▫ты не забываешь, где был, и всегда можешь шагнуть обратно, чтобы попробовать что-то другое

#backtracking

➡️Также уточнение

Стартуем сразу с 🟡medium задач, так как это довольно сложная тема и задач уровня 🟢easy для нее нет

🟡Medium
2698. Find the Punishment Number of an Integer

Company: 🔍📱📕

📝Дано число n, верните номер наказания.

Номер наказания для n определяется, как сумма квадратов всех целых чисел i, таких, что:

➖1 <= i <= n
➖десятичное представление i * i можно разбить таким образом, что сумма частей разбиения будет равна i

💡: пройди все числа от 1 до n и для каждого перебери все способы разрезать число по цифрам, возвращаясь назад, если их сумма превышает нужное значение

#leetcode2698 | #medium #backtracking

✅ Решение задачи 2698

Time: O(n * 2^k)
Space: O(k), [k = O(log^2 n)]

💡 Идея
🟦перебираем все числа от 1 до n и для каждого вычисляем его квадрат, а затем вызываем вспомогательный метод canPartition, чтобы проверить условие разложения

🟦если условие выполняется — т.е. квадрат можно разбить на части, сумма которых равна самому числу — то этот квадрат прибавляется к сумме res

🟦метод canPartition реализует backtracking, пытаясь проверить все возможные комбинации подстрок, преобразуемых в числа, и проверить, можно ли их суммой получить исходное число:
➖на каждом шаге выбираем очередную подстроку, уменьшаем целевое значение target на её числовое значение и делаем рекурсивный вызов для оставшейся строки

➖если сумма не совпадает или превышает целевое значение, происходит откат (backtrack) и пробуется следующий вариант разбиения

👩‍💻 Java Algo | #solution2698

🟡Medium
1079. Letter Tile Possibilities

Company: 🏢📱📱

📝Дана строка tiles, состоящая только из заглавных букв.

Верните количество возможных непустых последовательностей, которые вы можете составить, используя буквы tiles

💡: рекурсивно составляйте все возможные комбинации, используя массив частот символов

#leetcode1079 | #medium #backtracking

✅ Решение задачи 1079

Time: O(n!)
Space: O(n)

💡 Идея
🟦

Представьте, что мы играем с фишками «Скрабла» и у нас есть строка «AAABBC».

Здесь можно сделать важное замечание: на самом деле важно не расположение каждой буквы, а количество имеющихся в наличии фишек каждой буквы. Независимо от того, используем ли мы первую «А» или вторую «А», последовательности, которые мы можем создать, не меняются — нам просто нужно знать, что у нас есть три «А».

Это понимание подводит нас к ключевому решению: вместо отслеживания отдельных букв мы можем отслеживать частоту каждой из них

🟦Сначала создадим массив freq длиной 26, где каждый элемент соответствует количеству вхождений соответствующей буквы в строке, что позволит эффективно отслеживать, какие символы ещё можно использовать при построении комбинаций

🟦Затем используем рекурсивную функцию backtrack, которая перебирает все возможные варианты построения комбинаций:
➖на каждой итерации выбираем букву, которая ещё осталась

➖уменьшаем её частоту и добавляем 1 к результату, что означает новую уникальную комбинацию

➖вызываем рекурсивно backtrack, чтобы продолжить построение более длинных комбинаций

➖затем восстанавливаем частоту буквы обратно (backtracking)

🟦Таким образом, каждая ветка рекурсии учитывает все возможные перестановки символов с текущим набором оставшихся, тем самым эффективно находя общее число уникальных комбинаций всех возможных длин

👩‍💻 Java Algo | #solution1079

🟡Medium
47. Permutations II

Company: 📱📱🅰️

📝Дан целочисленный массив, который может содержать дубликаты. Верните все возможные уникальные перестановки в любом порядке

💡: отсортируйте массив и пропускайте одинаковые элементы на одном уровне рекурсии, чтобы избежать дубликатов в перестановках

#leetcode47 | #medium #backtracking

✅ Решение задачи 47

Time: O(n*n!)
Space: O(n!)

💡 Идея
🟦Сначала отсортируем массив, чтобы одинаковые числа оказались рядом — это необходимо для последующей фильтрации повторяющихся перестановок

🟦Далее используем ключевой метод backtrack:
➖внутри цикла перебираем все возможные числа, которые ещё не были использованы

➖после добавления числа в текущую комбинацию и отметки его как использованного рекурсивно вызываем backtrack

➖после возврата из рекурсии — делаем откат (backtrack): число удаляется и помечается как неиспользованное

➖при этом, если текущий элемент равен предыдущему, но предыдущий ещё не был использован в текущей ветке построения, значит, мы уже рассматривали эту комбинацию на этом уровне рекурсии и её нужно пропустить, чтобы избежать дубликатов в результате

➖когда текущая перестановка достигает нужной длины (размер входного массива), она добавляется в итоговый список

🟦Такой подход гарантирует, что будут перебраны все возможные уникальные перестановки без дубликатов, и результат будет полным и корректным

👩‍💻 Java Algo | #solution47

🟡Medium
306. Additive Number

Company: 📱

📝Дана строка, содержащая только цифры, вернуть true, если она является аддитивным числом.

Аддитивное число — это строка, цифры которой могут образовывать допустимую аддитивную последовательность:

▫ содержит не менее трёх чисел
▫ каждое последующее число в последовательности должно быть суммой двух предыдущих (за исключением первых двух)
▫числа в последовательности не могут иметь начальных нулей

💡: переберите все возможные комбинации первых двух чисел и продолжайте разбиение строки, если следующее число равно их сумме

#leetcode306 | #medium #backtracking

✅ Решение задачи 306

Time: O(2^n)
Space: O(n)

💡 Идея
🟦Из основного метода вызываем вспомогательный рекурсивный метод backtrack, который принимает:
▫исходную строку с цифрами (num)
▫текущую позицию в строке (start)
▫два предыдущих числа (n1, n2)
▫количество найденных чисел в последовательности (count)

🟦В методе backtrack делаем следующее:
➖на каждой итерации формируем текущее число currNum, последовательно добавляя цифры из строки

➖если два предыдущих числа равны -1 (ещё не заданы), или сумма двух предыдущих равна текущему числу, рекурсивно проверяем продолжение цепочки с новым числом

➖условие завершения — если достигнут конец строки и найдено хотя бы три числа

➖также учитываем случаи, когда число начинается с нуля и его длина больше одного, прекращая обработку этой ветки

🟦Таким образом, мы перебираем все возможные варианты составления текущего числа, чтобы оно соответствовало условиям аддитивной последовательности — либо как одно из первых двух чисел, либо как сумма двух предыдущих, проверяя строку до самого конца

👩‍💻 Java Algo | #solution306

🟡Medium
1415. The k-th Lexicographical String of All Happy Strings of Length n

Company: 🔍📱🏢

📝Даны два целых числа n и k. Рассмотрите отсортированный в лексикографическом порядке список всех счастливых строк длины n.

Верните k-ю строку этого списка или пустую строку, если количество счастливых строк меньше.

Счастливая строка — это строка, которая:
▫состоит только из букв набора ['a', 'b', 'c']
▫не содержит двух рядом стоящих одинаковых символов

Список счастливых строк для примера 3:

["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]

💡: рекурсивно стройте строки, добавляя буквы от 'a' к 'c', избегая одинаковых соседних символов

#leetcode1415 | #medium #backtracking

✅ Решение задачи 1415

Time: O(2^n)
Space: O(n*2^n)

💡 Идея
🟦Решение состоит в том, чтобы строить последовательности, всегда выбирая наименьшую возможную букву в лексикографическом порядке, при этом избегая повторов подряд. Для этого в методе backtrack:

➖перебираем массив допустимых букв и пытаемся поставить текущую букву в строку, проверяя, что она не совпадает с предыдущей

➖если условие выполнено, добавляем букву и рекурсивно вызываем backtrack, чтобы продолжить построение

➖когда длина текущей строки достигает заданного n, она считается готовой и добавляется в список all. Этот список автоматически формируется в лексикографическом порядке, так как перебор букв идёт от 'a' к 'c'

➖после возврата из рекурсии удаляем последнюю добавленную букву, чтобы освободить место для других вариантов

🟦В конце, когда все варианты построены, остаётся просто вернуть k-ю строку из списка или пустую строку, если k превышает количество сгенерированных последовательностей

👩‍💻 Java Algo | #solution1415