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

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

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

В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 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

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

Столкновение астероидов

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

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

При столкновени двух астероидов, асторид с меньшим весов уничтожается (у целого астероида вес остается неизменным после столкновения).

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

Пример:

Ввод: asteroids = [5,10,-5]
Вывод: [5,10]
Объяснение: 3-ий астероид сталкивается со 2-ым и уничтожается.

Ввод: asteroids = [8,-8]
Вывод: [ ]

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

Заливка

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

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

Также даются три числа sr, sc, color. Надо осуществить заливку, начиная с image[sr][sc].

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

Пример:

Ввод: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Вывод: [[2,2,2],[2,2,0],[2,0,1]]

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

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

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

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

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

Пример:

Ввод: 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] также является ответом

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

Игра в угадайку

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

Условие задачи: играем в угадайку по следующей схеме:

Выбирается число от 1 до n. Надо отгадать загаданное число. После каждой неудачной попытки говорится больше или меньше заданное число.

Надо реализовать API:

-1: загаданное число больше выбранного;
1: загаданное число меньше выбранного;
0: загаданное число и выбранное совпали.

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

Пример:

Ввод: n = 10, pick = 6
Вывод: 6

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

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

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

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

- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

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

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

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

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

Пример:

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


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

Подмассив с наибольшим произведением

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

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

Подмассив - последовательный кусок исходного массива.

Пример:

Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.

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

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

Текущая длительность котировок

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

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

Пример:

Ввод: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Вывод: [null, 1, 1, 1, 2, 1, 4, 6]

Объяснение:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, так как цены за четыре предыдущих дня (включая сегодняшний) были меньше или равны;
stockSpanner.next(85); // return 6

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

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

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

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

Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.

Необходимо разработать алгоритм с временной сложностью менее O(n).

Пример:

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

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

Произведение подмассива меньше  K

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

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

Пример:

Ввод: nums = [10,5,2,6], k = 100
Вывод: 8
Объяснение: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

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

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

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

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

Пример:

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

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

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

Слияние двух бинарных деревьев

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

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

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

Пример:

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

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

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

Поток данных в виде непересекающихся интервалов

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

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

Реализуйте класс сводных диапазонов:

Сводные диапазоны() инициализирует объект пустым потоком.
void addNum(значение int) Добавляет целочисленное значение в поток.
int[][] getinterval() Возвращает сводку целых чисел в потоке в данный момент в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по началу.

Пример:

Ввод: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Вывод: [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

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

Матрица Топлица

Сложность: Лёгкая Средняя Тяжёлая

Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.

Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.

Пример:

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

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

Перелет с наименьшей ценой

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

Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.

Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.

Пример:

Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700

Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200

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

Треугольник

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

Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на 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.

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

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

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

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

Пример:

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

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

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