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

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

Условие задачи: дается корень двоичного дерева, содержащего только цифры от 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

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

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

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

Условие задачи: дан двумерный массив, содержащий 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

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

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

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

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

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

Пример:

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

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

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

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

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

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

Пример:

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

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

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

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

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

Пример:

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

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

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

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

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

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

Наибольший общий делитель строки

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

Условие задачи: для двух строк s и t мы говорим "t делит s" тогда и только тогда, когда s = t + ... + t (т.е. t объединяется с самим собой один или несколько раз).

Дается две строки str1 и str2, верните самую большую строку x, такую, что x делит как str1, так и str2.

Пример:

Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: "ABC"

Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"

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