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

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

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

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

Поддерево дерева

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

Условие задачи: даны корни бинарных деревьев 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

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

Первая плохая версия

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

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

Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.

Также дается интерфейс bool isBadVersion(version), который производит проверку на то, является ли проверяемая версия неисправной. Решить задачу необходимо за минимальное количество вызовов чекера.

Пример:

Ввод: n = 5, bad = 4
Вывод: 4
Объяснение:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
4 - первая испорченная версия.

Ввод:
Вывод:

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