Pow(x, n)

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

Условие задачи:
Реализуйте функцию pow(x, n), которая вычисляет x в степени n (т. е. x^n).

Пример:
Ввод: x = 2.00000, n = 10
Вывод: 1024.00000

Ввод: x = 2.10000, n = 3
Вывод: 9.26100

Диапазон данных:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= x^n <= 104

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

То же дерево

Сложность задачи:
Низкая

Условие:
Получив корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.

Примеры (картинки по порядку):
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true

Ввод: p = [1,2], q = [1,null,2]
Вывод: false

Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false

Ограничения:
Количество узлов в обоих деревьях находится в диапазоне [0, 100].

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

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

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

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

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

Пример:

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

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

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

Инвертировать бинарное дерево

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

Условие задачи: дается корень двоичного дерева, инвертируйте дерево и верните его корень.

Пример:

Ввод: root = [4,2,7,1,3,6,9]
Вывод: [4,7,2,9,6,3,1]
Объяснение: *во вложении

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

Поиск мажоритарного элемента

Условие задачи:
Дан массив nums размера n. Требуется вернуть мажоритарный элемент.

Мажоритарный элемент - это элемент, который появляется более n / 2 раз. Вы можете быть уверены, что мажоритарный элемент всегда существует в массиве.

Примеры:
Ввод: nums = [4,2,4]
Вывод: 4

Ввод: nums = [8, 8, 6, 6, 6, 8, 8]
Вывод: 8

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

Извлечение дубликатов из отсортированного списка II

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

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

Пример:

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

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

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

Сжатие строки

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

Условие задачи: дается массив символов chars, сожмите его, используя следующий алгоритм:

Начинайте с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ для просмотра.
В противном случае добавьте символ, за которым следует длина группы.
Сжатые строки не должны возвращаться отдельно, а вместо этого должны храниться во входном символьном массиве chars. Обратите внимание, что длина группы, равная 10 или более, будет разделена на несколько символов в chars.

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

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример:

Ввод: chars = ["a","a","b","b","c","c","c"]
Вывод: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

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

Подмассив с фиксированными границами

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

Условие задачи: дается целочисленный массив nums и два целых числа minK и maxK.

Подмассив nums с фиксированной привязкой - это подмассив, который удовлетворяет следующим условиям:

Минимальное значение в подмассиве равно minK.
Максимальное значение в подмассиве равно max.
Возвращает количество подмассивов с фиксированной привязкой.

Подмассив - это непрерывная часть массива.

Пример:

Ввод: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Вывод: 2

Ввод: nums = [1,1,1,1], minK = 1, maxK = 1
Вывод: 10

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

Подмассив с фиксированными границами

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

Условие задачи: дается целочисленный массив nums и два целых числа minK и maxK.

Подмассив nums с фиксированной привязкой - это подмассив, который удовлетворяет следующим условиям:

Минимальное значение в подмассиве равно minK.
Максимальное значение в подмассиве равно max.
Возвращает количество подмассивов с фиксированной привязкой.

Подмассив - это непрерывная часть массива.

Пример:

Ввод: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Вывод: 2

Ввод: nums = [1,1,1,1], minK = 1, maxK = 1
Вывод: 10

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

Случайный узел списка

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

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

Реализуйте класс решения:

Инициализируется объект с помощью заголовка односвязного списка head.
int getRandom() случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью.

Пример:

Ввод: ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Вывод: [null, 1, 3, 2, 2, 3]

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

От предка до потомка

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

Условие задачи: дается корень двоичного дерева, содержащего только цифры от 0 до 9.

Каждый путь от корня к листу в дереве представляет собой число.

Например, путь от корня к листу 1 -> 2 -> 3 представляет число 123.
Возвращает общую сумму всех чисел от корня до конца. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-разрядное целое число.

Конечный узел - это узел без дочерних элементов.

Пример:

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

Ввод: root = [4,9,0,5,1]
Вывод: 1026

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

Симметрия в дереве

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

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

Пример:

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

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

Проверка полноты бинарного дерева

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

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

В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.

Пример:

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

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

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

Количество изолированных островов

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

Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду).

Остров - множество нулей, соединенных в четырех направлениях (справа, снизу, слева, сверху), изолированый остров - множество нулей, окруженных со всех сторон единицами.

Надо посчитать количество изолированных островов.

Пример:

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

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

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