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

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

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

Пример:

Ввод: 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]]

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

Изъятие дубликатов из односвязного списка

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

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

Пример:

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

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

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

Перенос каждого указателя вправо

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

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

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

Пример:

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

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

Вставка в бинарное дерево

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

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

Может существовать несколько возможных вариантов вставок. Необходимо вернуть любой из них.

Пример:

Ввод: root = [4,2,7,1,3], val = 5
Вывод: [4,2,7,1,3,5]

Объяснение: другой вариант -[5,2,7,1,3,4]


Ввод: root = [40,20,60,10,30,50,70], val = 25
Вывод: [40,20,60,10,30,50,70,null,null,25]

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

Быки и коровы

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

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

Быки - правильные цифры, находящиеся на нужных позициях.

Коровы - правильные числа, но находящиеся на соответствующих позициях.

Задача - выдать подсказку в формате "xAyB", где x - количество быков, y - количество коров.

Пример:

Ввод: secret = "1807", guess = "7810"
Вывод: "1A3B"
Объяснение:

Ввод: secret = "1123", guess = "0111"
Вывод: "1A1B"

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

Петля в связном списке II

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

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

Пример:

Ввод: head = [3,2,0,-4], pos = 1
Вывод: последний элемент зацикливается на элементе с индексом
1*.

* соответствующий список проиллюстрирован на картинке.

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

Расшифровка строки

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

Условие задачи: дана строка в формате: k[encoded_string], где k - число повторений зашифрованной строки. Необходимо вывести результирующую строку, которая соответствует расшифровке исходной строки.

Пример:

Ввод: s = "3[a]2[bc]"
Вывод: "aaabcbc"

Ввод: s = "3[a2[c]]"
Вывод: "accaccacc"

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

Перебор регистра букв

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

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

Пример:

Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]
Объяснение:

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

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

Переспелые апельсины

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

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

Каждую минуту апельсины, находящие рядом (сверху, слева, снизу, вправа) с переспевшими - становятся переспевшими.

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

Пример:

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

Ввод: grid = [[2,1,1],[0,1,1],[1,0,1]]
Вывод: -1
Объяснение: переспевший фрукт не контактирует со спелыми плодами.

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

Слияние двух отсортированных массивов

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

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

Надо свзать оба массива в один в порядке неубывания.

Результирующий массив должен содержаться в массиве nums1.

Пример:

Ввод: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]

Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]

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