Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 520
Subscribers
-324 hours
-207 days
-4730 days
Posts Archive
6 520
Задача: 725. Split Linked List in Parts
Сложность: medium
Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.
Пример:
Input: head = [1,2,3], k = 5 Output: [[1],[2],[3],[],[]]👨💻 Алгоритм: 1⃣Определите общую длину связного списка. 2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее. 3⃣Разделите список на части, присваивая каждую часть в массив результатов. 😎 Решение:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
int length = 0;
ListNode node = root;
while (node != null) {
length++;
node = node.next;
}
int partLength = length / k;
int extraParts = length % k;
ListNode[] parts = new ListNode[k];
node = root;
for (int i = 0; i < k; i++) {
ListNode partHead = node;
int partSize = partLength + (i < extraParts ? 1 : 0);
for (int j = 0; j < partSize - 1; j++) {
if (node != null) node = node.next;
}
if (node != null) {
ListNode nextPart = node.next;
node.next = null;
node = nextPart;
}
parts[i] = partHead;
}
return parts;
}
}6 520
Задача: 655. Print Binary Tree
Сложность: medium
Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.
Пример:
Input: root = [1,2] Output: [["","1",""], ["2","",""]]👨💻 Алгоритм: 1⃣Найдите высоту дерева и определите размер матрицы (m x n). 2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла. 3⃣Верните заполненную матрицу. 😎 Решение:
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
private int findHeight(TreeNode root) {
if (root == null) return -1;
return 1 + Math.max(findHeight(root.left), findHeight(root.right));
}
private void fill(String[][] res, TreeNode root, int r, int c, int height) {
if (root == null) return;
res[r][c] = Integer.toString(root.val);
if (root.left != null) {
fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
}
if (root.right != null) {
fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
}
}
public List<List<String>> printTree(TreeNode root) {
int height = findHeight(root);
int m = height + 1;
int n = (1 << (height + 1)) - 1;
String[][] res = new String[m][n];
for (String[] row : res) {
Arrays.fill(row, "");
}
fill(res, root, 0, (n - 1) / 2, height);
List<List<String>> result = new ArrayList<>();
for (String[] row : res) {
result.add(Arrays.asList(row));
}
return result;
}
}6 520
Задача: 1220. Count Vowels Permutation
Сложность: hard
Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам:
Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u')
Каждая гласная 'a' может быть только перед 'e'.
Каждая гласная 'e' может быть только перед 'a' или 'i'.
Каждая гласная 'i' не может быть перед другой 'i'.
Каждая гласная 'o' может быть только перед 'i' или 'u'.
Каждая гласная 'u' может быть только перед 'a'.
Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 2 Output: 10 Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".👨💻 Алгоритм: 1⃣Инициализация массивов и начальных условий: Инициализируйте пять одномерных массивов размером n для хранения количества строк, оканчивающихся на каждую гласную. Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной. 2⃣Заполнение массивов в соответствии с правилами: Проходите по длине строки от 1 до n. Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения. 3⃣Суммирование и возврат результата: Возьмите сумму последних элементов всех пяти массивов. Верните результат по модулю 10^9 + 7. 😎 Решение:
class Solution {
public int countVowelPermutation(int n) {
long[] aVowelPermutationCount = new long[n];
long[] eVowelPermutationCount = new long[n];
long[] iVowelPermutationCount = new long[n];
long[] oVowelPermutationCount = new long[n];
long[] uVowelPermutationCount = new long[n];
aVowelPermutationCount[0] = 1L;
eVowelPermutationCount[0] = 1L;
iVowelPermutationCount[0] = 1L;
oVowelPermutationCount[0] = 1L;
uVowelPermutationCount[0] = 1L;
int MOD = 1000000007;
for (int i = 1; i < n; i++) {
aVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1] + uVowelPermutationCount[i - 1]) % MOD;
eVowelPermutationCount[i] = (aVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1]) % MOD;
iVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
oVowelPermutationCount[i] = iVowelPermutationCount[i - 1] % MOD;
uVowelPermutationCount[i] = (iVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
}
long result = 0L;
result = (aVowelPermutationCount[n - 1] + eVowelPermutationCount[n - 1] + iVowelPermutationCount[n - 1] + oVowelPermutationCount[n - 1] + uVowelPermutationCount[n - 1]) % MOD;
return (int)result;
}
}6 520
⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти
Вот отсортированная база с тонной материала (постепенно пополняется):
(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR
Скачивать ничего не нужно — все выложили в Telegram
6 520
Задача: 736. Parse Lisp Expression
Сложность: hard
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output: 14👨💻 Алгоритм: 1⃣Определите функцию для оценки выражений. 2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных). 3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости. 😎 Решение:
import java.util.*;
public class Solution {
public int evaluate(String expression) {
return evaluate(expression, new HashMap<>());
}
private int evaluate(String expression, Map<String, Integer> env) {
if (!expression.startsWith("(")) {
if (Character.isDigit(expression.charAt(0)) || expression.charAt(0) == '-') {
return Integer.parseInt(expression);
}
return env.get(expression);
}
List<String> tokens = tokenize(expression);
if (tokens.get(0).equals("let")) {
for (int i = 1; i < tokens.size() - 2; i += 2) {
env.put(tokens.get(i), evaluate(tokens.get(i + 1), env));
}
return evaluate(tokens.get(tokens.size() - 1), env);
} else if (tokens.get(0).equals("add")) {
return evaluate(tokens.get(1), env) + evaluate(tokens.get(2), env);
} else if (tokens.get(0).equals("mult")) {
return evaluate(tokens.get(1), env) * evaluate(tokens.get(2), env);
}
return 0;
}
private List<String> tokenize(String expression) {
List<String> tokens = new ArrayList<>();
StringBuilder token = new StringBuilder();
int parens = 0;
for (char c : expression.toCharArray()) {
if (c == '(') {
parens++;
if (parens == 1) continue;
} else if (c == ')') {
parens--;
if (parens == 0) {
tokens.addAll(tokenize(token.toString()));
token = new StringBuilder();
continue;
}
} else if (c == ' ' && parens == 1) {
if (token.length() > 0) {
tokens.add(token.toString());
token = new StringBuilder();
}
continue;
}
token.append(c);
}
if (token.length() > 0) {
tokens.add(token.toString());
}
return tokens;
}
}6 520
Задача: 42. Trapping Rain Water
Сложность: hard
Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя.
Пример:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6👨💻 Алгоритм: 1⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max. 2⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max. 3⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans. 😎 Решение:
class Solution {
public int trap(int[] height) {
if (height.length == 0) return 0;
int ans = 0;
int size = height.length;
int[] left_max = new int[size];
int[] right_max = new int[size];
left_max[0] = height[0];
for (int i = 1; i < size; i++) {
left_max[i] = Math.max(height[i], left_max[i - 1]);
}
right_max[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--) {
right_max[i] = Math.max(height[i], right_max[i + 1]);
}
for (int i = 1; i < size - 1; i++) {
ans += Math.min(left_max[i], right_max[i]) - height[i];
}
return ans;
}
}6 520
Как начать зарабатывать на дизайне без опыта и связей
Забери пошаговый план, как без опыта и связей зарабатывать на дизайне уже через 60 дней по методу обратной интеграции
✅ Без постоянного поиска клиентов
✅ Без бирж и фриланс-площадок
✅ Без продаж и ненужных звонков
✅ И без копеечных заказов по 300 ₽
Бонусы на 100 000 ₽ только для участников:
3 практических курса по Figma, гайды и чек-листы для быстрого старта
Закрытая встреча с арт-директором ТОП3 дизайн студии РФ
Узнай, как с нуля получать реальные заказы и выйти на стабильный доход
Попробовать
#реклама 16+
study.logomachine.ru
О рекламодателе
6 520
Задача: 1360. Number of Days Between Two Dates
Сложность: easy
Напишите программу для подсчета количества дней между двумя датами.
Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.
Пример:
Input: date1 = "2019-06-29", date2 = "2019-06-30" Output: 1👨💻 Алгоритм: 1⃣Преобразование строк в даты: Используйте встроенные функции для преобразования строковых представлений дат в объекты дат. 2⃣Вычисление разницы в днях: Вычислите разницу между двумя объектами дат в днях. 3⃣Возвращение результата: Верните абсолютное значение разницы в днях для получения положительного числа. 😎 Решение:
import java.time.LocalDate;
import java.time.temporal.ChronoUnit;
public class Solution {
public int daysBetweenDates(String date1, String date2) {
LocalDate d1 = LocalDate.parse(date1);
LocalDate d2 = LocalDate.parse(date2);
return (int) Math.abs(ChronoUnit.DAYS.between(d1, d2));
}
}6 520
Задача: 354. Russian Doll Envelopes
Сложность: hard
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).👨💻 Алгоритм: 1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте). 2⃣Извлеките вторую размерность (высоты) отсортированного массива. 3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот. 😎 Решение:
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
if (arr1[0] == arr2[0]) {
return arr2[1] - arr1[1];
} else {
return arr1[0] - arr2[0];
}
}
});
int[] secondDim = new int[envelopes.length];
for (int i = 0; i < envelopes.length; ++i) secondDim[i] = envelopes[i][1];
return lengthOfLIS(secondDim);
}
}6 520
Задача: 370. Range Addition
Сложность: medium
Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].
У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.
Верните arr после применения всех обновлений.
Пример:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]👨💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:
public int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
for (int[] update : updates) {
int start = update[0], end = update[1], val = update[2];
result[start] += val;
if (end + 1 < length) {
result[end + 1] -= val;
}
}
for (int i = 1; i < length; i++) {
result[i] += result[i - 1];
}
return result;
}6 520
Задача: 687. Longest Univalue Path
Сложность: medium
Дано корень бинарного дерева, верните длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить.
Длина пути между двумя узлами представлена количеством рёбер между ними.
Пример:
Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).class Solution {
private int ans = 0;
private int solve(TreeNode root, int parent) {
if (root == null) {
return 0;
}
int left = solve(root.left, root.val);
int right = solve(root.right, root.val);
ans = Math.max(ans, left + right);
return root.val == parent ? Math.max(left, right) + 1 : 0;
}
public int longestUnivaluePath(TreeNode root) {
solve(root, -1);
return ans;
}
}6 520
Задача: 622. Design Circular Queue
Сложность: medium
Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.
Пример:
Input ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4]👨💻 Алгоритм: 1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди. 2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу. 3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди. 😎 Решение:
public class MyCircularQueue {
private int[] queue;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularQueue(int k) {
this.queue = new int[k];
this.front = 0;
this.rear = -1;
this.size = 0;
this.capacity = k;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : queue[front];
}
public int Rear() {
return isEmpty() ? -1 : queue[rear];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}6 520
Repost from easyoffer
База 1000+ реальных собеседований теперь встроена в easyoffer
Смотрите, как другие кандидаты отвечают на вопросы, решают задачи и проходят этапы на реальных собеседованиях от топовых компаний. Подготовьтесь к своему собеседованию с двойной уверенностью.
Напоминаем, что сегодня последний день Чёрной Пятницы
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/
6 520
Задача: 113. Path Sum II
Сложность: medium
Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.
Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22👨💻 Алгоритм: 1⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке. 2⃣Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен. 3⃣Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути. 😎 Решение:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private void recurseTree(
TreeNode node,
int remainingSum,
List<Integer> pathNodes,
List<List<Integer>> pathsList
) {
if (node == null) {
return;
}
pathNodes.add(node.val);
if (remainingSum == node.val && node.left == null && node.right == null) {
pathsList.add(new ArrayList<>(pathNodes));
} else {
this.recurseTree(
node.left,
remainingSum - node.val,
pathNodes,
pathsList
);
this.recurseTree(
node.right,
remainingSum - node.val,
pathNodes,
pathsList
);
}
pathNodes.remove(pathNodes.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> pathsList = new ArrayList<>();
List<Integer> pathNodes = new ArrayList<>();
this.recurseTree(root, sum, pathNodes, pathsList);
return pathsList;
}
}6 520
Задача: 1021. Remove Outermost Parentheses
Сложность: easy
Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.
Пример:
Input: s = "(()())(())" Output: "()()()"👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения результата. Используйте счетчик для отслеживания уровня вложенности скобок.. 2⃣Обработка строки: Итерируйте по каждому символу строки. Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат. Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат. 3⃣Возврат результата: Верните результат, содержащий строку без крайних скобок из каждой примитивной строки. 😎 Решение:
public class Solution {
public String removeOuterParentheses(String s) {
StringBuilder result = new StringBuilder();
int level = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
if (level > 0) {
result.append(c);
}
level++;
} else {
level--;
if (level > 0) {
result.append(c);
}
}
}
return result.toString();
}
}6 520
Задача: 752. Open the Lock
Сложность: medium
Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.
Пример:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6👨💻 Алгоритм: 1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния. 2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное. 3⃣Если очередь пуста и целевое состояние не найдено, верните -1. 😎 Решение:
import java.util.*;
public class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Queue<String> queue = new LinkedList<>();
queue.offer("0000");
Set<String> visited = new HashSet<>();
visited.add("0000");
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String node = queue.poll();
if (node.equals(target)) {
return steps;
}
if (dead.contains(node)) {
continue;
}
for (String neighbor : neighbors(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
steps++;
}
return -1;
}
private List<String> neighbors(String node) {
List<String> res = new ArrayList<>();
char[] nodeArray = node.toCharArray();
for (int i = 0; i < 4; i++) {
char original = nodeArray[i];
nodeArray[i] = original == '9' ? '0' : (char) (original + 1);
res.add(new String(nodeArray));
nodeArray[i] = original == '0' ? '9' : (char) (original - 1);
res.add(new String(nodeArray));
nodeArray[i] = original;
}
return res;
}
}6 520
Задача: №18. 4Sum
Сложность: medium
Учитывая массив nums из n целых чисел, верните все уникальные четверки [nums[a], nums[b], nums[c], nums[d]], такие что:
- 0 <= a, b, c, d < n
- a, b, c и d различны
- nums[a] + nums[b] + nums[c] + nums[d] == target
Ответ можно вернуть в любом порядке.
Пример:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]👨💻 Алгоритм: 1⃣Отсортировать массив
nums.
2⃣Использовать рекурсивную функцию kSum, которая решает задачу обобщённо для любого k (в данном случае — k = 4), уменьшая её до задачи двух указателей (2Sum).
3⃣Внутри kSum, если k == 2, используем два указателя и ищем пары чисел с нужной суммой. Если k > 2, рекурсивно вызываем kSum для k - 1, сдвигая индекс и уменьшая целевую сумму.
😎 Решение:
public class Solution {
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<>();
if (index >= len) {
return res;
}
if (k == 2) {
int i = index, j = len - 1;
while (i < j) {
if (target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target - nums[i]);
res.add(temp);
while (i < j && nums[i] == nums[i + 1]) i++;
while (i < j && nums[j - 1] == nums[j]) j--;
i++;
j--;
} else if (target - nums[i] > nums[j]) {
i++;
} else {
j--;
}
}
} else {
for (int i = index; i < len - k + 1; i++) {
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
if (temp != null) {
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
while (i < len - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return res;
}
}6 520
Repost from easyoffer
Черная пятница на easyoffer
Скидка 70% на PRO до 29 ноября.
👉 https://easyoffer.ru/
6 520
Задача: 930. Binary Subarrays With Sum
Сложность: medium
Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.
Пример:
Input: nums = [1,0,1,0,1], goal = 2 Output: 4👨💻 Алгоритм: 1⃣Использовать словарь для хранения количества встреченных сумм префиксов. Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями. 2⃣Пройти по массиву и обновить текущую сумму. Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов. Обновить словарь префиксных сумм. 3⃣Вернуть счетчик подмассивов. 😎 Решение:
import java.util.HashMap;
import java.util.Map;
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1);
int currentSum = 0;
int count = 0;
for (int num : nums) {
currentSum += num;
count += prefixSumCount.getOrDefault(currentSum - goal, 0);
prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
return count;
}
}6 520
Дизайн в FIGMA с нуля. Бесплатный курс + портфолио
Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб.
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
