Java | LeetCode

channel icon
Сайт: easyoffer.ru

Условия размещения

Цена за 48 часов в ленте 2650,00
Цена за 1 час закрепления
Взаимопиар Нет
0
6 968
подписчиков
-13
712
охват 1 публикации
0
~4
постов / день
-0,2%
10,2%
ERR % ?

Статистика

Последние публикации

Java | LeetCode
20 июня 2025 г. 22:17
Запустите рекламу в телеграм-каналах с Яндекс ДиректомЗапустите рекламу в телеграм-каналах с Яндекс Директом

Перфоманс-реклама теперь в телеграм-каналах ⚡

Яндекс Директ знает, как привлечь целевую аудиторию 💰👌

ПопробоватьПопробовать

#реклама
yandex.ru

О рекламодателе
Java | LeetCode
20 июня 2025 г. 19:01
Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15


👨‍💻 Алгоритм:

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.

3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.

😎 Решение:
public class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = 0, right = 0;
for (int weight : weights) {
left = Math.max(left, weight);
right += weight;
}

while (left < right) {
int mid = (left + right) / 2;
if (canShipInDays(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

private boolean canShipInDays(int[] weights, int D, int capacity) {
int days = 1, total = 0;
for (int weight : weights) {
if (total + weight > capacity) {
days++;
total = 0;
}
total += weight;
}
return days <= D;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
20 июня 2025 г. 16:11
Дизайн в FIGMA с нуля. Бесплатный курс + портфолиоДизайн в FIGMA с нуля. Бесплатный курс + портфолио

Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб.

Узнать большеУзнать больше

#реклама 16+
yudaevschool24.online

О рекламодателе
Java | LeetCode
20 июня 2025 г. 12:01
Задача: 476. Number Complement
Сложность: easy

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.

Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:
Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.


👨‍💻 Алгоритм:

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:
class Solution {
public int findComplement(int num) {
int bitmask = num;
bitmask |= (bitmask >> 1);
bitmask |= (bitmask >> 2);
bitmask |= (bitmask >> 4);
bitmask |= (bitmask >> 8);
bitmask |= (bitmask >> 16);
return bitmask ^ num;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
19 июня 2025 г. 22:04
Современная магистратура от Центрального университетаСовременная магистратура от Центрального университета

Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой?
Поступай в магистратуру Центрального университета!

- 4 офлайн программы по востребованным направлениям ИТ
- Онлайн-программа по машинному обучению
- 300 мест с грантами до 1,2 млн руб.
- Вечерние занятия и учеба по выходным — удобно совмещать с работой
- Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса
- Возможность стажировок и трудоустройства в ведущих компаниях
- Государственный диплом за 2 года

Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии.

Оставляй заявку на грант уже сейчас!

Подать заявкуПодать заявку

#реклама 16+
apply.centraluniversity.ru

О рекламодателе
Java | LeetCode
19 июня 2025 г. 19:01
Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False


👨‍💻 Алгоритм:

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:
import java.util.ArrayList;
import java.util.List;

class CombinationIterator {
private List combinations;

public CombinationIterator(String characters, int combinationLength) {
combinations = new ArrayList<>();
int n = characters.length();
int k = combinationLength;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
if (Integer.bitCount(bitmask) == k) {
StringBuilder curr = new StringBuilder();
for (int j = 0; j < n; ++j) {
if ((bitmask & (1 << (n - j - 1))) != 0) {
curr.append(characters.charAt(j));
}
}
combinations.add(curr.toString());
}
}
}

public String next() {
return combinations.remove(combinations.size() - 1);
}

public boolean hasNext() {
return !combinations.isEmpty();
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
19 июня 2025 г. 14:43
Онлайн-магистратура в IT совместно с ИТМО, МИФИ и МФТИОнлайн-магистратура в IT совместно с ИТМО, МИФИ и МФТИ

День открытых дверей
26 июня в 19.00 по Москве | Онлайн
Все программы 2025, общение со студентами и экспертами из вузов и Яндекса. Ответы на вопросы.

ЗарегистрироватьсяЗарегистрироваться

#реклама 16+
praktikum.yandex.ru

О рекламодателе
Java | LeetCode
19 июня 2025 г. 12:01
Задача: 39. Combination Sum
сложность: medium

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

Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается.

Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.

Пример:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]


👨‍💻 Алгоритм:

1⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎 Решение:
class Solution {
protected void backtrack(
int remain,
LinkedList comb,
int start,
int[] candidates,
List> results
) {
if (remain == 0) {
results.add(new ArrayList(comb));
return;
} else if (remain < 0) {
return;
}

for (int i = start; i < candidates.length; ++i) {
comb.add(candidates[i]);
this.backtrack(
remain - candidates[i],
comb,
i,
candidates,
results
);
comb.removeLast();
}
}

public List> combinationSum(int[] candidates, int target) {
List> results = new ArrayList>();
LinkedList comb = new LinkedList();

this.backtrack(target, comb, 0, candidates, results);
return results;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
18 июня 2025 г. 21:12
Демо-версия профессии фронтенд-разработчика!Демо-версия профессии фронтенд-разработчика!

Получитье бесплатный пробный доступ к обучению «Профессия Frontend-разработчик».

«Профессия Frontend-разработчик» — это программа подготовки для фронтендеров с нуля до уровня junior. Мы разработали этот курс совместно с BigTech-компаниями как альтернативу классической магистратуре в вузе.

Сейчас вы можете бесплатно попробовать это обучение на демо-доступе.

В течение нескольких дней вы:

✅ протестируете формат уроков в Result;

✅ попробуете написать код и выполнить несколько заданий;

✅ посетите мастер-класс для начинающих;

✅ познакомитесь с единомышленниками;

✅ сможете задать вопрос про разработку и обучение в чате.

Подать заявкуПодать заявку

#реклама 16+
learn.result-university.com

О рекламодателе
Java | LeetCode
18 июня 2025 г. 19:01
Задача: 64. Minimum Path Sum
Сложность: medium

На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути.

Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени.

Пример:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.


👨‍💻 Алгоритм:

1⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы.

2⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз.

3⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий.

😎 Решение:
public class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if (i == grid.length - 1 && j != grid[0].length - 1) dp[i][j] =
grid[i][j] + dp[i][j + 1];
else if (
j == grid[0].length - 1 && i != grid.length - 1
) dp[i][j] = grid[i][j] + dp[i + 1][j];
else if (
j != grid[0].length - 1 && i != grid.length - 1
) dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
else dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
18 июня 2025 г. 12:01
Задача: 225. Implement Stack using Queues
Сложность: easy

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False


👨‍💻 Алгоритм:

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

3⃣Поддержка стандартных операций очереди:
Используйте только стандартные операции очереди: добавление в конец, удаление из начала, определение размера и проверка на пустоту.

😎 Решение:
import java.util.LinkedList;
import java.util.Queue;

class MyStack {
private Queue q1 = new LinkedList<>();
private Queue q2 = new LinkedList<>();
private int top;

public void push(int x) {
q2.add(x);
top = x;
while (!q1.isEmpty()) {
q2.add(q1.remove());
}
Queue temp = q1;
q1 = q2;
q2 = temp;
}

public void pop() {
q1.remove();
if (!q1.isEmpty()) {
top = q1.peek();
}
}

public boolean empty() {
return q1.isEmpty();
}

public int top() {
return top;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
17 июня 2025 г. 21:09
Бесплатный курс по 3D-моделированию с нуляБесплатный курс по 3D-моделированию с нуля

Начни карьеру в дизайне и получи первую зарплату!

Вас ждет реальный рабочий процесс:

✅ разные задачи по 3D Blander
✅ опыт общения с клиентами
✅ оплата за проект

Освойте Blender и создайте работу для портфолио

Обучение полностью бесплатное для первых 70 участников.
Осталось 28 мест.

В конце курса мы откроем для вас доступ к звездной распродаже

Там вы сможете обменять звездочки на ценные бонусы:

1. Гайд по выходу на биржу UpWork
2. Курс «Заработок на дизайне»
3. Анимированный концепт Samsung True для портфолио
4. Бессрочный грант на обучение: 15 000 ₽
5. Гайд «Горячие клавиши в Blender»

Записывайтесь сейчас!

Узнать большеУзнать больше

#реклама 16+
yudaevschool24.online

О рекламодателе
Java | LeetCode
17 июня 2025 г. 19:01
Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.

Пример:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1


👨‍💻 Алгоритм:

1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

2⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;

if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}

grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}

return num_islands;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
17 июня 2025 г. 13:34
Запусти IT-бизнес с доходом от 500 000 ₽/мес за 7 дней!Запусти IT-бизнес с доходом от 500 000 ₽/мес за 7 дней!

Что вы получаете:
✅ IT-продукт с рынком 416+ млрд ₽
💰 Доход от 500 000 ₽ в первый месяц
💻 Полностью онлайн — работайте из любой точки мира

Стартовый бюджет: от 200 000 ₽
Окупаемость: 14 дней ⚡

Узнать большеУзнать больше

#реклама
edler.pro

О рекламодателе
Java | LeetCode
17 июня 2025 г. 12:01
ЗадачаЗадача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.


👨‍💻 Алгоритм:

1⃣Определите количество возможных двоичных кодов длины k.

2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:
class Solution {
public static boolean hasAllCodes(String s, int k) {
int need = 1 << k;
boolean[] got = new boolean[need];
int allOne = need - 1;
int hashVal = 0;

for (int i = 0; i < s.length(); i++) {
hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
if (i >= k - 1 && !got[hashVal]) {
got[hashVal] = true;
need--;
if (need == 0) {
return true;
}
}
}
return false;
}
}


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
16 июня 2025 г. 22:11
Вакансия удалённый 1C-программист. З/П до 250 000 ₽Вакансия удалённый 1C-программист. З/П до 250 000 ₽

Ищем 1С-программиста с опытом от 3-х лет на full-time. Аккредитованная IT-компания. Удалённая работа из любой точки мира. ДМО. Оформление в штат по ТК РФ. Зарплата до 250000 ₽. Помощь в развитии.

Стань частью профессиональной команды Programming Store. Переходи по ссылке и откликайся!

Подать заявкуПодать заявку

#реклама
mrqz.me

О рекламодателе
Java | LeetCode
16 июня 2025 г. 19:01
Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:
Input: deck = [1,2,3,4,4,3,2,1]
Output: true


👨‍💻 Алгоритм:

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:
import java.util.*;
import java.util.stream.Collectors;

class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map count = new HashMap<>();
for (int num : deck) {
count.put(num, count.getOrDefault(num, 0) + 1);
}

int g = count.values().stream().reduce(this::gcd).orElse(0);
return g > 1;
}

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


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
16 июня 2025 г. 12:01
Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false


👨‍💻 Алгоритм:

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:
var isBoomerang = function(points) {
let [x1, y1] = points[0];
let [x2, y2] = points[1];
let [x3, y3] = points[2];
return (x1 !== x2 || y1 !== y2) &&
(x1 !== x3 || y1 !== y3) &&
(x2 !== x3 || y2 !== y3) &&
(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) !== 0;
};


Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний
Java | LeetCode
15 июня 2025 г. 21:12
Дарим подписку на Яндекс МузыкуДарим подписку на Яндекс Музыку

Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️

ПопробоватьПопробовать

#реклама 18+
music.yandex.ru

О рекламодателе
Реклама на Яндексе
Java | LeetCode
15 июня 2025 г. 19:01
Задача: 685. Redundant Connection II
Сложность: hard

В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.

Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]


👨‍💻 Алгоритм:

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map parent = new HashMap<>();
List candidates = new ArrayList<>();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[]{parent.get(edge[1]), edge[1]});
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}

int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set cycle = orbit(root, parent).seen;
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
return edge;
}
}
}

Map> children = new HashMap<>();
for (int v : parent.keySet()) {
int pv = parent.get(v);
children.computeIfAbsent(pv, k -> new ArrayList<>()).add(v);
}

boolean[] seen = new boolean[N + 1];
Stack stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
stack.addAll(children.get(node));
}
}
}
for (boolean b : seen) {
if (!b) {
return candidates.get(0);
}
}
return candidates.get(1);
}

public OrbitResult orbit(int node, Map parent) {
Set seen = new HashSet<>();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}

class OrbitResult {
int node;
Set seen;
OrbitResult(int n, Set s) {
node = n;
seen = s;
}
}


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