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 654
Obunachilar
+124 soatlar
-107 kunlar
-4930 kunlar
Postlar arxiv
6 653
🔥 Один в поле не воин, поэтому топовый программист должен находится в топ команде.
🧑💻 Марк Цукерберг создал первоначальную версию Facebook в одиночку, но для превращения стартапа в глобальную социальную сеть потребовалась мощная команда.
👌 IT мероприятия - одно из тех мест, где можно найти единомышленников в данной нише.
🔥 Подпишись на канал IT события, чтобы не упустить возможность в реализации своего потенциала.
6 653
#easy
Задача: 157. Read N Characters Given Read4
Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов.
Метод read4:
API read4 читает четыре последовательных символа из файла, затем записывает эти символы в массив буфера buf4.
Возвращаемое значение — количество фактически прочитанных символов.
Обратите внимание, что у read4 есть собственный указатель файла, аналогично FILE *fp в C.
Определение read4:
Параметр: char[] buf4
Возвращает: int
buf4[] — это назначение, а не источник. Результаты из read4 будут скопированы в buf4[].
Метод read:
Используя метод read4, реализуйте метод read, который читает n символов из файла и сохраняет их в массиве буфера buf. Учтите, что вы не можете напрямую манипулировать файлом.
Возвращаемое значение — количество фактически прочитанных символов.
Определение read:
Параметры: char[] buf, int n
Возвращает: int
buf[] — это назначение, а не источник. Вам нужно будет записать результаты в buf[].
Примечание:
Учтите, что вы не можете напрямую манипулировать файлом. Файл доступен только для чтения с помощью read4, но не для read.
Функция read будет вызываться только один раз для каждого тестового случая.
Вы можете предполагать, что массив буфера назначения, buf, гарантированно имеет достаточно места для хранения n символов.
Пример:
Input: file = "abc", n = 4 Output: 3 Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.👨💻 Алгоритм: 1️⃣Инициализация и подготовка: Инициализируйте переменные: copiedChars = 0 для подсчета скопированных символов и readChars = 4 для подсчета прочитанных символов из файла. Начальное значение readChars установлено в 4, что позволяет использовать условие readChars != 4 в качестве маркера конца файла (EOF). Создайте внутренний буфер из 4 символов: buf4. 2️⃣Чтение и копирование символов: Пока количество скопированных символов меньше N (copiedChars < n) и еще есть символы в файле (readChars == 4): Прочитайте символы из файла во внутренний буфер buf4 с помощью метода read4(buf4). Копируйте символы из внутреннего буфера buf4 в основной буфер buf по одному. Увеличивайте copiedChars после каждого скопированного символа. 3️⃣Завершение процесса: Если количество скопированных символов достигло N (copiedChars == n), прервите процесс копирования. Верните copiedChars как результат функции, указывающий на количество успешно скопированных символов в основной буфер buf. 😎 Решение:
public class Solution extends Reader4 {
public int read(char[] buf, int n) {
int copiedChars = 0, readChars = 4;
char[] buf4 = new char[4];
while (copiedChars < n && readChars == 4) {
readChars = read4(buf4);
for (int i = 0; i < readChars; ++i) {
if (copiedChars == n) return copiedChars;
buf[copiedChars] = buf4[i];
++copiedChars;
}
}
return copiedChars;
}
}6 653
#medium
Задача: 155. Min Stack
Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.
Пример:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2class MinStack {
private Stack<int[]> stack = new Stack<>();
public MinStack() {}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(new int[] { x, x });
return;
}
int currentMin = stack.peek()[1];
stack.push(new int[] { x, Math.min(x, currentMin) });
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}6 653
#Hard
Задача: 154. Find Minimum in Rotated Sorted Array II
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:
[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива.
Необходимо максимально уменьшить количество операций.
Пример:
Input: nums = [1,3,5] Output: 1👨💻 Алгоритм: 1️⃣Сравнение с правой границей: В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]). 2️⃣Обновление указателей: Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid. Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid. Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента. . 3️⃣Итерация до сужения диапазона поиска: Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов. 😎 Решение:
class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) high = pivot;
else if (nums[pivot] > nums[high]) low = pivot + 1;
else high -= 1;
}
return nums[low];
}
}6 653
#Medium
Задача: 153. Find Minimum in Rotated Sorted Array
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.👨💻 Алгоритм: 1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. . 3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:
class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int left = 0, right = nums.length - 1;
if (nums[right] > nums[0]) {
return nums[0];
}
while (right >= left) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
if (nums[mid] > nums[0]) {
left = mid + 1;
} else {
}
}
return Integer.MAX_VALUE;
}
}6 653
🔥 Один в поле не воин, поэтому топовый программист должен находится в топ команде.
🧑💻 Марк Цукерберг создал первоначальную версию Facebook в одиночку, но для превращения стартапа в глобальную социальную сеть потребовалась мощная команда.
👌 IT мероприятия - одно из тех мест, где можно найти единомышленников в данной нише.
🔥 Подпишись на канал IT события, чтобы не упустить возможность в реализации своего потенциала.
6 653
#Medium
Задача: 152. Maximum Product Subarray
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.👨💻 Алгоритм: 1️⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения. 2️⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив. . 3️⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result. 😎 Решение:
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int result = nums[0];
for (int i = 0; i < nums.length; i++) {
int accu = 1;
for (int j = i; j < nums.length; j++) {
accu *= nums[j];
result = Math.max(result, accu);
}
}
return result;
}
}6 653
+6
📣 Создайте идеальную квартиру – от идеи до полной готовности!
RE Design Buro – более 15 лет разрабатывают дизайн, проводят ремонт и полностью комплектуют квартиры. ⭐️
🏆 450+ успешных проектов в Москве и в области
⭐️ Полный цикл работ: от разработки дизайн-проекта до полного завершения ремонта, уборки и подбора всех необходимых элементов.
⭐️ Работают узкие специалисты, а не бригады: плиточники, электрики, сантехники и другие.
⭐️ Средний срок ремонта – 6 месяцев, чтобы вы могли скорее наслаждаться своей квартирой.
⭐️ Рейтинг выполненных ремонтов – 4.9.
⭐️ Фиксированные цены и сроки – никаких сюрпризов на пути к вашей идеальной квартире.
⭐️ Оплата частями по факту выполнения работ, чтобы вы могли спокойно планировать бюджет.
🔥 Специальные условия для IT-специалистов!
👉 Выполненные работы
👉 Подписывайтесь на канал
👉 Бесплатная консультация дизайнера
👉 Получите расчет стоимости ремонта
6 653
#Medium
Задача: 151. Reverse Words in a String
Дана входная строка s, переверните порядок слов.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в строке s разделены как минимум одним пробелом.
Верните строку, в которой слова расположены в обратном порядке, соединённые одним пробелом.
Обратите внимание, что строка s может содержать пробелы в начале или в конце, или множественные пробелы между двумя словами. Возвращаемая строка должна содержать только один пробел, разделяющий слова. Не включайте лишние пробелы.
Пример:
Input: s = "the sky is blue" Output: "blue is sky the"👨💻 Алгоритм: 1️⃣Удаление лишних пробелов: Удалите начальные и конечные пробелы из строки s. Это делается для того, чтобы убрать пробелы в начале и в конце строки, которые могут исказить конечный результат. В коде это реализовано с помощью методов erase и find_first_not_of/find_last_not_of, которые удаляют пробелы до первого и после последнего непробельного символа. 2️⃣Разделение строки на слова: Преобразуйте строку s в поток и используйте istringstream для чтения слов, разделенных пробелами. Каждое слово определяется как последовательность символов, не содержащая пробелов. Слова сохраняются в вектор words. Это делается с помощью copy, который копирует слова из потока в words с помощью istream_iterator. . 3️⃣Реверсирование и соединение слов: Переверните вектор слов и соедините их обратно в одну строку, разделяя слова одним пробелом. Для реверсирования используется функция reverse, а для соединения слов — ostringstream вместе с ostream_iterator. Слова объединяются таким образом, что между ними находится только один пробел, исключая лишние пробелы между словами. 😎 Решение:
class Solution {
public String reverseWords(String s) {
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}6 653
Java Джуниоры! Важное объявление
FAANG School в течение 24 часов отдают бесплатно свою библиотеку знаний. Вы можете получить доступ:
– Подробный гайд, как найти работу в IT без опыта
– Подборка платформ с вакансиями для java-разработчиков
– Пошаговая RoadMap по Java
– Мануал по Docker. Основные команды и концепции
– Микросервисы. Вопросы с собеседований
– Шпаргалка с горячими клавишами JetBrains IDE. Ускоришь работу в 10 раз
– Desk setup. Подборка аксессуаров для комфортной работы
– Шпаргалка по Kafka
Библиотека знаний постоянно пополняется, но бесплатный доступ длится всего сутки. Чтобы получить полезные материалы, переходи по ссылке и жми на оранжевую кнопку.
6 653
#Medium
Задача: 150. Evaluate Reverse Polish Notation
Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации.
Вычислите это выражение. Верните целое число, которое представляет значение этого выражения.
Обратите внимание на следующие моменты:
Допустимые операторы: '+', '-', '*' и '/'.
Каждый операнд может быть целым числом или другим выражением.
Деление двух целых чисел всегда округляется к нулю.
Деление на ноль в выражении отсутствует.
Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации.
Ответ и все промежуточные вычисления можно представить 32-битным целым числом.
Пример:
Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9👨💻 Алгоритм: 1️⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n). 2️⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом. . 3️⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом. 😎 Решение:
class Solution {
private static final Map<
String,
BiFunction<Integer, Integer, Integer>
> OPERATIONS = new HashMap<>();
static {
OPERATIONS.put("+", (a, b) -> a + b);
OPERATIONS.put("-", (a, b) -> a - b);
OPERATIONS.put("*", (a, b) -> a * b);
OPERATIONS.put("/", (a, b) -> a / b);
}
public int evalRPN(String[] tokens) {
int currentPosition = 0;
int length = tokens.length; // We need to keep track of this ourselves.
while (length > 1) {
while (!OPERATIONS.containsKey(tokens[currentPosition])) {
currentPosition++;
}
String operation = tokens[currentPosition];
int number1 = Integer.parseInt(tokens[currentPosition - 2]);
int number2 = Integer.parseInt(tokens[currentPosition - 1]);
BiFunction<Integer, Integer, Integer> operator = OPERATIONS.get(
operation
);
int value = operator.apply(number1, number2);
tokens[currentPosition] = Integer.toString(value);
delete2AtIndex(tokens, currentPosition - 2, length);
currentPosition--;
length -= 2;
}
return Integer.parseInt(tokens[0]);
}
private void delete2AtIndex(String[] tokens, int d, int length) {
for (int i = d; i < length - 2; i++) {
tokens[i] = tokens[i + 2];
}
}
}6 653
#Hard
Задача: 149. Max Points on a Line
Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.
Пример:
Input: points = [[1,1],[2,2],[3,3]] Output: 3👨💻 Алгоритм: 1️⃣Итерация по всем точкам: Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов. 2️⃣Расчёт углов и подсчёт: Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу . 3️⃣Обновление ответа: Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ). 😎 Решение:
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n == 1) {
return 1;
}
int result = 2;
for (int i = 0; i < n; i++) {
Map<Double, Integer> cnt = new HashMap<>();
for (int j = 0; j < n; j++) {
if (j != i) {
cnt.merge(
Math.atan2(
points[j][1] - points[i][1],
points[j][0] - points[i][0]
),
1,
Integer::sum
);
}
}
result = Math.max(result, Collections.max(cnt.values()) + 1);
}
return result;
}
}6 653
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
6 653
#Medium
Задача: 148. Sort List
Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.
Пример:
Input: head = [4,2,1,3] Output: [1,2,3,4]👨💻 Алгоритм: 1️⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2️⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3️⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode mid = getMid(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode();
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 != null) ? list1 : list2;
return dummyHead.next;
}
ListNode getMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = (midPrev == null) ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}6 653
👩💻 Есть опыт в проге, но не растет зп? Может нужно найти крутой оффер?
🗿 Большинство IT специалистов работает за копейки и даже не осознает этого. Лучший способ понять рынок вакансий - стать его частью и начать анализировать.
👍 Предела совершенству нет, что нельзя сказать про зп в рамках одной компании. Подпишись на Мидл работает и повышай свой капитал.
6 653
#medium
Задача: 147. Insertion Sort List
Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка.
Шаги алгоритма сортировки вставками:
1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список.
2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда.
3. Процесс повторяется до тех пор, пока не закончатся входные элементы.
Пример:
Input: head = [4,2,1,3] Output: [1,2,3,4]👨💻 Алгоритм: 1️⃣Создание вспомогательного узла (pseudo_head): В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком. 2️⃣Механизм вставки узла: В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A. 3️⃣Использование пары указателей для вставки: Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка. 😎 Решение:
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode prev = dummy;
while (prev.next != null && prev.next.val <= curr.val) {
prev = prev.next;
}
ListNode next = curr.next;
curr.next = prev.next;
prev.next = curr;
curr = next;
}
return dummy.next;
}
}6 653
#medium
Задача: 146. LRU Cache
Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.
Функции get и put должны выполняться за среднее время O(1).
Пример:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]class ListNode {
int key;
int val;
ListNode next;
ListNode prev;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
int capacity;
Map<Integer, ListNode> dic;
ListNode head;
ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!dic.containsKey(key)) {
return -1;
}
ListNode node = dic.get(key);
remove(node);
add(node);
return node.val;
}
public void put(int key, int value) {
if (dic.containsKey(key)) {
ListNode oldNode = dic.get(key);
remove(oldNode);
}
ListNode node = new ListNode(key, value);
dic.put(key, node);
add(node);
if (dic.size() > capacity) {
ListNode nodeToDelete = head.next;
remove(nodeToDelete);
dic.remove(nodeToDelete.key);
}
}
public void add(ListNode node) {
ListNode previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
public void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}6 653
#easy
Задача: 145. Binary Tree Postorder Traversal
Дан корень бинарного дерева, верните обход значений узлов в постпорядке.
Пример:
Input: root = [1,null,2,3] Output: [3,2,1]👨💻 Алгоритм: 1️⃣Заполнение стека по стратегии право->узел->лево: Инициируйте стек и добавьте в него корень дерева. Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода. 2️⃣Извлечение узла из стека и проверка: Извлекайте последний узел из стека, проверяя, является ли он левым листом (узел без потомков). Если это так, добавьте значение узла в выходной список (массив значений). Если узел имеет потомков, продолжайте выполнение стека с добавлением дочерних узлов по той же стратегии. 3️⃣Повторение процесса до опустошения стека: Если извлеченный узел не является левым листом, необходимо обработать его потомков. Для этого, верните узел и его потомков в стек в правильном порядке, чтобы следующие итерации могли корректно обработать все узлы. Повторяйте процесс до тех пор, пока стек не опустеет, что означает завершение обхода всех узлов. 😎 Решение:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> output = new LinkedList();
Deque<TreeNode> stack = new ArrayDeque();
if (root == null) return output;
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
output.addFirst(root.val);
if (root.left != null) stack.push(root.left);
if (root.right != null) stack.push(root.right);
}
return output;
}
}6 653
🤬 Постоянные ошибки, как они надоели!
🤯 Планируя свои дела, мы забываем, что оборудование может подвести. Это может перекрыть все рабочие планы. Придется гуглить, смотреть видосы, звонить знакомым "Не встречалась ли тебе такая ошибка?"
🥵 Все это время и силы. Наша команда нашла этому решение - Битый код. Канал, который даст тебе базу в мире ошибок.
🍸 Стань тем человеком, к которому будут обращаться и про которого будут говорить "Он сможет помочь"
6 653
#easy
Задача: 144. Binary Tree Preorder Traversal
Дан корень бинарного дерева, верните предварительный обход значений его узлов.
Пример:
Input: root = [1,null,2,3] Output: [1,2,3]👨💻 Алгоритм: 1️⃣Определение структуры узла дерева: Определите класс TreeNode, который будет использоваться в реализации. Каждый узел TreeNode содержит значение и ссылки на левого и правого потомков. 2️⃣Инициализация процесса обхода: Начните обход с корневого узла дерева. Используйте стек для хранения узлов дерева, которые нужно обойти, начиная с корня. 3️⃣Итеративный обход дерева: На каждой итерации извлекайте текущий узел из стека и добавляйте его значение в выходной список. Сначала добавьте в стек правого потомка (если он существует), затем левого потомка (если он существует). Это гарантирует, что узлы будут обрабатываться в порядке слева направо, так как стек работает по принципу LIFO (последний пришел - первый ушел). Повторяйте процесс, пока стек не опустеет, что означает завершение обхода всех узлов. 😎 Решение:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return output;
}
}