Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 505
Subscribers
No data24 hours
-167 days
-5030 days
Posts Archive
6 505
👨💻 Будущий специалист, ты знаешь, какая самая частая ошибка новичка в сфере IT?
Отсутствие практики убивает в тебе потенциал
✈️ Как с этим бороться, мой друг?
Найди работу и прокачивай свои скилы на конкретных задачах
🔥 У нас ты будешь находить большое количество вакансий каждый день. Понятие работы перестанет быть для тебя размытым.
Подпишись на канал и не откладывай свой прогресс в долгий ящик.
6 505
#easy
Задача: 136. Single Number
Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,1] Output: 1👨💻 Алгоритм: 1️⃣Переберите все элементы в массиве nums. 2️⃣Если какое-то число в nums новое для массива, добавьте его. 3️⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение:
class Solution {
public int singleNumber(int[] nums) {
List<Integer> no_duplicate_list = new ArrayList<>();
for (int i : nums) {
if (!no_duplicate_list.contains(i)) {
no_duplicate_list.add(i);
} else {
no_duplicate_list.remove(new Integer(i));
}
}
return no_duplicate_list.get(0);
}
}6 505
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
6 505
#hard
Задача: 135. Candy
В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.
Вы раздаете конфеты этим детям с соблюдением следующих требований:
Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.
Пример:
Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.👨💻 Алгоритм: 1️⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2️⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3️⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:
public class Solution {
public int candy(int[] ratings) {
int sum = 0;
int[] left2right = new int[ratings.length];
int[] right2left = new int[ratings.length];
Arrays.fill(left2right, 1);
Arrays.fill(right2left, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
left2right[i] = left2right[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right2left[i] = right2left[i + 1] + 1;
}
}
for (int i = 0; i < ratings.length; i++) {
sum += Math.max(left2right[i], right2left[i]);
}
return sum;
}
}6 505
#medium
Задача: 134. Gas Station
Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.
Пример:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3 Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.👨💻 Алгоритм: 1️⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0. 2️⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i]. Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2. 3️⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer. 😎 Решение:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int currGain = 0, totalGain = 0, answer = 0;
for (int i = 0; i < gas.length; ++i) {
totalGain += gas[i] - cost[i];
currGain += gas[i] - cost[i];
if (currGain < 0) {
answer = i + 1;
currGain = 0;
}
}
return totalGain >= 0 ? answer : -1;
}
}6 505
#medium
Задача: 133. Clone Graph
Дана ссылка на узел в связанном неориентированном графе.
Верните глубокую копию (клон) графа.
Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей.
Пример:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).👨💻 Алгоритм: 1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов. 2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных. 3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла. 😎 Решение:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val, List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
HashMap<Node, Node> visited = new HashMap();
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(node);
visited.put(node, new Node(node.val, new ArrayList()));
while (!queue.isEmpty()) {
Node n = queue.remove();
for (Node neighbor : n.neighbors) {
if (!visited.containsKey(neighbor)) {
visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
queue.add(neighbor);
}
visited.get(n).neighbors.add(visited.get(neighbor));
}
}
return visited.get(node);
}
}6 505
#Hard
Задача: 132. Palindrome Partitioning II
Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.
Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.👨💻 Алгоритм: 1️⃣Определение задачи и начальные условия: Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом). 2️⃣Генерация подстрок и рекурсивный поиск: Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки. 3️⃣Условие палиндрома и рекурсивное разделение: Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки 😎 Решение:
class Solution {
public int minCut(String s) {
return findMinimumCut(s, 0, s.length() - 1, s.length() - 1);
}
private int findMinimumCut(String s, int start, int end, int minimumCut) {
if (start == end || isPalindrome(s, start, end)) {
return 0;
}
for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
if (isPalindrome(s, start, currentEndIndex)) {
minimumCut = Math.min(
minimumCut,
1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
);
}
}
return minimumCut;
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
return true;
}
}6 505
Расширьте свои навыки в программировании с бесплатным мини-курсом по Java! Научитесь создавать Telegram-ботов, разрабатывать программы для обработки данных и строить чаты на фреймворке Spring. Не упустите шанс — начните обучение уже сегодня: 👉 https://epic.st/NbtET?erid=2Vtzqv74ZQ7
Формат мини-курса отлично подойдёт для обучения из любой точки мира: смотрите видео в удобное время и закрепляйте навыки на практике.
🎁 За время обучения вы получите 5 полезных материалов в подарок, сертификат на скидку 10 000 рублей на любой курс, персональную карьерную консультацию и доступ к изучению английского языка в Skillbox на год.
До встречи на мини-курсе. Старт после регистрации!
Реклама. ЧОУ ДПО «Образовательные технологии «Скилбокс (Коробка навыков)», ИНН: 9704088880
6 505
#Medium
Задача: 131. Palindrome Partitioning
Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]👨💻 Алгоритм: 1️⃣Инициация рекурсивного обхода: В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start. Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки. 2️⃣Проверка на палиндром и продолжение поиска: Для каждой сгенерированной подстроки проверяем, является ли она палиндромом. Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова. 3️⃣Возврат (Backtracking) и сохранение результатов: Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат. 😎 Решение:
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<List<String>>();
dfs(0, result, new ArrayList<String>(), s);
return result;
}
void dfs(int start, List<List<String>> result, List<String> currentList, String s) {
if (start >= s.length()) result.add(new ArrayList<String>(currentList));
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
currentList.add(s.substring(start, end + 1));
dfs(end + 1, result, currentList, s);
currentList.remove(currentList.size() - 1);
}
}
}
boolean isPalindrome(String s, int low, int high) {
while (low < high) {
if (s.charAt(low++) != s.charAt(high--)) return false;
}
return true;
}
}6 505
Как запустить собственный пет-проект и зарабатывать на нём зарплату senior-разработчика?
На этом канале мы решаем сложные задачи, которые часто попадаются на собеседованиях. Но что, если перевернуть игру и вместо работы на кого-то запустить собственный пет-проект, который будет приносить деньги?
Александр Рогачев запустил телеграм-канал Indie Hackers, где рассказывает про пет-проекты, которые приносят стабильный доход своим создателям.
Без венчурных инвестиций, без бизнес-планов и команды.
Разве такое возможно?
Да!
Несколько примеров:
Агрегатор вакансий c доходом в 4000$ / месяц
Плагин для Chrome с доходом 20000₽ / месяц
Если вы в поиске свежих идей, которые могут обеспечить стабильный пассивных доход, подписывайтесь на канал Indie Hackers.
Уверен, что там вы найдёте то самое, что зажжёт огонь в вашем сердце ❤️🔥
➡️ Ссылка для входа
6 505
#Medium
Задача: 130. Surrounded Regions
Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.
Пример:
Input: board = [["X"]] Output: [["X"]]👨💻 Алгоритм: 1️⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2️⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3️⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:
public class Solution {
protected Integer ROWS = 0;
protected Integer COLS = 0;
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
this.ROWS = board.length;
this.COLS = board[0].length;
List<Pair<Integer, Integer>> borders = new LinkedList<Pair<Integer, Integer>>();
for (int r = 0; r < this.ROWS; ++r) {
borders.add(new Pair(r, 0));
borders.add(new Pair(r, this.COLS - 1));
}
for (int c = 0; c < this.COLS; ++c) {
borders.add(new Pair(0, c));
borders.add(new Pair(this.ROWS - 1, c));
}
for (Pair<Integer, Integer> pair : borders) {
this.DFS(board, pair.first, pair.second);
}
for (int r = 0; r < this.ROWS; ++r) {
for (int c = 0; c < this.COLS; ++c) {
if (board[r][c] == 'O') board[r][c] = 'X';
if (board[r][c] == 'E') board[r][c] = 'O';
}
}
}
protected void DFS(char[][] board, int row, int col) {
if (board[row][col] != 'O') return;
board[row][col] = 'E';
if (col < this.COLS - 1) this.DFS(board, row, col + 1);
if (row < this.ROWS - 1) this.DFS(board, row + 1, col);
if (col > 0) this.DFS(board, row, col - 1);
if (row > 0) this.DFS(board, row - 1, col);
}
}
class Pair<U, V> {
public U first;
public V second;
public Pair(U first, V second) {
this.first = first;
this.second = second;
}
}6 505
#Medium
Задача: 129. Sum Root to Leaf Numbers
Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.
Каждый путь от корня до листа в дереве представляет собой число.
Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.
Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Листовой узел — это узел без детей.
Пример:
Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.👨💻 Алгоритм: 1️⃣Инициализация: Создайте переменные для хранения суммы чисел (rootToLeaf) и текущего числа (currNumber), а также стек для обхода дерева, начиная с корневого узла. 2️⃣Обход дерева: Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf. 3️⃣Возвращение результата: По завершении обхода всех узлов возвращайте rootToLeaf, содержащую сумму всех чисел от корня до листьев дерева. 😎 Решение:
class Solution {
public int sumNumbers(TreeNode root) {
int rootToLeaf = 0, currNumber = 0;
int steps;
TreeNode predecessor;
while (root != null) {
if (root.left != null) {
predecessor = root.left;
steps = 1;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
++steps;
}
if (predecessor.right == null) {
currNumber = currNumber * 10 + root.val;
predecessor.right = root;
root = root.left;
} else {
if (predecessor.left == null) {
rootToLeaf += currNumber;
}
for (int i = 0; i < steps; ++i) {
currNumber /= 10;
}
predecessor.right = null;
root = root.right;
}
} else {
currNumber = currNumber * 10 + root.val;
if (root.right == null) {
rootToLeaf += currNumber;
}
root = root.right;
}
}
return rootToLeaf;
}
}6 505
#Medium
Задача: 128. Longest Consecutive Sequence
Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.
Необходимо написать алгоритм, который работает за время O(n).
Пример:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.👨💻 Алгоритм: 1️⃣Проверка базового случая: Перед началом работы проверяем базовый случай с пустым массивом. Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение. 2️⃣Обработка чисел в массиве: Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим). Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу. Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем. 3️⃣Завершение обработки и возврат результата: В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность). Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной. 😎 Решение:
class Solution {
private boolean arrayContains(int[] arr, int num) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num) {
return true;
}
}
return false;
}
public int longestConsecutive(int[] nums) {
int longestStreak = 0;
for (int num : nums) {
int currentNum = num;
int currentStreak = 1;
while (arrayContains(nums, currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
return longestStreak;
}
}6 505
#Hard
Задача: 127. Word Ladder
Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:
Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.👨💻 Алгоритм: 1️⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние. 2️⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий
beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.
3️⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.
😎 Решение:
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int L = beginWord.length();
Map<String, List<String>> allComboDict = new HashMap<>();
wordList.forEach(word -> {
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
allComboDict.put(newWord, transformations);
}
});
Queue<Pair<String, Integer>> Q = new LinkedList<>();
Q.add(new Pair(beginWord, 1));
Map<String, Boolean> visited = new HashMap<>();
visited.put(beginWord, true);
while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
if (adjacentWord.equals(endWord)) {
return level + 1;
}
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
}
return 0;
}
}6 505
Тестовое собеседование на Middle Java-разработчика сегодня
Сегодня(7 августа) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика.
Как это будет:
1. Степан Аракелян, ex-Tech Lead в МТС и ментор в ШОРКТАТ, проведет настоящее собеседование на Middle Java-разработчика
2. Степан будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью
3. В конце можно будет задать любой вопрос Степану
Что узнаешь на прямом эфире от ШОРТКАТ:
- Чего ждут от кандидатов на Middle позиции в Java-разработке
- Какие вопросы задают на интервью и зачем
- Как подготовиться к собесу, чтобы получить оффер
Это бесплатно?
Бесплатно
Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot
6 505
#Hard
Задача: 126.Word Ladder II
Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] Explanation: There are 2 shortest transformation sequences: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"👨💻 Алгоритм: 1️⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS). 2️⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList. 3️⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths. 😎 Решение:
class Solution {
Map<String, List<String>> adjList = new HashMap<>();
List<String> currPath = new ArrayList<>();
List<List<String>> shortestPaths = new ArrayList<>();
private List<String> findNeighbors(String word, Set<String> wordList) {
List<String> neighbors = new ArrayList<>();
char[] charList = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char oldChar = charList[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == oldChar) continue;
charList[i] = c;
String newWord = String.valueOf(charList);
if (wordList.contains(newWord)) neighbors.add(newWord);
}
charList[i] = oldChar;
}
return neighbors;
}
private void backtrack(String source, String destination) {
if (source.equals(destination)) {
Collections.reverse(currPath);
shortestPaths.add(new ArrayList<>(currPath));
Collections.reverse(currPath);
}
if (!adjList.containsKey(source)) return;
for (String neighbor : adjList.get(source)) {
currPath.add(neighbor);
backtrack(neighbor, destination);
currPath.remove(currPath.size() - 1);
}
}
private void bfs(String beginWord, Set<String> wordList) {
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
wordList.remove(beginWord);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
String currentWord = queue.poll();
for (String neighbor : findNeighbors(currentWord, wordList)) {
adjList.computeIfAbsent(neighbor, k -> new ArrayList<>()).add(currentWord);
if (wordList.remove(neighbor)) queue.add(neighbor);
}
}
}
}
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
bfs(beginWord, new HashSet<>(wordList));
currPath.add(endWord);
backtrack(endWord, beginWord);
return shortestPaths;
}
}6 505
#easy
Задача: 125. Valid Palindrome
Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.
Для данной строки s верните true, если она является палиндромом, и false в противном случае.
Пример:
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.👨💻 Алгоритм: 1️⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода. 2️⃣Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке. 3️⃣Результирующий алгоритм прост: 1. Установите два указателя, один на каждом конце входной строки. 2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени. 3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше. 4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше. 5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине. 😎 Решение:
class Solution {
public boolean isPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
if (
Character.toLowerCase(s.charAt(i)) !=
Character.toLowerCase(s.charAt(j))
) return false;
}
return true;
}
}6 505
#hard
Задача: 124. Binary Tree Maximum Path Sum
Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.
Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.
Пример:
Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1👨💻 Алгоритм: 1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение. Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²). 2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй, одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство. В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием. 3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i]. Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]). Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5. И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]). Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6. Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1], то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом: max_profits[i] = left_profits[i] + right_profits[i+1] 😎 Решение:
class Solution {
public int maxProfit(int[] prices) {
int length = prices.length;
if (length <= 1) return 0;
int leftMin = prices[0];
int rightMax = prices[length - 1];
int[] leftProfits = new int[length];
int[] rightProfits = new int[length + 1];
for (int l = 1; l < length; ++l) {
leftProfits[l] = Math.max(leftProfits[l - 1], prices[l] - leftMin);
leftMin = Math.min(leftMin, prices[l]);
int r = length - 1 - l;
rightProfits[r] = Math.max(
rightProfits[r + 1],
rightMax - prices[r]
);
rightMax = Math.max(rightMax, prices[r]);
}
int maxProfit = 0;
for (int i = 0; i < length; ++i) {
maxProfit = Math.max(
maxProfit,
leftProfits[i] + rightProfits[i + 1]
);
}
return maxProfit;
}
}6 505
#medium
Задача: 122. Best Time to Buy and Sell Stock II
Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день.
Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день.
Найдите и верните максимальную прибыль, которую вы можете получить.
Пример:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.👨💻 Алгоритм: 1️⃣Предположим, что дан массив: \[ 7, 1, 5, 3, 6, 4 \] Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение* 2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики. Математически говоря: Общая прибыль = ∑ (высота(пик i) - высота(впадина i)) 3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли. Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B. 😎 Решение:
class Solution {
public int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
}
}6 505
#easy
Задача: 121. Best Time to Buy and Sell Stock
Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.
Ваша задача — максимизировать вашу прибыль, выбрав один день для покупки акции и другой день в будущем для ее продажи.
Верните максимальную прибыль, которую вы можете получить от этой операции. Если прибыль получить невозможно, верните 0.
Пример:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.👨💻 Алгоритм: Ключевые моменты на графике — это пики и впадины. Нам нужно найти наибольшую цену после каждой впадины, разница между которыми может быть максимальной прибылью. Мы можем поддерживать две переменные — minprice и maxprofit, соответствующие наименьшей впадине и максимальной прибыли (максимальной разнице между ценой продажи и minprice), полученной на данный момент соответственно. 😎 Решение:
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) minprice = prices[i];
else if (prices[i] - minprice > maxprofit) maxprofit = prices[i] -
minprice;
}
return maxprofit;
}
}