Endi mavjud! Telegram Tadqiqoti 2025 — yilning asosiy insaytlari 
Java | LeetCode
Kanalga Telegram’da o‘tish
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+icUwivvbGOkwNWRi Вопросы собесов t.me/+7ESm0VKXC4tjYzky Вакансии t.me/+4pspF5nDjgM4MjQy
Ko'proq ko'rsatish6 661
Obunachilar
-424 soatlar
-177 kunlar
-4530 kunlar
Postlar arxiv
6 662
Задача: 1007. Minimum Domino Rotations For Equal Row
Сложность: medium
В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1.
Пример:
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] Output: 2👨💻 Алгоритм: 1⃣Проверка кандидатов: Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино. 2⃣Подсчет поворотов для каждого кандидата: Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms. Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения. 3⃣Возврат минимального количества поворотов: Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1. 😎 Решение:
public class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int check(int x) {
int rotationsA = 0, rotationsB = 0;
for (int i = 0; i < tops.length; i++) {
if (tops[i] != x && bottoms[i] != x) {
return -1;
} else if (tops[i] != x) {
rotationsA++;
} else if (bottoms[i] != x) {
rotationsB++;
}
}
return Math.min(rotationsA, rotationsB);
}
int rotations = check(tops[0]);
if (rotations != -1 || tops[0] == bottoms[0]) {
return rotations;
} else {
return check(bottoms[0]);
}
}
}6 662
Онлайн-магистратура с IT специальностями от Яндекса
Совместно с ИТМО, МИФИ, МФТИ.
Онлайн-магистратура с актуальными программами и гибким графиком обучения.
Получите высокооплачиваемую IT профессию, официальный диплом и практические знания.
Господдержка оплаты. Совмещение с работой!
Подать заявку
#реклама 16+
practicum.yandex.ru
О рекламодателе
6 662
Задача: 260. Single Number III
Сложность: medium
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.👨💻 Алгоритм: 1⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел. 2⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы. 3⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа. 😎 Решение:
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
int diff = xor & -xor;
int[] res = new int[2];
for (int num : nums) {
if ((num & diff) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
}6 662
Реклама для бизнеса любого уровня в Яндекс Директе
Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌
Начните прямо сейчас ⚡
Зарегистрироваться
#реклама
direct.yandex.ru
О рекламодателе
6 662
Задача: 142. Linked List Cycle II
Сложность: medium
Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.
Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.
Не модифицируйте связный список.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.👨💻 Алгоритм: 1⃣Инициализация и начало обхода: Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов. Начните обход со связного списка, перемещая узел на один шаг за раз. 2⃣Проверка на наличие узла в множестве: Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen. Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл. 3⃣Добавление узла в множество или завершение обхода: Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу. Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка. 😎 Решение:
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> nodesSeen = new HashSet<>();
ListNode node = head;
while (node != null) {
if (nodesSeen.contains(node)) {
return node;
} else {
nodesSeen.add(node);
node = node.next;
}
}
return null;
}
}6 662
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 662
Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium
Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.
Пример:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"] Output: ["/a","/c/d","/c/f"]👨💻 Алгоритм: 1⃣Сортировка папок: Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками. 2⃣Фильтрация вложенных папок: Будем использовать переменную для отслеживания текущей родительской папки. 3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список. 😎 Решение:
import java.util.*;
public class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String> result = new ArrayList<>();
String parent = "";
for (String path : folder) {
if (parent.isEmpty() || !path.startsWith(parent + "/")) {
parent = path;
result.add(path);
}
}
return result;
}
}6 662
Repost from easyoffer
⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.
Напоминаю, что в честь релиза запускаем акцию.
Первые 500 покупателей получат:
🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал
🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь
6 662
Задача: 650. 2 Keys Keyboard
Сложность: medium
На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.
Пример:
Input: n = 3 Output: 3👨💻 Алгоритм: 1⃣Используйте динамическое программирование для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране. 2⃣Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа. 3⃣Возвращайте значение из таблицы динамического программирования для n. 😎 Решение:
public class Solution {
public int minSteps(int n) {
if (n == 1) return 0;
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 1; j <= i / 2; j++) {
if (i % j == 0) {
dp[i] = Math.min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
}6 662
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 662
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.class Solution {
public ListNode deleteNodes(ListNode head, int m, int n) {
ListNode currentNode = head;
ListNode lastMNode = head;
while (currentNode != null) {
int mCount = m, nCount = n;
while (currentNode != null && mCount != 0) {
lastMNode = currentNode;
currentNode = currentNode.next;
mCount--;
}
while (currentNode != null && nCount != 0) {
currentNode = currentNode.next;
nCount--;
}
lastMNode.next = currentNode;
}
return head;
}
}6 662
Регистрируйтесь на Yandex Ecom Open Air 8 августа
Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг.
Участие бесплатно!
Зарегистрироваться
#реклама 18+
ecomfest.ru
О рекламодателе
6 662
Задача: 1004. Max Consecutive Ones III
Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6👨💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение:
public class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, maxOnes = 0, zeroCount = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) {
zeroCount++;
}
while (zeroCount > k) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
maxOnes = Math.max(maxOnes, right - left + 1);
}
return maxOnes;
}
}6 662
Задача: 993. Cousins in Binary Tree
Сложность: easy
Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.
Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.
Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.
Пример:
Input: root = [1,2,3,4], x = 4, y = 3 Output: false👨💻 Алгоритм: 1⃣Поиск глубины и родителя для каждого узла: Используйте поиск в глубину (DFS) для обхода дерева. Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y. 2⃣Проверка условий на кузенов: Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей. 3⃣Возврат результата: Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false. 😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private TreeNode parentX = null;
private TreeNode parentY = null;
private int depthX = -1;
private int depthY = -1;
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root, null, 0, x, y);
return depthX == depthY && parentX != parentY;
}
private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
if (node == null) {
return;
}
if (node.val == x) {
parentX = parent;
depthX = depth;
} else if (node.val == y) {
parentY = parent;
depthY = depth;
} else {
dfs(node.left, node, depth + 1, x, y);
dfs(node.right, node, depth + 1, x, y);
}
}
}6 662
Задача: 1473. Paint House III
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.class Solution {
Integer[][][] memo = new Integer[100][100][21];
final int MAX_COST = 1000001;
int findMinCost(int[] houses, int[][] cost, int targetCount, int currIndex,
int neighborhoodCount, int prevHouseColor) {
if (currIndex == houses.length) {
return neighborhoodCount == targetCount ? 0 : MAX_COST;
}
if (neighborhoodCount > targetCount) {
return MAX_COST;
}
if (memo[currIndex][neighborhoodCount][prevHouseColor] != null) {
return memo[currIndex][neighborhoodCount][prevHouseColor];
}
int minCost = MAX_COST;
if (houses[currIndex] != 0) {
int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
minCost =
findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
} else {
int totalColors = cost[0].length;
for (int color = 1; color <= totalColors; color++) {
int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
int currCost = cost[currIndex][color - 1]
+ findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
minCost = Math.min(minCost, currCost);
}
}
return memo[currIndex][neighborhoodCount][prevHouseColor] = minCost;
}
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int answer = findMinCost(houses, cost, target, 0, 0, 0);
return answer == MAX_COST ? -1 : answer;
}
}6 662
Задача: 505. The Maze II
Сложность: medium
В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.
Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).
Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.
Пример:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: 12 Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.👨💻 Алгоритм: 1⃣Инициализация Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь. 2⃣Обход лабиринта Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов. 3⃣Обновление расстояний Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь. 😎 Решение:
public class Solution {
public int shortestDistance(int[][] maze, int[] start, int[] dest) {
int[][] distance = new int[maze.length][maze[0].length];
for (int[] row: distance)
Arrays.fill(row, Integer.MAX_VALUE);
distance[start[0]][start[1]] = 0;
int[][] dirs={{0, 1} ,{0, -1}, {-1, 0}, {1, 0}};
Queue < int[] > queue = new LinkedList < > ();
queue.add(start);
while (!queue.isEmpty()) {
int[] s = queue.remove();
for (int[] dir: dirs) {
int x = s[0] + dir[0];
int y = s[1] + dir[1];
int count = 0;
while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
if (distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]) {
distance[x - dir[0]][y - dir[1]] = distance[s[0]][s[1]] + count;
queue.add(new int[] {x - dir[0], y - dir[1]});
}
}
}
return distance[dest[0]][dest[1]] == Integer.MAX_VALUE ? -1 : distance[dest[0]][dest[1]];
}
}6 662
Задача: 68. Text Justification
Сложность: hard
Дан массив строк wordsи чисел maxWidth. Нужно было отформатировать текст так, чтобы в строке были ровное число maxWidthсимволов, и она была выровнена по ширине.
Слова выводятся жадно, пробелы добавляются так, чтобы строки были выровнены, при этом слева добавляется больше пробелов. Последняя строка проводится по левому краю.
Пример:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ]👨💻 Алгоритм: 1⃣Создайте два вспомогательных метода getWords и createLine, описанные выше. 2⃣Инициализируйте список ответов ans и целочисленную переменную i для итерации по входным данным. Используйте цикл while для перебора входных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе. 3⃣Пока i < words.length, выполните следующие шаги: Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i). Увеличьте i на currentLine.length. Создайте строку, вызвав createLine(line, i), и добавьте её в ans. Верните ans. 😎 Решение:
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int i = 0;
while (i < words.length) {
List<String> currentLine = getWords(i, words, maxWidth);
i += currentLine.size();
ans.add(createLine(currentLine, i, words, maxWidth));
}
return ans;
}
private List<String> getWords(int i, String[] words, int maxWidth) {
List<String> currentLine = new ArrayList<>();
int currLength = 0;
while (i < words.length && currLength + words[i].length() <= maxWidth) {
currentLine.add(words[i]);
currLength += words[i].length() + 1;
i++;
}
return currentLine;
}
private String createLine(
List<String> line,
int i,
String[] words,
int maxWidth
) {
int baseLength = -1;
for (String word : line) {
baseLength += word.length() + 1;
}
int extraSpaces = maxWidth - baseLength;
if (line.size() == 1 || i == words.length) {
return String.join(" ", line) + " ".repeat(extraSpaces);
}
int wordCount = line.size() - 1;
int spacesPerWord = extraSpaces / wordCount;
int needsExtraSpace = extraSpaces % wordCount;
for (int j = 0; j < needsExtraSpace; j++) {
line.set(j, line.get(j) + " ");
}
for (int j = 0; j < wordCount; j++) {
line.set(j, line.get(j) + " ".repeat(spacesPerWord));
}
return String.join(" ", line);
}
}6 662
Задача: 660. Remove 9
Сложность: hard
Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29...
Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].
Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности.
Пример:
Input: n = 9 Output: 10👨💻 Алгоритм: 1⃣Инициализация: Начните с числа 1 и создайте переменную для отслеживания количества найденных чисел, не содержащих цифру 9. 2⃣Итерация и проверка: Последовательно увеличивайте число и проверяйте, содержит ли оно цифру 9. Если не содержит, увеличьте счетчик. 3⃣Поиск n-го числа: Продолжайте процесс до тех пор, пока не найдете n-е число, не содержащее цифру 9. 😎 Решение:
public class Solution {
public int newInteger(int n) {
int count = 0;
int num = 0;
while (count < n) {
num++;
if (!Integer.toString(num).contains("9")) {
count++;
}
}
return num;
}
}6 662
Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard
Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.
Пример:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
👨💻 Алгоритм:
1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎 Решение:
import java.util.*;
public class Solution {
public int minPushBox(char[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
int[] player = new int[2], box = new int[2], target = new int[2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'S') {
player = new int[]{i, j};
} else if (grid[i][j] == 'B') {
box = new int[]{i, j};
} else if (grid[i][j] == 'T') {
target = new int[]{i, j};
}
}
}
queue.offer(new int[]{player[0], player[1], box[0], box[1], 0});
visited.add(player[0] + "," + player[1] + "," + box[0] + "," + box[1]);
while (!queue.isEmpty()) {
int[] state = queue.poll();
int px = state[0], py = state[1], bx = state[2], by = state[3], pushes = state[4];
if (bx == target[0] && by == target[1]) {
return pushes;
}
for (int[] dir : directions) {
int npx = px + dir[0], npy = py + dir[1];
if (isValid(npx, npy, m, n, grid)) {
if (npx == bx && npy == by) {
int nbx = bx + dir[0], nby = by + dir[1];
if (isValid(nbx, nby, m, n, grid) && visited.add(npx + "," + npy + "," + nbx + "," + nby)) {
queue.offer(new int[]{npx, npy, nbx, nby, pushes + 1});
}
} else if (visited.add(npx + "," + npy + "," + bx + "," + by)) {
queue.offer(new int[]{npx, npy, bx, by, pushes});
}
}
}
}
return -1;
}
private boolean isValid(int x, int y, int m, int n, char[][] grid) {
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
}
}6 662
Задача: 414. Third Maximum Number
Сложность: easy
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [3,2,1] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел, используя значения None или аналогичные значения. 2⃣Пройдитесь по массиву, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число. 😎 Решение:
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int thirdMax(int[] nums) {
Integer first = null;
Integer second = null;
Integer third = null;
for (Integer num : nums) {
if (num.equals(first) || num.equals(second) || num.equals(third)) {
continue;
}
if (first == null || num > first) {
third = second;
second = first;
first = num;
} else if (second == null || num > second) {
third = second;
second = num;
} else if (third == null || num > third) {
third = num;
}
}
return third != null ? third : first;
}
}