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

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

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

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

Необходимо разработать алгоритм с временной сложностью менее 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

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

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

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

Количество точек на прямой

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

Условие задачи: дается массив точек, где точки [i] = [xi, yi] представляют точку на плоскости X-Y, верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

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

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

Сбор урожая яблок

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

Условие задачи: дано неориентированное дерево, состоящее из n вершин, пронумерованных от 0 до n-1, в вершинах которого есть несколько яблок. Вы тратите 1 секунду, чтобы пройти по одному ребру дерева. Верните минимальное время в секундах, которое вы должны потратить, чтобы собрать все яблоки на дереве, начиная с вершины 0 и возвращаясь к этой вершине.

Ребра неориентированного дерева заданы в массиве ребер, где ребра[i] = [ai, bi] означают, что существует ребро, соединяющее вершины ai и bi. Кроме того, существует логический массив has Apple, где has Apple[i] = true означает, что в вершине i есть яблоко; в противном случае в ней нет никакого яблока.

Пример:

Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Вывод: 8


Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Вывод: 6

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

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

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

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

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

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

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

Пример:

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

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

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

Подсчет подостровов

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

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

Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.

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

Пример:

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

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

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

Шаблон слова

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

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

Под соответствием имеется биекция двух строковых наборов, которая в результате дает непустое слово.

Пример:

Ввод: pattern = "abba", s = "dog cat cat dog"
Вывод: true

Ввод: pattern = "abba", s = "dog cat cat fish"
Вывод: false

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

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

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

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

Пример:

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

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

Арифметическая прогрессия в массиве

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

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

Массивы [1,3,5,7,9], [7,7,7,7], [3,-1,-5,-9] являются таковыми.

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

Подмассив - непрерывная последовательность исходного массива.

Пример:

Ввод: nums = [1,2,3,4]
Вывод: 3
Объяснение: [1, 2, 3], [2, 3, 4] и [1,2,3,4] являются арифметическими подмассивами.

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

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

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

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

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

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

Пример:

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

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

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

Проверка схожести половин строки

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

Условие задачи: на вход подается строка четной длины. Далее проводится разделение на две равные части.

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

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

Пример:

Ввод: s = "book"
Вывод: true

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

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

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

Условие задачи: дан целочисленный массив, а также размер 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
Объяснение: *качественные узлы помечены голубым цветом на вложении.

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

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

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

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

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

Два огромных океана

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

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

После того, как прошел бурный дождь по острову начала стекать вода. Жидкость может течь лишь в том направлении, где рельеф в текущей точке не меньше (по значению на решетке), чем рельеф в соседней.

Необходимо выявить точки, из которых дождевая вода может попасть и в Тихий океан и в Атлантический.

Пример:

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

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

Удаление дубликатов из отсортированного связного списка

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

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

Пример:

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

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

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

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

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

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

Класс должен содержать в себе следующие методы:

- BSTIterator(TreeNode root). Данный метод инициализирует объект класса. root передаются в конструктор в качестве входного аргумента. Указатель должен быть инициализирован несуществующим числом, которое меньше любого из элементов бинарного дерева;

- boolean hasNext(). Возвращает true в случае если существует потомок у правого поддерева. В ином случае возвращает false;

- int next(). Перемещает указатель в правую ветвь, возвращая число в указателе.

При инициализации указатель на несуществующий наименьший элемент, вызывая метод next(), будет возвращать наименьший элемент бинарного дерева.

Пример:

Ввод:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Вывод: [null, 3, 7, true, 9, true, 15, true, 20, false]

Объяснение:
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False

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

Счастливое число

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

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

Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.

Пример:

Ввод: n = 19
Вывод: true
Объяснение:
1 + 81 = 82
64 + 4 = 68
36 + 64 = 100
1 + 0 + 0 = 1

Ввод: n = 2
Вывод: false

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