Столбцы таблицы Excel
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
👍8
Максимальное скользящее
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер 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]Решение задачи
👍5
Подсчет качественных узлов бинарного бинарного дерева
Сложность: Средняя
Условие задачи: дано бинарное дерево, необходимо посчитать количество качественных узлов (Х) по пути из корня до узла Х.
Качественным элементом считается такой узел, значение которого больше значения родительского узла.
Пример:
Ввод: root = [3,1,4,3,null,1,5]
Вывод: 4
Объяснение: *качественные узлы помечены голубым цветом на вложении.
Решение задачи
Сложность: Средняя
Условие задачи: дано бинарное дерево, необходимо посчитать количество качественных узлов (Х) по пути из корня до узла Х.
Качественным элементом считается такой узел, значение которого больше значения родительского узла.
Пример:
Ввод: root = [3,1,4,3,null,1,5]
Вывод: 4
Объяснение: *качественные узлы помечены голубым цветом на вложении.
Решение задачи
👍6
Наиближайшая сумма трёх
Сложность: Средняя
Условие задачи: дан целочисленный массив и целевое значение суммы. Необходимо найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.
Каждый массив имеет единственное решение.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дан целочисленный массив и целевое значение суммы. Необходимо найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.
Каждый массив имеет единственное решение.
Пример:
Ввод:
nums = [-1,2,1,-4], target = 1Вывод:
2Объяснение:
(-1 + 2 + 1 = 2)Ввод:
nums = [0,0,0], target = 1Вывод:
0Решение задачи
👍5
Подмножества
Сложность: Средняя
Условие задачи: дан массив из целых чисел, необходимо вывести все подмножества исходного массива, которые не содержат дубликаты.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дан массив из целых чисел, необходимо вывести все подмножества исходного массива, которые не содержат дубликаты.
Пример:
Ввод:
nums = [1,2,3]Вывод:
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Ввод:
nums = [0]Вывод:
[[],[0]]Решение задачи
👍4
Сцепка бинарного дерева из центрированного и прямого проходов
Сложность: Средняя
Условие задачи: даны два списка preorder и inorder, где preorder - центрированный порядок дерева (сenter > left > rigth), inorder - прямой проход (left > center > right). Оба - описывают структуру одного дерева, необходимо сконструировать бинарное дерево.
Пример:
Ввод: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Вывод: [3,9,20,null,null,15,7]
Ввод: preorder = [-1], inorder = [-1]
Вывод: [-1]
Решение задачи
Сложность: Средняя
Условие задачи: даны два списка preorder и inorder, где preorder - центрированный порядок дерева (сenter > left > rigth), inorder - прямой проход (left > center > right). Оба - описывают структуру одного дерева, необходимо сконструировать бинарное дерево.
Пример:
Ввод: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Вывод: [3,9,20,null,null,15,7]
Ввод: preorder = [-1], inorder = [-1]
Вывод: [-1]
Решение задачи
👍3
Сумма тропы в дереве 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]]Объяснение: * голубые узлы на изображении
Решение задачи
👍1
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Решение задачи
👍6🤔1
K - ближайших точек к началу координат
Сложность: Средняя
Условие задачи: дан массив точек на плоскости, характеризующихся соответствующими декартовыми координатами. Также дается число k, которое обозначает количество точек, наиболее близких к началу координат, которые надо вывести. Расстояние измеряется через расстояние Евклида.
Гарантируется уникальность ответа.
Пример:
Ввод: points = [[1,3],[-2,2]], k = 1
Вывод: [[-2,2]]
Решение задачи
Сложность: Средняя
Условие задачи: дан массив точек на плоскости, характеризующихся соответствующими декартовыми координатами. Также дается число k, которое обозначает количество точек, наиболее близких к началу координат, которые надо вывести. Расстояние измеряется через расстояние Евклида.
Гарантируется уникальность ответа.
Пример:
Ввод: points = [[1,3],[-2,2]], k = 1
Вывод: [[-2,2]]
Решение задачи
👍2
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Решение задачи
👍3
Проверка соответствия строк в двух списках
Сложность: Лёгкая
Условие задачи: на вход подаются два строковых массива, необходимо вернуть 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
Где приземлится мяч
Сложность: Средняя
Условие задачи: дается двумерный массив, определяющий короб, а также n-ое количество мячей.
Каждая ячейка данной коробки имеет диагональную перегородку, которая может перенаправлять движение мяча.
- Перегородка ячейки типа "левый верхний угол —> правый нижний угол" имеет представление 1.
- Перегородка ячейки типа "правый верхний угол —> левый нижний угол" имеет представление -1.
В каждом столбце сверху бросается ровно один мяч, а дорога из перегородок может уткнуть мяч либо в стену, либо дать спокойно выпасть снизу коробки.
Необходимо вернуть массив, который будет показывать добрался ли i-ый мяч до дна коробки (интерпретируется 1) или же уткнулся в стену (-1).
Пример:
Ввод: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Вывод: [1,-1,-1,-1,-1]
Объяснение: *во вложении
Ввод: grid = [[-1]]
Вывод: [-1]
Объяснение: мяч уткнется в левую стенку коробки
Решение задачи
Сложность: Средняя
Условие задачи: дается двумерный массив, определяющий короб, а также n-ое количество мячей.
Каждая ячейка данной коробки имеет диагональную перегородку, которая может перенаправлять движение мяча.
- Перегородка ячейки типа "левый верхний угол —> правый нижний угол" имеет представление 1.
- Перегородка ячейки типа "правый верхний угол —> левый нижний угол" имеет представление -1.
В каждом столбце сверху бросается ровно один мяч, а дорога из перегородок может уткнуть мяч либо в стену, либо дать спокойно выпасть снизу коробки.
Необходимо вернуть массив, который будет показывать добрался ли i-ый мяч до дна коробки (интерпретируется 1) или же уткнулся в стену (-1).
Пример:
Ввод: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Вывод: [1,-1,-1,-1,-1]
Объяснение: *во вложении
Ввод: grid = [[-1]]
Вывод: [-1]
Объяснение: мяч уткнется в левую стенку коробки
Решение задачи
👍8
Нахождение первой и последние позиций в отсортированном массиве
Сложность: Средняя
Условие задачи: дается целочисленный массив в порядке не убывания, необходимо найти первую и последнюю позиции целевого элемента, который надо отыскать.
Если целевого элемента нет в массиве, то надо вывести [-1; 1].
Алгоритм должен быть не медленнее, чем O(log n) по времени.
Пример:
Ввод: nums = [5,7,7,8,8,10], target = 8
Вывод: [3,4]
Объяснение:
Ввод: nums = [5,7,7,8,8,10], target = 6
Вывод: [-1,-1]
Решение задачи
Сложность: Средняя
Условие задачи: дается целочисленный массив в порядке не убывания, необходимо найти первую и последнюю позиции целевого элемента, который надо отыскать.
Если целевого элемента нет в массиве, то надо вывести [-1; 1].
Алгоритм должен быть не медленнее, чем O(log n) по времени.
Пример:
Ввод: nums = [5,7,7,8,8,10], target = 8
Вывод: [3,4]
Объяснение:
Ввод: nums = [5,7,7,8,8,10], target = 6
Вывод: [-1,-1]
Решение задачи
👍2
Пересечение интервала
Сложность: Средняя
Условие задачи: дается массив из непересекающихся интервалов, где первое число подсписка - начальная координата, а второе число - конечная координата. Также подается новый интервал.
Необходимо внедрить новый интервал в уже существующий список и вернуть полученный результат после вставки.
Пример:
Ввод: intervals = [[1,3],[6,9]], newInterval = [2,5]
Вывод: [[1,5],[6,9]]
Ввод: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Вывод: [[1,2],[3,10],[12,16]]
Решение задачи
Сложность: Средняя
Условие задачи: дается массив из непересекающихся интервалов, где первое число подсписка - начальная координата, а второе число - конечная координата. Также подается новый интервал.
Необходимо внедрить новый интервал в уже существующий список и вернуть полученный результат после вставки.
Пример:
Ввод: intervals = [[1,3],[6,9]], newInterval = [2,5]
Вывод: [[1,5],[6,9]]
Ввод: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Вывод: [[1,2],[3,10],[12,16]]
Решение задачи
👍2
Два огромных океана
Сложность: Средняя
Условие задачи: на вход подается двумерная матрица, которая отображает рельеф острова (чем больше значение в ячейке, тем выше рельеф в текущей точке относительно уровня моря), окруженного двумя океанами: Тихим и Атлантическим.
После того, как прошел бурный дождь по острову начала стекать вода. Жидкость может течь лишь в том направлении, где рельеф в текущей точке не меньше (по значению на решетке), чем рельеф в соседней.
Необходимо выявить точки, из которых дождевая вода может попасть и в Тихий океан и в Атлантический.
Пример:
Ввод: 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]]
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается двумерная матрица, которая отображает рельеф острова (чем больше значение в ячейке, тем выше рельеф в текущей точке относительно уровня моря), окруженного двумя океанами: Тихим и Атлантическим.
После того, как прошел бурный дождь по острову начала стекать вода. Жидкость может течь лишь в том направлении, где рельеф в текущей точке не меньше (по значению на решетке), чем рельеф в соседней.
Необходимо выявить точки, из которых дождевая вода может попасть и в Тихий океан и в Атлантический.
Пример:
Ввод: 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]]
Объяснение: *во вложении
Решение задачи
👍3
Бинарное дерево с правой стороны
Сложность: Средняя
Условие задачи: на вход подается бинарное дерево, представим, что стоим справа, необходимо вывезти значения, которые будут видны с этой стороны.
Пример:
Ввод: root = [1,2,3,null,5,null,4]
Вывод: [1,3,4]
Объяснение: * во вложении
Ввод: root = [1,null,3]
Вывод: [1, 3]
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается бинарное дерево, представим, что стоим справа, необходимо вывезти значения, которые будут видны с этой стороны.
Пример:
Ввод: root = [1,2,3,null,5,null,4]
Вывод: [1,3,4]
Объяснение: * во вложении
Ввод: root = [1,null,3]
Вывод: [1, 3]
Решение задачи
👍5
Префиксное дерево
Сложность: Средняя
Условие задачи: префиксное дерево - это структура данных для эффективного хранения и извлечения ключей в массиве строк.
Необходимо реализовать класс со следующими методами:
- Trie() - инициализатор;
- void insert(String word) - осуществляет вставку в экземпляр класса;
- boolean search(String word) - возвращает флаг о наличии слова word в дереве;
- boolean startsWith(String prefix) - возвращает флаг о том, начинается ли слово, вставленное на предыдущем шаге с prefix.
Пример:
Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Вывод: [null, null, true, false, true, null, true]
Объяснение:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Решение задачи
Сложность: Средняя
Условие задачи: префиксное дерево - это структура данных для эффективного хранения и извлечения ключей в массиве строк.
Необходимо реализовать класс со следующими методами:
- Trie() - инициализатор;
- void insert(String word) - осуществляет вставку в экземпляр класса;
- boolean search(String word) - возвращает флаг о наличии слова word в дереве;
- boolean startsWith(String prefix) - возвращает флаг о том, начинается ли слово, вставленное на предыдущем шаге с prefix.
Пример:
Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Вывод: [null, null, true, false, true, null, true]
Объяснение:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Решение задачи
👍2
Длина последнего слова
Сложность: Лёгкая
Условие задачи: на вход подается строка, состоящая из пробелов и слов. Необходимо посчитать длину последнего слова в строке.
Пример:
Ввод: s = "Hello World"
Вывод: 5
Объяснение: слово "World" имеет длину 5.
Ввод: s = " fly me to the moon "
Вывод: 4
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается строка, состоящая из пробелов и слов. Необходимо посчитать длину последнего слова в строке.
Пример:
Ввод: s = "Hello World"
Вывод: 5
Объяснение: слово "World" имеет длину 5.
Ввод: s = " fly me to the moon "
Вывод: 4
Решение задачи
👍5❤2🔥2
Площадь прямоугольников
Сложность: Средняя
Условие задачи: на вход подаются координаты двух прямоугольников (левый нижний угол, а также правый верхний угол).
Необходимо вычислить суммарную площадь, занимаемую двумя прямоугольниками.
Пример:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: на вход подаются координаты двух прямоугольников (левый нижний угол, а также правый верхний угол).
Необходимо вычислить суммарную площадь, занимаемую двумя прямоугольниками.
Пример:
Ввод:
ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2Вывод:
45Решение задачи
👍8
Подсчет узлов бинарного дерева
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
👍5🔥2
Комбинация сумм II
Сложность: Средняя
Условие задачи: на вход дается список возможных кандидатов и целевое значение суммы, необходимо вывести все комбинации, которыми можно получить целевое значение.
Каждое число из списка кандидатов должно содержаться в конечном подсписке из ответов ровно один раз.
Результирующий ответ не должен содержать в себе дубликатов.
Пример:
Ввод: candidates = [10,1,2,7,6,1,5], target = 8
Вывод: [
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Ввод: candidates = [2,5,2,1,2], target = 5
Вывод: [
[1,2,2],
[5]
]
Решение задачи
Сложность: Средняя
Условие задачи: на вход дается список возможных кандидатов и целевое значение суммы, необходимо вывести все комбинации, которыми можно получить целевое значение.
Каждое число из списка кандидатов должно содержаться в конечном подсписке из ответов ровно один раз.
Результирующий ответ не должен содержать в себе дубликатов.
Пример:
Ввод: candidates = [10,1,2,7,6,1,5], target = 8
Вывод: [
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Ввод: candidates = [2,5,2,1,2], target = 5
Вывод: [
[1,2,2],
[5]
]
Решение задачи
👍4👎1