Количество узлов

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

Условие задачи: дано дерево (т.е. связный неориентированный граф, не имеющий циклов), состоящее из n узлов с числом от 0 до n - 1 и ровно n - 1 ребер. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая представляет собой символ нижнего регистра, указанный в строковых метках (т.е. узел с номером i имеет метку labels[i]).

Массив ребер задан на ребрах фермы[i] = [ai, bi], что означает наличие ребра между узлами ai и bi в дереве.

Возвращает массив размера n, где и[i] - количество узлов в поддереве узла земли, которые имеют ту же метку, что и узел i.

Поддерево дерева - это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Вывод: [2,1,1,1,1,1,1]
Объяснение:

Ввод: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Вывод: [4,2,1,1]

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

Наименьшая лексикографически схожая строка

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

Условие задачи: даны две строки одинаковой длины s1 и s2 и строка baseStr.

Говорим, что s1[i] и s2[i] являются эквивалентными символами.

Например, если s1 = "abc" и s2 = "cde", то мы имеем 'a' == 'c', 'b' == 'd' и 'c' == 'e'.
Эквивалентные символы следуют обычным правилам отношения эквивалентности:

Рефлексивность: 'a' == 'a'.
Симметрия: 'a' == 'b' подразумевает 'b' == 'a'.
Транзитивность: 'a' == 'b' и 'b' == 'c' подразумевает 'a' == 'c'.
Например, учитывая информацию об эквивалентности из s1 = "abc" и s2 = "cde", "cd" и "ab" являются эквивалентными строками базового Str = "eed", а "aab" является лексикографически наименьшей эквивалентной строкой базового str.

Верните лексикографически наименьшую эквивалентную строку базового Str, используя информацию об эквивалентности из s1 и s2.

Пример:

Ввод: s1 = "parker", s2 = "morris", baseStr = "parser"
Вывод: "makkek"

Ввод: s1 = "hello", s2 = "world", baseStr = "hold"
Вывод: "hdld"

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

Количество провинций

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

Условие задачи: даётся n провинций, какие-то из них соединены между собой, какие-то нет, также соблюдается правило транзитивности: если провинция «1» соединена с провинцией «2», а «2» соединена с «3» провинцией, то и «1» соединена с «3».

Провинцией является совокупность городов, объединённых между собой, но при этом отделенные от других, принадлежащих другим провинциям.

На вход даётся квадратичная матрица, в которой isConnected[i][j] = 1 - соединение между i - ым и j - - ым населенными пунктами (1 - имеется соединение, 0 - отсутствует).

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

Пример:

Ввод: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Вывод: 2
Объяснение: *во вложении

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

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

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

Проверка соответствия строк в двух списках

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

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

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

Пример:

Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true

Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"

Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false

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

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

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

Сумма тропы в дереве 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]]
Объяснение: * голубые узлы на изображении


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

Подмножества

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

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

Пример:

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

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

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

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

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

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

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

Столбцы таблицы Excel

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

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

Пример:

Ввод:columnNumber = 1
Вывод: "A"

Ввод: columnNumber = 28
Вывод: "AB"

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

Городской судья

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

Условие задачи: в городе живёт 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

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

Сумма по пути 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

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

Сравнение стёртых строк

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

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

Если строка пустая, то backspace оставляет её пустой.

Пример:

Ввод: s = "ab#c", t = "ad#c"
Вывод: true
Объяснение: обе строки после использования удаления символов образуют сроку "ac"

Ввод: s = "ab##", t = "c#d#"
Вывод: true

Ввод: s = "a#c", t = "b"
Вывод: false

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

Диаметр бинарного дерева

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

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

Диаметр бинарного дерева - наибольшая длина между двумя любыми узлами в дереве (необязательно включая корневой элемент всего дерева).

Длина между двумя узлами дерева - количество ребер между ними.

Пример:

Ввод: root = [1,2,3,4,5]
Вывод: 3
Объяснение: длина пути [4,2,1,3] или пути [5,2,1,3].

Ввод: root = [1,2]
Вывод: 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.

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

Поиск в бинарном дереве

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

Условие задачи: дано бинарное дерево поиска и целевое значения для поиска.

Необходимо найти в дереве такой элемент, равный целевому, а также вывести поддерево данного узла.

Пример:

Ввод: root = [4,2,7,1,3], val = 2
Вывод: [2,1,3]

Ввод: root = [4,2,7,1,3], val = 5
Вывод: []

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

Ключи и комнаты

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

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

При посещении какой-либо комнаты в ней находится определенная связка уникальных ключей, номер ключа означет номер комнаты, для которой он отпирает дверь. Можно использовать сразу все связку ключей.

На вход подается массив комнат, где в i-ячейке дается список ключей, находящихся в текущей комнате. Необходимо определеть, можно ли обойти все комнаты.

Пример:

Ввод: rooms = [[1],[2],[3],[]]
Вывод: true
Объяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3.

Ввод: rooms = [[1,3],[3,0,1],[2],[0]]
Вывод: false

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

Расшифровка строки

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

Условие задачи: сообщение содержит символы из множества A-Z и может быть расшифровано следующим образом:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

На воход подается строка , состоящая из чисел, необходимо посчитать сколькими способами можно ее расшифровать.

Пример:

Ввод: s = "12"
Вывод: 2
Объяснение: "12" можно расшифровать двумя путями: как (1 2) = "AB", а также как и (12) = "L".

Ввод: s = "226"
Вывод: 3

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

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

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

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

Массивы [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"

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