✅ Решение задачи 76

Time: O(n)
Space: O(1)

📝 Идея
▫️ С помощью правого указателя находим окно, в котором содержатся все символы из строки t, далее левым указателем сужаем окно для минимального ответа
▫️Эффективно искать минимальное окно нам помогает массив, в котором мы храним частоту символов

#solution76

✅ Как и любая hard-задача, данная не стала исключением и породила множество неэффективных и сложных решений.
Однако это решение крайне быстрое и простое, что показывает и статистика на LeetCode

🟢 Easy
206. Reverse Linked List

Класс ListNode:

public class ListNode { 
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { 
        this.val = val; 
    }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

Подсказка: сохраняйте предыдущий и следующий узел

29/200
#easy
#leetcode206

🟢 Easy
21. Merge Two Sorted Lists

📃 Вам даны заголовки двух отсортированных связанных списков list1и list2.
Объедините два списка в один отсортированный список.

Подсказка: в новый узел сохраняйте наименьший из двух списков

30/200
#easy
#leetcode21

✅ Решение задачи 21

Time: O(n)
Space: O(1)

📝 Идея
▫️Создаем новый корень двух списков и текущий узел
▫️Проходимся по двум спискам, сохраняя наименьший из узлов
▫️В конце останется непустым один из списков, поэтому сохраняем на него ссылку

#solution21

🟡 Medium
19. Remove Nth Node From End of List

📃 Дан связанный список, удалить n-ый с конца узел

Подсказка: используйте два указателя и сдвиньте один из них на n вперед

31/200
#medium
#leetcode19

✅ Решение задачи 19

Time: O(n)
Space: O(1)

📝 Идея
▫️Указатель right сдвигаем на n вперед, а left инициализируем левее head
▫️Теперь при простой итерации до момента, когда right окажется за пределами списка, left будет находиться как раз на позиции (n+1) c конца
▫️Остается только изменить ссылку на следующий узел ссылкой через один, тем самым удалив n-ый узел с конца

#solution19

🟡 Medium
33. Search in Rotated Sorted Array

📃 Массив nums отсортирован по возрастанию и имеет различные значения, но при этом возможен поворот (как здесь)
Вернуть индекс target, если он находится в nums и -1, если нет

Необходимо написать алгоритм, который работает за O(log(n))

Подсказка: используйте бинарный поиск, проверяя значения элементов nums[l] и nums[mid] для правильного перемещения указателей

32/200
#medium
#leetcode33

✅ Решение задачи 33

Time: O(log(n))
Space: O(1)

📝 Идея
▫️Используем бинарный поиск, при этом проверяя значение элемента под индексом mid:
- если nums[l] <= nums[mid], значит мы находимся на отсортированной части массива без поворотов
- если нет, значит мы находимся на отрезке, где значения в левой части больше центральных
▫️Исходя из позиции, кроме обычных проверок бинарного поиска, также проверяем отношение target к указателям, чтобы передвигать mid к элементам ближе по значению к target

#solution33

🔴 Hard
4. Median of Two Sorted Arrays

📃 Даны два отсортированных массива nums1 и nums2 размером m и n, вернуть медиану двух отсортированных массивов

Необходимо написать алгоритм, который работает за O(log(m+n))

Подсказка: используйте бинарный поиск по меньшему из массивов, чтобы найти левую часть соединенных массивов

33/200
#hard
#leetcode4

✅ Решение задачи 4

Time: O(log(min(n, m)))
Space: O(1)

📝 Идея
▫️Используя бинарный поиск по меньшему из массивов, находим такой элемент, который при соединении двух массивов будет являться серединой
Для этого должны выполняться условия:
- максимальный элемент из левой части отрезка nums1 должен быть меньше минимального элемента из правой части отрезка nums2 и также наоборот, тогда два массива разделены правильно на две части
▫️Присвоение максимальных и минимальных значений используем для того, чтобы логика алгоритма не рушилась, если mid оказался за пределами массива

#solution4

🟡 Medium
143. Reorder List

Подсказка: найдите середину списка и переверните его вторую часть

34/200
#medium
#leetcode143

✅ Решение задачи 143

Time: O(n)
Space: O(1)

📝 Идея
▫️С помощью двух указателей slow и fast находим середину списка
▫️Переворачиваем вторую часть списка знакомым алгоритмом
▫️Теперь остается только последовательно брать элементы из первой части списка и из перевернутой второй

#solution143

🟢 Easy
141. Linked List Cycle

📃 Дан связанный список, определите есть ли в нем цикл, используя O(1) памяти

Подсказка: используйте два указателя

35/200
#easy
#leetcode141

✅ Решение задачи 141

Time: O(n)
Space: O(1)

📝 Идея
▫️Используем два указателя slow и fast:
- slow сдвигаем на одну позицию вперед
- fast сдвигаем на две позиции вперед
▫️Если в списке есть цикл, то они обязательно в один момент встретятся

#solution141

🟡 Medium
2. Add Two Numbers

📃 Даны два непустых связанных списка, представляющих неотрицательные целые числа. Цифры хранятся в обратном порядке, и каждый из узлов содержит одну цифру.
Сложите два числа и верните сумму в виде связанного списка

Подсказка: реализуйте обычное сложение столбиком

36/200
#medium
#leetcode2

✅ Решение задачи 2

Time: O(n)
Space: O(1)

📝 Идея
▫️Так как списки уже даны в обратном порядке, удобно реализовать обычное сложение столбиком
▫️Если при сложении двух цифр сумма оказалась больше 10, запоминаем единицу и используем ее дальше

#solution2

🟡 Medium
287. Find the Duplicate Number

📃 Дан массив целых чисел, содержащий n + 1 целые числа, где каждое целое число находится в диапазоне [1, n] включительно.

В массиве есть только одно повторяющееся число, верните его

Необходимо решить задачу, не изменяя массив и используя только O(1) память

Подсказка: задача сводится к нахождению цикла, как в связанном списке

37/200
#medium
#leetcode287

✅ Решение задачи 287

Time: O(n)
Space: O(1)

📝 Идея
▫️Используем два указателя: slow передвигаем на 1 позицию вперед, fast — на две
▫️Теперь, когда знаем их точку пересечения — запускаем новый указатель с начала массива и также передвигаем на одну позицию одновременно со slow
▫️Данный алгоритм всегда будет указывать на элемент, в котором образуется цикл

#solution287