K-ый наибольший элемент в массиве
Сложность: Средняя
Условие задачи: дается массив, а также число k. Необходимо вернуть k-ый наибольший элемент в массиве.
Данный элемент отсчитывается в отсортированном списке, а не по уникальности значений.
Решение должно иметь временную сложность не более
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается массив, а также число k. Необходимо вернуть k-ый наибольший элемент в массиве.
Данный элемент отсчитывается в отсортированном списке, а не по уникальности значений.
Решение должно иметь временную сложность не более
O(n). Пример:
Ввод:
nums = [3,2,1,5,6,4], k = 2Вывод:
5Ввод:
nums = [3,2,3,1,2,4,5,5,6], k = 4Вывод:
4Решение задачи
👍4❤1
Проверка соответствия строк в двух списках
Сложность: Лёгкая
Условие задачи: на вход подаются два строковых массива, необходимо вернуть true, если два массива представляют одну и ту же строку, false в противном случае.
Под представлением одной и той же строки подразумевается, что после конкатенации всех фрагментов списков, две полученные строки будут идентичными.
Пример:
Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true
Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"
Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подаются два строковых массива, необходимо вернуть true, если два массива представляют одну и ту же строку, false в противном случае.
Под представлением одной и той же строки подразумевается, что после конкатенации всех фрагментов списков, две полученные строки будут идентичными.
Пример:
Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true
Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"
Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false
Решение задачи
👍2
K-ый наибольший элемент
Сложность: Лёгкая
Условие задачи: необходимо разработать класс по нахождению k-ого наибольшего элемента среди передаваемых значений. k-м считается элемент для отсортированного списка, а не по уникальности значения.
Класс содержит следующие методы:
-
-
Пример:
Ввод:
Вывод:
Объяснение:
Решение задачи
Сложность: Лёгкая
Условие задачи: необходимо разработать класс по нахождению k-ого наибольшего элемента среди передаваемых значений. k-м считается элемент для отсортированного списка, а не по уникальности значения.
Класс содержит следующие методы:
-
KthLargest(int k, int[] nums) иниициализирует класс;-
int add(int val) добавляет элемент в спискок и возвращает k-ый наименьший согласно условию.Пример:
Ввод:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]Вывод:
[null, 4, 5, 5, 8, 8]Объяснение:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8Решение задачи
👍1
Сумма тропы в дереве 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
Подмножества
Сложность: Средняя
Условие задачи: дан массив из целых чисел, необходимо вывести все подмножества исходного массива, которые не содержат дубликаты.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дан массив из целых чисел, необходимо вывести все подмножества исходного массива, которые не содержат дубликаты.
Пример:
Ввод:
nums = [1,2,3]Вывод:
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Ввод:
nums = [0]Вывод:
[[],[0]]Решение задачи
👍2
Максимальное скользящее
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер 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]Решение задачи
👍2
Столбцы таблицы Excel
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
👍2
Городской судья
Сложность: Лёгкая
Условие задачи: в городе живёт n людей, проиндексированные с 1 до n. Пошел слух, что один из горожан является судьей.
Если в городе-таки имеется судья, то:
1. Судья никому не доверяет.
2. Каждый горожанин, за исключением судьи, доверяет судье.
3. Существует один и единственный человек, который удовлетворяет правилам 1 и 2.
На вход подается массив связей доверия между гражданами, где
Вывести надо индекс судьи или же -1 в случае отсутствия такового среди жителей города.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: в городе живёт n людей, проиндексированные с 1 до n. Пошел слух, что один из горожан является судьей.
Если в городе-таки имеется судья, то:
1. Судья никому не доверяет.
2. Каждый горожанин, за исключением судьи, доверяет судье.
3. Существует один и единственный человек, который удовлетворяет правилам 1 и 2.
На вход подается массив связей доверия между гражданами, где
trust[i] = [ai, bi] обозначает, что ai доверяет жителю bi.Вывести надо индекс судьи или же -1 в случае отсутствия такового среди жителей города.
Пример:
Ввод:
n = 2, trust = [[1,2]]Вывод:
2Ввод:
n = 3, trust = [[1,3],[2,3],[3,1]]Вывод:
-1Решение задачи
👍2
Сумма по пути III
Сложность: Средняя
Условие задачи: дан указатель на корень бинарного дерева и целое число - значение таргета. Надо посчитать количество путей в дереве, сумма значений в узлах которых равна целевому значению.
Путь может начинаться с любого из узлов дерева, но при этом путь должен сожержать лишь узлы-родственники.
Пример:
Ввод:
Вывод:
Объяснение: *во вложении
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дан указатель на корень бинарного дерева и целое число - значение таргета. Надо посчитать количество путей в дереве, сумма значений в узлах которых равна целевому значению.
Путь может начинаться с любого из узлов дерева, но при этом путь должен сожержать лишь узлы-родственники.
Пример:
Ввод:
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8Вывод:
3Объяснение: *во вложении
Ввод:
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Вывод:
3Решение задачи
👍1
Сравнение стёртых строк
Сложность: Лёгкая
Условие задачи: даны две строки, необходимо выяснить являются они идентичными после удаления символов путем использования клавиши backspace (символ #).
Если строка пустая, то backspace оставляет её пустой.
Пример:
Ввод:
Вывод:
Объяснение: обе строки после использования удаления символов образуют сроку
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: даны две строки, необходимо выяснить являются они идентичными после удаления символов путем использования клавиши backspace (символ #).
Если строка пустая, то backspace оставляет её пустой.
Пример:
Ввод:
s = "ab#c", t = "ad#c"Вывод:
trueОбъяснение: обе строки после использования удаления символов образуют сроку
"ac"Ввод:
s = "ab##", t = "c#d#"Вывод:
trueВвод:
s = "a#c", t = "b"Вывод:
falseРешение задачи
👍2
Диаметр бинарного дерева
Сложность: Лёгкая
Условие задачи: дан корневой элемент бинарного дерева, необходимо расчитать диаметр бинарного дерева.
Диаметр бинарного дерева - наибольшая длина между двумя любыми узлами в дереве (необязательно включая корневой элемент всего дерева).
Длина между двумя узлами дерева - количество ребер между ними.
Пример:
Ввод: root = [1,2,3,4,5]
Вывод: 3
Объяснение: длина пути [4,2,1,3] или пути [5,2,1,3].
Ввод: root = [1,2]
Вывод: 1
Решение задачи
Сложность: Лёгкая
Условие задачи: дан корневой элемент бинарного дерева, необходимо расчитать диаметр бинарного дерева.
Диаметр бинарного дерева - наибольшая длина между двумя любыми узлами в дереве (необязательно включая корневой элемент всего дерева).
Длина между двумя узлами дерева - количество ребер между ними.
Пример:
Ввод: root = [1,2,3,4,5]
Вывод: 3
Объяснение: длина пути [4,2,1,3] или пути [5,2,1,3].
Ввод: root = [1,2]
Вывод: 1
Решение задачи
👍1
Количество возрастающих подпоследовательностей наибольшей длины
Сложность: Средняя
Условие задачи: дан массив целых чисел, надо посчитать количество возрастающих подпоследовательностей наибольшей длины. Подпоследовательность (ее элементы) должна строго возрастать.
Пример:
Ввод:
Вывод:
Объяснение: есть две возрастающие подпоследовательности одинаковой длины:
Ввод:
Вывод:
Объяснение: в данном массиве есть 5 подпоследовательностей длины 1.
Решение задачи
Сложность: Средняя
Условие задачи: дан массив целых чисел, надо посчитать количество возрастающих подпоследовательностей наибольшей длины. Подпоследовательность (ее элементы) должна строго возрастать.
Пример:
Ввод:
nums = [1,3,5,4,7]Вывод:
2Объяснение: есть две возрастающие подпоследовательности одинаковой длины:
[1, 3, 4, 7] и [1, 3, 5, 7]Ввод:
nums = [2,2,2,2,2]Вывод:
5Объяснение: в данном массиве есть 5 подпоследовательностей длины 1.
Решение задачи
👍3
Поиск в бинарном дереве
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска и целевое значения для поиска.
Необходимо найти в дереве такой элемент, равный целевому, а также вывести поддерево данного узла.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска и целевое значения для поиска.
Необходимо найти в дереве такой элемент, равный целевому, а также вывести поддерево данного узла.
Пример:
Ввод:
root = [4,2,7,1,3], val = 2Вывод:
[2,1,3]Ввод:
root = [4,2,7,1,3], val = 5Вывод:
[]Решение задачи
👍1
Ключи и комнаты
Сложность: Средняя
Условие задачи: есть
При посещении какой-либо комнаты в ней находится определенная связка уникальных ключей, номер ключа означет номер комнаты, для которой он отпирает дверь. Можно использовать сразу все связку ключей.
На вход подается массив комнат, где в i-ячейке дается список ключей, находящихся в текущей комнате. Необходимо определеть, можно ли обойти все комнаты.
Пример:
Ввод:
Вывод:
Объяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3.
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: есть
n комнат проиндексированных с 0, все они закрыты кроме комнаты с номером 0. Необходимо посетить все комнаты, однако этого нельзя сдеать не имея ключа от соответствующей закрытой двери. При посещении какой-либо комнаты в ней находится определенная связка уникальных ключей, номер ключа означет номер комнаты, для которой он отпирает дверь. Можно использовать сразу все связку ключей.
На вход подается массив комнат, где в i-ячейке дается список ключей, находящихся в текущей комнате. Необходимо определеть, можно ли обойти все комнаты.
Пример:
Ввод:
rooms = [[1],[2],[3],[]]Вывод:
trueОбъяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3.
Ввод:
rooms = [[1,3],[3,0,1],[2],[0]]Вывод:
falseРешение задачи
👍2
Расшифровка строки
Сложность: Средняя
Условие задачи: сообщение содержит символы из множества
На воход подается строка , состоящая из чисел, необходимо посчитать сколькими способами можно ее расшифровать.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: сообщение содержит символы из множества
A-Z и может быть расшифровано следующим образом:'A' -> "1"
'B' -> "2"
...
'Z' -> "26"На воход подается строка , состоящая из чисел, необходимо посчитать сколькими способами можно ее расшифровать.
Пример:
Ввод:
s = "12"Вывод:
2Объяснение:
"12" можно расшифровать двумя путями: как (1 2) = "AB", а также как и (12) = "L".Ввод:
s = "226"Вывод:
3Решение задачи
👍2❤1
Арифметическая прогрессия в массиве
Сложность: Средняя
Условие задачи: дан массив, который называется массивом арифметической прогрессии в случае, если содержит как минимум три элемента, а разница между соседними элементами одинаковая.
Массивы [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
Решение задачи
Сложность: Средняя
Условие задачи: дан массив, который называется массивом арифметической прогрессии в случае, если содержит как минимум три элемента, а разница между соседними элементами одинаковая.
Массивы [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
Решение задачи
Палиндром наибольшей длины в подстроке
Сложность: Средняя
Условие задачи: дана строка, необходимо найти в ней палиндром наибольшей длины.
Палиндром - строка, которая одинаково читается как справа-налево, так и слева-направо.
Пример:
Ввод: s = "babad"
Вывод: "bab"
Объяснение: "aba" также является ответом
Ввод: s = "cbbd"
Вывод: "bb"
Решение задачи
Сложность: Средняя
Условие задачи: дана строка, необходимо найти в ней палиндром наибольшей длины.
Палиндром - строка, которая одинаково читается как справа-налево, так и слева-направо.
Пример:
Ввод: s = "babad"
Вывод: "bab"
Объяснение: "aba" также является ответом
Ввод: s = "cbbd"
Вывод: "bb"
Решение задачи
👍2
Поддерево дерева
Сложность: Лёгкая
Условие задачи: даны корни бинарных деревьев
Пример:
Ввод:
Вывод:
Объяснение: *на картинке к задаче
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: даны корни бинарных деревьев
root и subRoot. Надо осуществить проверку, является ли subRoot поддеревом root с той же самой структурой и значениями в узлах.Пример:
Ввод:
root = [3,4,5,1,2], subRoot = [4,1,2]Вывод:
trueОбъяснение: *на картинке к задаче
Ввод:
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Вывод:
falseРешение задачи
👍1
Первая плохая версия
Сложность: Лёгкая
Условие задачи: производится разработка нового программного продукта, и на последней проверке было выявлено, что версия ПО не прошла проверку качества. Каждая следующая версия зависит от предыдущей, то есть если текущая версия не проходит проверки, то все последующие также не годны для какого-либо обслуживания.
Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.
Также дается интерфейс
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: производится разработка нового программного продукта, и на последней проверке было выявлено, что версия ПО не прошла проверку качества. Каждая следующая версия зависит от предыдущей, то есть если текущая версия не проходит проверки, то все последующие также не годны для какого-либо обслуживания.
Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.
Также дается интерфейс
bool isBadVersion(version), который производит проверку на то, является ли проверяемая версия неисправной. Решить задачу необходимо за минимальное количество вызовов чекера. Пример:
Ввод:
n = 5, bad = 4Вывод:
4Объяснение:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
4 - первая испорченная версия.Ввод:
Вывод:
Решение задачи
👍2
Слияние двух отсортированных массивов
Сложность: Лёгкая
Условие задачи: даны два массива, отсортированные в порядке неубывания, а также две переменные m и n, в которых хранится длина каждого из массивов.
Надо свзать оба массива в один в порядке неубывания.
Результирующий массив должен содержаться в массиве
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: даны два массива, отсортированные в порядке неубывания, а также две переменные m и n, в которых хранится длина каждого из массивов.
Надо свзать оба массива в один в порядке неубывания.
Результирующий массив должен содержаться в массиве
nums1. Пример:
Ввод:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]
Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]
Решение задачи👍1