Поиск суммы в бинарном дереве поиска
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
root = [5,3,6,2,4,null,7], k = 9Вывод:
trueВвод:
root = [5,3,6,2,4,null,7], k = 28Вывод:
falseРешение задачи
👍2
Калькулятор II
Сложность: Средняя
Условие задачи: на вход подается строка, которая представляет математическое выражение. Необходимо вывести результат математического выражения.
Целочисленное деление округляет число в сторону нуля.
Нельзя пользоваться встроенными функциями.
Пример:
Ввод: s = "3+2*2"
Вывод: 7
Ввод: s = " 3/2 "
Вывод: 1
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается строка, которая представляет математическое выражение. Необходимо вывести результат математического выражения.
Целочисленное деление округляет число в сторону нуля.
Нельзя пользоваться встроенными функциями.
Пример:
Ввод: s = "3+2*2"
Вывод: 7
Ввод: s = " 3/2 "
Вывод: 1
Решение задачи
👍6❤1👎1
Наикратчайший путь в бинарной матрице
Сложность: Средняя
Условие задачи: дана квадратная матрица, необходимо посчитать длину (количество посещенных клеток) самой короткой тропы.
Путь должен соответствовать следующим условиям:
- начинаться в левой верхней клетке, заканчиваться в правой нижней;
- все ячейки по пути должны иметь нулевые значения;
- клетки по пути могут быть соединены в любом из 8-ми направлений.
В случае отсутствии подобного пути, вернуть -1.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 2
Ввод: grid = [[0,0,0],[1,1,0],[1,1,0]]
Вывод: 4
Решение задачи
Сложность: Средняя
Условие задачи: дана квадратная матрица, необходимо посчитать длину (количество посещенных клеток) самой короткой тропы.
Путь должен соответствовать следующим условиям:
- начинаться в левой верхней клетке, заканчиваться в правой нижней;
- все ячейки по пути должны иметь нулевые значения;
- клетки по пути могут быть соединены в любом из 8-ми направлений.
В случае отсутствии подобного пути, вернуть -1.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 2
Ввод: grid = [[0,0,0],[1,1,0],[1,1,0]]
Вывод: 4
Решение задачи
👍2
Сдвиг нулей
Сложность: Лёгкая
Условие задачи: дан массив, необходимо переместить все нулевые элементы к концу массива, к его правой границе.
Решение должно изменять исходный массив, не используя дополнительной памяти.
Пример:
Ввод: nums = [0,1,0,3,12]
Вывод: [1,3,12,0,0]
Ввод: nums = [0]
Вывод: [0]
Решение задачи
Сложность: Лёгкая
Условие задачи: дан массив, необходимо переместить все нулевые элементы к концу массива, к его правой границе.
Решение должно изменять исходный массив, не используя дополнительной памяти.
Пример:
Ввод: nums = [0,1,0,3,12]
Вывод: [1,3,12,0,0]
Ввод: nums = [0]
Вывод: [0]
Решение задачи
👍13
Содержание дубликатов II
Сложность: Лёгкая
Условие задачи: дается массив из целых чисел и число k. Необходимо вернуть true, если существуют два уникальных индекса, которые удовлетворяют условиям:
- nums[i] == nums[j];
- abs(i - j) <= k.
Пример:
Ввод: nums = [1,2,3,1], k = 3
Вывод: true
Ввод: nums = [1,0,1,1], k = 1
Вывод: true
Решение задачи
Сложность: Лёгкая
Условие задачи: дается массив из целых чисел и число k. Необходимо вернуть true, если существуют два уникальных индекса, которые удовлетворяют условиям:
- nums[i] == nums[j];
- abs(i - j) <= k.
Пример:
Ввод: nums = [1,2,3,1], k = 3
Вывод: true
Ввод: nums = [1,0,1,1], k = 1
Вывод: true
Решение задачи
👍6
Ключи и комнаты
Сложность: Средняя
Условие задачи: есть
При посещении какой-либо комнаты в ней находится определенная связка уникальных ключей, номер ключа означет номер комнаты, для которой он отпирает дверь. Можно использовать сразу все связку ключей.
На вход подается массив комнат, где в 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Решение задачи
👍4
Форматирование
Сложность: Лёгкая
Условие задачи: дается номер водительского удостоверения, представленный строкой. Символы в номере могут быть разбиты на n+1 групп. Также дается число k.
Необходимо преобразовать номер в строку по k-символов. Однако лишь первая группа может быть меньше, чем k-символов. Помимо этого все символы нижнего регистра необходимо изменить на верхний регистр.
Пример:
Ввод: s = "5F3Z-2e-9-w", k = 4
Вывод: "5F3Z-2E9W"
Объяснение:
Ввод: s = "2-5g-3-J", k = 2
Вывод: s = "2-5g-3-J", k = 2
Решение задачи
Сложность: Лёгкая
Условие задачи: дается номер водительского удостоверения, представленный строкой. Символы в номере могут быть разбиты на n+1 групп. Также дается число k.
Необходимо преобразовать номер в строку по k-символов. Однако лишь первая группа может быть меньше, чем k-символов. Помимо этого все символы нижнего регистра необходимо изменить на верхний регистр.
Пример:
Ввод: s = "5F3Z-2e-9-w", k = 4
Вывод: "5F3Z-2E9W"
Объяснение:
Ввод: s = "2-5g-3-J", k = 2
Вывод: s = "2-5g-3-J", k = 2
Решение задачи
👍4
Сумма на отрезке
Сложность: Лёгкая
Условие задачи: дается бинарное дерево поиска, дается два числа low и high, необходимо посчитать сумму узлов дерева, находящихся в пределах данного отрезка [low, high].
Пример:
Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15
Вывод: 32
Объяснение: в данный отрезок входят числа 7, 10, 15.
Решение задачи
Сложность: Лёгкая
Условие задачи: дается бинарное дерево поиска, дается два числа low и high, необходимо посчитать сумму узлов дерева, находящихся в пределах данного отрезка [low, high].
Пример:
Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15
Вывод: 32
Объяснение: в данный отрезок входят числа 7, 10, 15.
Решение задачи
👍2
Общая подпоследовательность наибольшей длины
Сложность: Средняя
Условие задачи: на вход подаются две строки, необходимо вывести их наидлиннейшую общую подпоследовательность, а точнее ее длину.
Подпоследовательность - совокупность символов, не обязательно смежных, идущих слева направо в том же порядке, что и в исходной строке.
Пример:
Ввод: text1 = "abcde", text2 = "ace"
Вывод: 3
Объяснение: "ace"
Ввод: text1 = "abc", text2 = "def"
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: на вход подаются две строки, необходимо вывести их наидлиннейшую общую подпоследовательность, а точнее ее длину.
Подпоследовательность - совокупность символов, не обязательно смежных, идущих слева направо в том же порядке, что и в исходной строке.
Пример:
Ввод: text1 = "abcde", text2 = "ace"
Вывод: 3
Объяснение: "ace"
Ввод: text1 = "abc", text2 = "def"
Вывод: 0
Решение задачи
👍4
Выход из лабиринта
Сложность: Средняя
Условие задачи: на вход подается двумерный массив, отражающий карту лабиринта ('.' - пустая ячейка, ' + ' - стена). Также на вход подается массив со входом, обозначающий изначальное положение, откуда будет искаться выход.
Двигаться можно лишь в четырёх направлениях: лево, право, верх, низ.
Необходимо вычислить количество шагов до ближайшего выхода или же вернуть -1 в случае отсутствия такового.
Пример:
Ввод: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Вывод: 1
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается двумерный массив, отражающий карту лабиринта ('.' - пустая ячейка, ' + ' - стена). Также на вход подается массив со входом, обозначающий изначальное положение, откуда будет искаться выход.
Двигаться можно лишь в четырёх направлениях: лево, право, верх, низ.
Необходимо вычислить количество шагов до ближайшего выхода или же вернуть -1 в случае отсутствия такового.
Пример:
Ввод: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Вывод: 1
Объяснение: *во вложении
Решение задачи
👍1
Максимальное число из 6 и 9
Сложность: Лёгкая
Условие задачи: дается число, полностью состоящее из 6 и 9. Необходимо вычислить наибольшее число в данной раскладке, при этом имея возможность заменить не более одной шестерки на девятку.
Пример:
Ввод: num = 9669
Вывод: 9969
Ввод: num = 9996
Вывод: 9999
Решение задачи
Сложность: Лёгкая
Условие задачи: дается число, полностью состоящее из 6 и 9. Необходимо вычислить наибольшее число в данной раскладке, при этом имея возможность заменить не более одной шестерки на девятку.
Пример:
Ввод: num = 9669
Вывод: 9969
Ввод: num = 9996
Вывод: 9999
Решение задачи
👍1
Нахождение существующего пути
Сложность: Лёгкая
Условие задачи: дается ненаправленный граф, ребра которого представлены в массиве. Между каждой парой узлов в дереве имеется не более одного ребра.
Необходимо определить существует ли корректная дорога между узлом source и destination.
Пример:
Ввод: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Вывод: true
Объяснение: *во вложении
Ввод: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: дается ненаправленный граф, ребра которого представлены в массиве. Между каждой парой узлов в дереве имеется не более одного ребра.
Необходимо определить существует ли корректная дорога между узлом source и destination.
Пример:
Ввод: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Вывод: true
Объяснение: *во вложении
Ввод: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Вывод: false
Решение задачи
👍2
Наиближайшая сумма трёх
Сложность: Средняя
Условие задачи: дан целочисленный массив и целевое значение суммы. Необходимо найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.
Каждый массив имеет единственное решение.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дан целочисленный массив и целевое значение суммы. Необходимо найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.
Каждый массив имеет единственное решение.
Пример:
Ввод:
nums = [-1,2,1,-4], target = 1Вывод:
2Объяснение:
(-1 + 2 + 1 = 2)Ввод:
nums = [0,0,0], target = 1Вывод:
0Решение задачи
👍1
Проверка схожести половин строки
Сложность: Лёгкая
Условие задачи: на вход подается строка четной длины. Далее проводится разделение на две равные части.
Две строки называются схожими, если в них находится одно и то же количество гласных вне зависимости от регистра.
Необходимо проверить схожесть двух строк, полученных разбиением по середине.
Пример:
Ввод: s = "book"
Вывод: true
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается строка четной длины. Далее проводится разделение на две равные части.
Две строки называются схожими, если в них находится одно и то же количество гласных вне зависимости от регистра.
Необходимо проверить схожесть двух строк, полученных разбиением по середине.
Пример:
Ввод: s = "book"
Вывод: true
Решение задачи
👍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]Решение задачи
👍4
Столбцы таблицы Excel
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается номер столбца, необходимо конвертировать его в буквенное представление, которое будет использоваться в таблице-Excel.
Пример:
Ввод:columnNumber = 1
Вывод: "A"
Ввод: columnNumber = 28
Вывод: "AB"
Решение задачи
👍2
Максимальное количество сумок, полностью заполненных камнями
Сложность: Средняя
Условие задачи: дается n-сумок, пронумерованных с нуля. Дается также два массива, проиндексированных аналогичным образом: capacity и rocks. i-а сумка может вмещать capacity[i] камней и в текущий момент содержит уже rocks[i] каменей. Помимо этого дается еще additionalRocks, число камней, которые можно добавить в произвольную сумку.
Необходимо вычислить максимальное количество сумок, которое получится при ситуации, когда все дополнительные камни размещены.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается n-сумок, пронумерованных с нуля. Дается также два массива, проиндексированных аналогичным образом: capacity и rocks. i-а сумка может вмещать capacity[i] камней и в текущий момент содержит уже rocks[i] каменей. Помимо этого дается еще additionalRocks, число камней, которые можно добавить в произвольную сумку.
Необходимо вычислить максимальное количество сумок, которое получится при ситуации, когда все дополнительные камни размещены.
Пример:
Ввод:
capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2Вывод:
3Ввод:
capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100Вывод:
3Решение задачи
👍2
Раскладка костей
Сложность: Средняя
Условие задачи: есть два типа костей: типа domino и типа tromino.
Дается целое число n, необходимо вычислить количество комбинаций чтобы выложить поле размером 2 x n при помощи двух типов костей.
При укладке плитки каждый квадрат должен быть покрыт плиткой. Две плитки различны тогда и только тогда, когда на доске есть две смежные в 4 направлениях ячейки, такие, что ровно в одной из плиток оба квадрата заняты плиткой.
Пример:
Ввод: n = 3
Вывод: 5
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: есть два типа костей: типа domino и типа tromino.
Дается целое число n, необходимо вычислить количество комбинаций чтобы выложить поле размером 2 x n при помощи двух типов костей.
При укладке плитки каждый квадрат должен быть покрыт плиткой. Две плитки различны тогда и только тогда, когда на доске есть две смежные в 4 направлениях ячейки, такие, что ровно в одной из плиток оба квадрата заняты плиткой.
Пример:
Ввод: n = 3
Вывод: 5
Объяснение: *во вложении
Решение задачи
👍1
Идеальное число
Сложность: Лёгкая
Условие задачи: идеальное число - это положительное целое число, которое равно сумме делителей этого же числа, за исключением самого числа.
Необходимо проверить входное число на идеальность.
Пример:
Ввод: num = 28
Вывод: true
Объяснение: 28 = 1 + 2 + 4 + 7 + 14
Ввод: num = 7
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: идеальное число - это положительное целое число, которое равно сумме делителей этого же числа, за исключением самого числа.
Необходимо проверить входное число на идеальность.
Пример:
Ввод: num = 28
Вывод: true
Объяснение: 28 = 1 + 2 + 4 + 7 + 14
Ввод: num = 7
Вывод: false
Решение задачи
👍3
Минимальное количество ребер
Сложность: Средняя
Условие задачи: дается ациклический направленный граф с вершинами, пронумерованными от 0 до n-1.
Необходимо найти наименьшее количество ребер в графе такое что, можно было бы обойти все узлы.
Пример:
Ввод: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Вывод: [0,3]
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается ациклический направленный граф с вершинами, пронумерованными от 0 до n-1.
Необходимо найти наименьшее количество ребер в графе такое что, можно было бы обойти все узлы.
Пример:
Ввод: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Вывод: [0,3]
Объяснение: *во вложении
Решение задачи
👍1