Сумма тропы в дереве II
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, а также целовое значение суммы, необходимо вернуть такие пути в дереве (от корня до последнего потомка), сумма значений в узлах которых равна целевой сумме. Каждый путь должен быть возвращен как список из значений узлов.
Пример:
Ввод:
Вывод:
Объяснение: * голубые узлы на изображении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, а также целовое значение суммы, необходимо вернуть такие пути в дереве (от корня до последнего потомка), сумма значений в узлах которых равна целевой сумме. Каждый путь должен быть возвращен как список из значений узлов.
Пример:
Ввод:
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Вывод:
[[5,4,11,2],[5,8,4,5]]Объяснение: * голубые узлы на изображении
Решение задачи
👍2❤1
Максимальное скользящее
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер k подмассива, начинающегося от левой границы, и заканчивающегося в процессе выполнения алгоритма у правой границы. На каждом шаге можно просматривать k последовательных элементов скользящего массива. На каждом шаге надо определить максимальное значение скользящего.
Пример:
Ввод:
Вывод:
Объяснение:
Скользящее на каждой итерации
Ввод:
Вывод:
Решение задачи
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер 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
1 3 [-1 -3 5] 3 6 7
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7
1 3 -1 -3 5 [3 6 7] Ввод:
nums = [1], k = 1Вывод:
[1]Решение задачи
👍1
Возрастающая подпоследовательность наибольшей длины
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
❤1👍1
Суммы подмассивов, кратные K
Сложность: Средняя
Условие задачи: дается целочисленный массив nums и целое число k, верните количество непустых подмассивов, сумма которых делится на k.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [4,5,0,-2,-3,1], k = 5
Вывод: 7
Объяснение: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Ввод: nums = [5], k = 9
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: дается целочисленный массив nums и целое число k, верните количество непустых подмассивов, сумма которых делится на k.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [4,5,0,-2,-3,1], k = 5
Вывод: 7
Объяснение: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Ввод: nums = [5], k = 9
Вывод: 0
Решение задачи
👍1
Восстановить IP
Сложность: Средняя
Условие задачи: действительный IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.
Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: действительный IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.
Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.
Пример:
Ввод:
s = "25525511135"Вывод:
["255.255.11.135","255.255.111.35"]Ввод:
s = "0000"Вывод:
["0.0.0.0"]Решение задачи
👍3
Создание четырехугольного дерева
Сложность: Средняя
Условие задачи: дана матричная сетка n * n, состоящая только из 0 и 1. Мы хотим представить сетку в виде четырехъядерного дерева.
Возвращает корень квадродерева, представляющего сетку.
Обратите внимание, что вы можете присвоить значению узла значение True или False, когда isLeaf имеет значение False, и оба значения принимаются в ответе.
Квадродерево - это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Кроме того, каждый узел имеет два атрибута.
Выполните рекурсию для каждого из дочерних элементов с соответствующей подсеткой.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Решение задачи
Сложность: Средняя
Условие задачи: дана матричная сетка n * n, состоящая только из 0 и 1. Мы хотим представить сетку в виде четырехъядерного дерева.
Возвращает корень квадродерева, представляющего сетку.
Обратите внимание, что вы можете присвоить значению узла значение True или False, когда isLeaf имеет значение False, и оба значения принимаются в ответе.
Квадродерево - это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Кроме того, каждый узел имеет два атрибута.
Выполните рекурсию для каждого из дочерних элементов с соответствующей подсеткой.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Решение задачи
👍2
Поиск дубликата поддерева
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, верните все повторяющиеся поддеревья.
Для каждого вида повторяющихся поддеревьев вам нужно только вернуть корневой узел любого из них.
Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Ввод: root = [1,2,3,4,null,2,4,null,null,4]
Вывод: [[2,4],[4]]
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, верните все повторяющиеся поддеревья.
Для каждого вида повторяющихся поддеревьев вам нужно только вернуть корневой узел любого из них.
Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Ввод: root = [1,2,3,4,null,2,4,null,null,4]
Вывод: [[2,4],[4]]
Решение задачи
❤1👍1
Сортировка массива
Сложность: Средняя
Условие задачи: дается массив целых чисел nums, отсортируйте массив в порядке возрастания и верните его.
Вы должны решить проблему без использования каких-либо встроенных функций в O(nlog(n)) временной сложности и с наименьшей возможной пространственной сложностью.
Пример:
Ввод: nums = [5,2,3,1]
Вывод: [1,2,3,5]
Ввод: nums = [5,1,1,2,0,0]
Вывод: [0,0,1,1,2,5]
Решение задачи
Сложность: Средняя
Условие задачи: дается массив целых чисел nums, отсортируйте массив в порядке возрастания и верните его.
Вы должны решить проблему без использования каких-либо встроенных функций в O(nlog(n)) временной сложности и с наименьшей возможной пространственной сложностью.
Пример:
Ввод: nums = [5,2,3,1]
Вывод: [1,2,3,5]
Ввод: nums = [5,1,1,2,0,0]
Вывод: [0,0,1,1,2,5]
Решение задачи
👍1
Извлечение дубликатов из отсортированного списка II
Сложность: Средняя
Условие задачи: на вход подается указатель на начало связного списка, необходимо удалить все узлы, имеющие дубликаты, то есть в списке должны остаться лишь уникальные значения, которые были в изначальном списке. Необходимо вернуть связный список в отсортированном порядке как и был.
Пример:
Ввод: head = [1,2,3,3,4,4,5]
Вывод: [1,2,5]
Ввод: head = [1,1,1,2,3]
Вывод: [2,3]
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается указатель на начало связного списка, необходимо удалить все узлы, имеющие дубликаты, то есть в списке должны остаться лишь уникальные значения, которые были в изначальном списке. Необходимо вернуть связный список в отсортированном порядке как и был.
Пример:
Ввод: head = [1,2,3,3,4,4,5]
Вывод: [1,2,5]
Ввод: head = [1,1,1,2,3]
Вывод: [2,3]
Решение задачи
👍1
Проверка полноты бинарного дерева
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
👍1
Поиск в двумерной матрице 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
Решение задачи
Сложность: Средняя
Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:
- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).
Пример:
Ввод: 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
Решение задачи
👍1
Подмассив с наибольшим произведением
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
👍2
Текущая длительность котировок
Сложность: Средняя
Условие задачи: разработайте алгоритм, который сохраняет котировки некоторой акции текущего дня и осуществляет подсчёт, сколько дней до этого стоимость бумаг была меньше или равна цена на текущий день (включая текущий день).
Пример:
Ввод:
Сложность: Средняя
Условие задачи: разработайте алгоритм, который сохраняет котировки некоторой акции текущего дня и осуществляет подсчёт, сколько дней до этого стоимость бумаг была меньше или равна цена на текущий день (включая текущий день).
Пример:
Ввод:
["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
Подсчет узлов бинарного дерева
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
❤1👍1
Произведение подмассива меньше K
Сложность: Средняя
Условие задачи: дается массив и целевое значение произведения, необходимо вернуть количесво подмассивов, в которых последовательные элементы будут при умножении давать значение меньшее или равное целевому.
Пример:
Ввод:
Вывод: 8
Объяснение:
Решение задачи
Сложность: Средняя
Условие задачи: дается массив и целевое значение произведения, необходимо вернуть количесво подмассивов, в которых последовательные элементы будут при умножении давать значение меньшее или равное целевому.
Пример:
Ввод:
nums = [10,5,2,6], k = 100Вывод: 8
Объяснение:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]Решение задачи
👍1
Поиск суммы в бинарном дереве поиска
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
root = [5,3,6,2,4,null,7], k = 9Вывод:
trueВвод:
root = [5,3,6,2,4,null,7], k = 28Вывод:
falseРешение задачи
👍1
Реализация класса MinStack
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:
-
-
-
-
Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).
Пример:
Ввод:
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс 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
Решение задачи❤2👍1
Количество точек на прямой
Сложность: Тяжёлая
Условие задачи: дается массив точек, где точки [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
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается массив точек, где точки [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
Решение задачи
❤2👍1
Сбор урожая яблок
Сложность: Средняя
Условие задачи: дано неориентированное дерево, состоящее из 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
Решение задачи
Сложность: Средняя
Условие задачи: дано неориентированное дерево, состоящее из 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
Решение задачи
❤2👍1
Мост наименьшей длины
Сложность: Средняя
Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.
Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.
Можно изменить 0 на 1 для соединения двух островов в один.
Необходимо посчитать количество смен нулей на единицу для соединения двух островов.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:
Ввод: grid = [[0,1,0],[0,0,0],[0,0,1]]
Вывод: 2
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.
Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.
Можно изменить 0 на 1 для соединения двух островов в один.
Необходимо посчитать количество смен нулей на единицу для соединения двух островов.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:
Ввод: grid = [[0,1,0],[0,0,0],[0,0,1]]
Вывод: 2
Решение задачи
👍1