Нахождение всех анаграмм в строке

Сложность: Средняя

Условие задачи: даны две строки s и p, надо вернуть все индексы стартовых позиций, с которых начинаются анаграммы внутри строки s.

Анаграмма - строка, составленная путём перестановок букв из какого либо базового набора.

Пример:

Ввод: s = "cbaebabacd", p = "abc"
Вывод: [0,6]

Объяснение:
Подстрока "cba" начинается с индекса 0, она является анаграммой строки "abc".
Подстрока "bac" начинается с индекса 6, она является анаграммой строки "abc".

Ввод: s = "abab", p = "ab"
Вывод: [0,1,2]

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

Топ k-наиболее часто встречающихся слов

Сложность: Средняя

Условие задачи: дан массив строк, необходимо вернуть k-наиболее частых элементов.

При одинаковом количестве появлений нескольких слов, необходимо отсортировать данные слова в лексикографическом порядке.

Пример:

Ввод:
words = ["i","love","leetcode","i","love","coding"],
k = 2
Вывод: ["i","love"]

Объяснение: "i" и "love" два наиболее частых слова.
Но заметим, что "i" идет первее, чем "love" как раз-таки из-за алфавитного порядка.

Ввод: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Вывод: ["the","is","sunny","day"]

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

Сместить массив

Сложность: Средняя

Условие задачи: дан массив, необходимо сместить массив на k-элементов, где k - неотрицательное число.

Пример:

Ввод: nums = [1,2,3,4,5,6,7], k = 3
Вывод: [5,6,7,1,2,3,4]

Ввод: nums = [-1,-100,3,99], k = 2
Вывод: [3,99,-1,-100]

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

Сдвиг нулей

Сложность: Лёгкая

Условие задачи: дан массив, необходимо переместить все нулевые элементы к концу массива, к его правой границе.

Решение должно изменять исходный массив, не используя дополнительной памяти.

Пример:

Ввод: nums = [0,1,0,3,12]
Вывод: [1,3,12,0,0]

Ввод: nums = [0]
Вывод: [0]

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

Swap Adjacent in LR String

Сложность задачи: Средняя

Условие задачи:
В строке, состоящей из символов «L», «R» и «X», например «RXXLRXRXL», перемещение состоит либо в замене одного вхождения «XL» на «LX», либо в замене одного вхождения «RX» на "ХР". Учитывая начальную строку и конец конечной строки, вернуть True тогда и только тогда, когда существует последовательность ходов для преобразования одной строки в другую.

Пример:
Ввод: start = "RXXLRXRXL", end = "XRLXXRRLX"
Вывод: true
Объяснение: Мы можем преобразовать начало в конец, выполнив следующие шаги:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Ввод: start = "X", end = "L"
Вывод: false

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

Самая длинная подстрока без повторений

Сложность: Средняя.

Условие задачи: дана строка надо найти самую длинную подстроку, в которой не будет повторений.

Пример:

Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: ответом является подстрока "abc", длина которой равна 3.

Ввод: s = "bbbbb"
Вывод: 1

Ввод: s = "pwwkew"
Вывод: 3
Объяснение: ответ - "wke" (длина = 3).

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

Бинарный поиск

Сложность: Лёгкая

Условие задачи: дан целочисленный массив, отсортированный в порядке возрастания. Необходимо найти индекс target-значения. Если целевое значение отсутствует - нужно вернуть -1.

Пример:

Ввод: nums = [-1,0,3,5,9,12], target = 9
Вывод: 4

Ввод: nums = [-1,0,3,5,9,12], target = 2
Вывод: -1

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

Пересечение двух массивов II

Сложность: Лёгкая

Условие задачи: даны два целочисленных массива, необходимо вернуть все элементы, встречающиеся в каждом из них. Ответ может быть возвращен в любом порядке.

Пример:

Ввод: nums1 = [1,2,2,1], nums2 = [2,2]
Вывод: [2,2]

Ввод: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Вывод: [4,9] или [9,4]

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

Изменение порядка следования элементов связного списка

Сложность: Средняя

Условие задачи : дан связный список:
L0 → L1 → … → Ln - 1 → Ln.

Надо переопределить порядок следования элементов на следующий:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Пример:

Ввод: head = [1,2,3,4]
Вывод: [1,4,2,3]

Ввод: [1,2,3,4,5]
Вывод: [1,5,2,4,3]

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

Середина связного списка

Сложность: Лёгкая

Условие задачи: дан связный список. Необходимо вернуть указатель на серединный элемент исходного списка.

Пример:

Ввод: head = [1,2,3,4,5]
Вывод: [3,4,5]
Объяснение: серединный узел - узел 3.

Ввод: head = [1,2,3,4,5,6]
Вывод: [4,5,6]
Объяснение: лист имеет два серединных значения: 3 и 4, мы возвращаем второй.

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

