Поиск в бинарном дереве

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

Условие задачи: дано бинарное дерево поиска и целевое значения для поиска.

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

Пример:

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

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

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

Количество возрастающих подпоследовательностей наибольшей длины

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

Условие задачи: дан массив целых чисел, надо посчитать количество возрастающих подпоследовательностей наибольшей длины. Подпоследовательность (ее элементы) должна строго возрастать.

Пример:

Ввод: nums = [1,3,5,4,7]
Вывод: 2
Объяснение: есть две возрастающие подпоследовательности одинаковой длины: [1, 3, 4, 7] и [1, 3, 5, 7]

Ввод: nums = [2,2,2,2,2]
Вывод: 5
Объяснение: в данном массиве есть 5 подпоследовательностей длины 1.

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

Диаметр бинарного дерева

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

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

Диаметр бинарного дерева - наибольшая длина между двумя любыми узлами в дереве (необязательно включая корневой элемент всего дерева).

Длина между двумя узлами дерева - количество ребер между ними.

Пример:

Ввод: root = [1,2,3,4,5]
Вывод: 3
Объяснение: длина пути [4,2,1,3] или пути [5,2,1,3].

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

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

Сравнение стёртых строк

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

Условие задачи: даны две строки, необходимо выяснить являются они идентичными после удаления символов путем использования клавиши backspace (символ #).

Если строка пустая, то backspace оставляет её пустой.

Пример:

Ввод: s = "ab#c", t = "ad#c"
Вывод: true
Объяснение: обе строки после использования удаления символов образуют сроку "ac"

Ввод: s = "ab##", t = "c#d#"
Вывод: true

Ввод: s = "a#c", t = "b"
Вывод: false

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

Тройная сумма

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

Условие задачи: дан целочисленный массив nums, вычислите все тройки [nums[i], nums[j], nums[k]] такие что i != j, i != k, и j != k, и nums[i] + nums[j] + nums[k] == 0.

Решение не должно содержать дубликатов.

Пример:

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

Объяснение: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
Но уникальные тройки - [-1,0,1] и [-1,-1,2].

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

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

Сумма по пути III

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

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

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

Пример:

Ввод: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Вывод: 3
Объяснение: *во вложении

Ввод: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Вывод: 3

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

Поиск в сдвинутом сортированном массиве

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

Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]])

Массив [0,1,2,4,5,6,7], имея опорный элемент 3, будет выглядеть следующим образом: [4,5,6,7,0,1,2].

Необходимо осуществить поиск целевого элемента в сдвинутом массиве, определив его индекс, или же вывести -1 при его отсутствии.

Решение должно быть за O(log n) по времени.

Пример:

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

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

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

Балансировка бинарного дерева

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

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

Для данной проблемы сбалансированным по высоте деревом является бинарное дерево, у которого для каждого родителя есть оба потомка, если потомки вообще имеются.

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: true

Ввод: root = [1,2,2,3,3,null,null,4,4]
Вывод: true

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

Городской судья

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

Условие задачи: в городе живёт n людей, проиндексированные с 1 до n. Пошел слух, что один из горожан является судьей.

Если в городе-таки имеется судья, то:

1. Судья никому не доверяет.
2. Каждый горожанин, за исключением судьи, доверяет судье.
3. Существует один и единственный человек, который удовлетворяет правилам 1 и 2.

На вход подается массив связей доверия между гражданами, где trust[i] = [ai, bi] обозначает, что ai доверяет жителю bi.

Вывести надо индекс судьи или же -1 в случае отсутствия такового среди жителей города.

Пример:

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

Ввод: n = 3, trust = [[1,3],[2,3],[3,1]]
Вывод: -1

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

Мост наименьшей длины

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

Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.

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

Можно изменить 0 на 1 для соединения двух островов в один.

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

Пример:

Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:

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

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

Минимальная глубина бинарного дерева

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

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

Глубина дерева - количество узлов от корня до ближайшего потомка.

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: 2

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

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

Римские цифры

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

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

Пример:

Ввод: s = "III"
Вывод: 3

Ввод: s = "LVIII"
Вывод: 58

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

Уникальные бинарные деревья поиска

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

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

Пример:

Ввод: n = 3
Вывод: 5
Объяснение:

Ввод: n = 1
Вывод: 1

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

Поедание бананов

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

Условие задачи: обезьяна Коко любит есть бананы. Есть n связок бананов, где i-ая связка содержит piles[i] бананов. Смотритель зоопарка же ушел и вернется через h часов.

Коко может поедать бананы с произвольной скоростью k бананов в час. Если в связке менее k бананов, она поедает всю связку и более в этот час не ест.

Коко кушает медленно, но уверенно: обезьяна нацелена на съедение всех бананов до возвращения смотрителя.

Необходимо вычислить минимальное число k, такое что все бананы будут съедены за h часов.

Пример:

Ввод: piles = [3,6,7,11], h = 8
Вывод: 4

Ввод: piles = [30,11,23,4,20], h = 5
Вывод: 30

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

Конвертация отсортированного массива в бинарное дерево поиска

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

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

Сбалансированное по высоте бинарное дерево - это бинарное дерево, глубина между потомками которого на каждом узле отличается не более чем на единицу.

Пример:

Ввод: nums = [-10,-3,0,5,9]
Вывод: [0,-3,9,-10,null,5]
Объяснение: [0,-10,5,null,-3,null,9] также является ответом

Ввод: nums = [1,3]
Вывод: [3,1]
Объяснение: [1,null,3] также является ответом

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

Столбцы таблицы Excel

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

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

Пример:

Ввод:columnNumber = 1
Вывод: "A"

Ввод: columnNumber = 28
Вывод: "AB"

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

Максимальное скользящее

Сложность: Тяжёлая

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

Пример:

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

Объяснение:
Скользящее на каждой итерации Max
-------------------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

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

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

Подсчет качественных узлов бинарного бинарного дерева

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

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

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

Пример:

Ввод: root = [3,1,4,3,null,1,5]
Вывод: 4
Объяснение: *качественные узлы помечены голубым цветом на вложении.

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

Наиближайшая сумма трёх

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

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

Каждый массив имеет единственное решение.

Пример:

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2
Объяснение: (-1 + 2 + 1 = 2)

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

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

Подмножества

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

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

Пример:

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

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

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

Сцепка бинарного дерева из центрированного и прямого проходов

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

Условие задачи: даны два списка preorder и inorder, где preorder - центрированный порядок дерева (сenter > left > rigth), inorder - прямой проход (left > center > right). Оба - описывают структуру одного дерева, необходимо сконструировать бинарное дерево.

Пример:

Ввод: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Вывод: [3,9,20,null,null,15,7]

Ввод: preorder = [-1], inorder = [-1]
Вывод: [-1]

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