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

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

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

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

Пример:

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

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

Реализация класса 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

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

Схожие деревья

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

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

Два дерева считаются схожими по последним потомкам в случае если последовательность последних потомков и в первом и во втором деревьях идентична.

Пример:

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

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

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

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

Условие задачи: даны два списка 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]

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

Заправочная станция

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

Условие задачи: вдоль кольцевого маршрута расположено n заправочных станций, где количество газа на i-й станции равно gas[i].

У вас есть автомобиль с неограниченным запасом бензина, и проезд от i-й станции до следующей (i + 1)-й станции обходится в стоимость [i] бензина. Вы начинаете путешествие с пустым баком на одной из заправочных станций.

Учитывая два целочисленных массива gas и cost, верните индекс начальной заправочной станции, если вы можете объехать круг один раз по часовой стрелке, в противном случае верните -1. Если существует решение, оно гарантированно будет уникальным

Пример:

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

Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1

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