Реализация класса MinStack

Сложность: Средняя

Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:

- void push(int val), который добавляет элемент в стак;
- void pop(), удаляющий верхний элемент стака;
- int top(), возвращающий верхний элемент на стаке;
- int getMin(), возвращающий минимальный элемент в стаке на момент вызова метода.

Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).

Пример:

Ввод:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Вывод:
[null,null,null,null,-3,null,0,-2]

Объяснение:

MinStack minStack = новый объект класса MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

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

Перестановки, зависящие от регистра символа

Сложность: Средняя

Условие задачи: дана строка, содержащая как цифры, так и буквы. Надо вернуть всевозможные варианты перестановок строки, изменяя регистр букв.

Пример:

Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]

Ввод: s = "3z4"
Вывод: ["3z4","3Z4"]

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

Треугольник

Сложность: Средняя

Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на i-ой позиции можно перемещаться на i-ую или i+1 позицию следующего ряда.

Пример:
Ввод: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Вывод: 11

Объяснение: треуголльник выглядит следующим образом:

2
3 4
6 5 7
4 1 8 3

Минимальный путь выглядит следующим образом: 2 + 3 + 5 + 1 = 11.

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

Мокрые бандиты

Сложность: Средняя

Условие задачи: Мы - профессиональные грабители, обчищающие дома под Рождество и в каждом ограбленном нами доме оставляем характерный символ: невыключенный кран с водой.

Перед нами стоит задача: ограбить на максимальную сумму дома, находящиеся на проспекте Линкольна, но у данных домов есть характерная черта: при ограбление соседних домов срабатывает сигнализация, вызывающая полицию.

Нам необходимо выяснить какие дома надо ограбить, чтобы получить максимальный куш.

Пример:

Ввод: nums = [1,2,3,1]
Вывод: 4

Объяснение: Грабим 1-ый дом (money = 1), а после навещаем 3-ий дом (money = 3).
Суммарный куш: 1 + 3 = 4.

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

Максимальная площадь острова

Сложность: Средняя

Условие задачи: Условие задачи: дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Требуется опеределить максмимальную площадь острова из островов, расположенных на карте.

Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.


Пример:

Ввод: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Вывод: 6

Ввод: grid = [[0,0,0,0,0,0,0,0]]
Вывод: 0

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

Двумерный бинарный поиск

Сложность: Средняя

Условие задачи: данна 2-мерная матрица чисел, в которой числа упорядочены по возрастанию сверху-вниз и слева-направо. Надо определить, есть ли в матрице целевое значение.

Пример:

Ввод: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Вывод: True

Ввод: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Вывод: Fasle

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

Максимальный подмассив

Сложность: Средняя

Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.

Подмассивом называется последовательная часть исходного массива.

Пример:

Ввод: nums = [-2,1,-3,4,-1,2,1,-5,4]
Вывод: 6

Объяснение: 4,-1,2,1] имеет наибольшую сумму 6.

Ввод: nums = [5,4,-1,7,8]
Вывод: 23

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

Скобочная пунктуация

Сложность: Лёгкая

Условие задачи: дана строка, содержащая в себе только символы: '(', ')', '{', '}', '[', ']'. Надо выполнить проверку на то, корректно ли открыты и закрыты все скобки.

Пример:

Ввод: s = "()"
Вывод: True

Ввод: s = "()[]{}"
Вывод: True

Ввод: s = "(]"
Вывод: False

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

Комбинации

Сложность: Средняя

Условие задачи: даны два целых положительных числа n и k. Надо вывести все комибинации, состоящие из k-чисел в диапазоне [1, n].

Пример:

Ввод: n = 4, k = 2
Вывод:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Объяснение: число перестановок равно 6. Важным моментом является неупорядоченность чисел внутри самих комбинаций, то есть пары [1,2] и [2,1] являются одинаковыми.

Ввод: n = 1, k = 1
Вывод: [[1]]

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

Проверка бинарного дерева

Сложность: Средняя

Условие задачи: требуется проверить является ли исходное дерево бинарным деревом поиска.

Правильное бинарное дерево удовлетворяет следующим условиям:
- элементы левого поддеревоа должно быть меньше родителя.
- элементы правого поддерева должны быть больше, чем значение в родительском узле.
- левое и правое поддеревья должны быть также бинарными деревьями поиска.

Пример:

Ввод: root = [5,1,4,null,null,3,6]
Вывод: False
Объяснение: 4 < 5, но при этом находится в правом поддереве.

Ввод: root = [2,1,3]
Вывод: True

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

Сцепка бинарного дерева

Сложность: Средняя

Условие задачи: дано бинарное дерево, необходимо вернуть элементы данного дерева, находящиеся на одном уровне.

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [[3],[9,20],[15,7]]
Объяснение:

Ввод: root = [1]
Вывод: [[1]]

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