Наикратчайший путь в бинарной матрице
Сложность: Средняя
Условие задачи: дана квадратная матрица, необходимо посчитать длину (количество посещенных клеток) самой короткой тропы.
Путь должен соответствовать следующим условиям:
- начинаться в левой верхней клетке, заканчиваться в правой нижней;
- все ячейки по пути должны иметь нулевые значения;
- клетки по пути могут быть соединены в любом из 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
Решение задачи
👍5
Далеко на сколько это возможно
Сложность: Средняя
Условие задачи: дан двумерный массив, где 0 - вода, 1 - часть суши. Надо найти расстояние. Расстояние представляет из себя максимальную дистанцию от клетки с водой до ближайшей части суши.
Измерение расстояния происходит через вычисление Манхэттенского пути (дистания между двумя клетками
Ввод:
Ввод:
Сложность: Средняя
Условие задачи: дан двумерный массив, где 0 - вода, 1 - часть суши. Надо найти расстояние. Расстояние представляет из себя максимальную дистанцию от клетки с водой до ближайшей части суши.
Измерение расстояния происходит через вычисление Манхэттенского пути (дистания между двумя клетками
(x0, y0) и (x1, y1): |x0 - x1| + |y0 - y1|
Пример:Ввод:
grid = [[1,0,1],[0,0,0],[1,0,1]]
Вывод: 2Ввод:
grid = [[1,0,0],[0,0,0],[0,0,0]]
Вывод: 4
Решение задачи👍2
Счастливое число
Сложность: Лёгкая
Условие задачи: требуется написать алгоритм, определяющий является ли число счастливым.
Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: требуется написать алгоритм, определяющий является ли число счастливым.
Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.
Пример:
Ввод:
n = 19
Вывод: true
Объяснение: 1 + 81 = 82
64 + 4 = 68
36 + 64 = 100
1 + 0 + 0 = 1
Ввод: n = 2
Вывод: false
Решение задачи🤔7👍2
Forwarded from Дмитрий
Количество изолированных островов
Сложность: Средняя
Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду).
Остров - множество нулей, соединенных в четырех направлениях (справа, снизу, слева, сверху), изолированый остров - множество нулей, окруженных со всех сторон единицами.
Надо посчитать количество изолированных островов.
Пример:
Ввод: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Вывод: 2
Объяснение:
Ввод: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Вывод: 1
Решение задачи
Сложность: Средняя
Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду).
Остров - множество нулей, соединенных в четырех направлениях (справа, снизу, слева, сверху), изолированый остров - множество нулей, окруженных со всех сторон единицами.
Надо посчитать количество изолированных островов.
Пример:
Ввод: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Вывод: 2
Объяснение:
Ввод: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Вывод: 1
Решение задачи
👍2
Столкновение астероидов
Сложность: Средняя
Условие задачи: дан массив астероидов (каждое значение - вес астероида, а знак - направление движения). Каждый из астероидов двигается с одинаковой скоростью.
При столкновени двух астероидов, асторид с меньшим весов уничтожается (у целого астероида вес остается неизменным после столкновения).
Вывести надо результирующий массив после всевозможных столкновений.
Пример:
Ввод:
Ввод:
Решение задачи
Сложность: Средняя
Условие задачи: дан массив астероидов (каждое значение - вес астероида, а знак - направление движения). Каждый из астероидов двигается с одинаковой скоростью.
При столкновени двух астероидов, асторид с меньшим весов уничтожается (у целого астероида вес остается неизменным после столкновения).
Вывести надо результирующий массив после всевозможных столкновений.
Пример:
Ввод:
asteroids = [5,10,-5]
Вывод: [5,10]
Объяснение: 3-ий астероид сталкивается со 2-ым и уничтожается. Ввод:
asteroids = [8,-8]
Вывод: [ ]Решение задачи
👎3👍1
Квадраты отсортированного массива
Сложность: Лёгкая
Условие задачи: дан массив, отсортированный в порядке неубывания. Надо вернуть массив (также отсортированный), состоящий из элементов первого массива, возведенных во вторую степень.
Пример:
Ввод:
Вывод:
Объяснение: после возведения в квадрат получаем следующий массив -
Ввод:
Вывод:
Решить задачу надо за линейное время.
Решение задачи
Сложность: Лёгкая
Условие задачи: дан массив, отсортированный в порядке неубывания. Надо вернуть массив (также отсортированный), состоящий из элементов первого массива, возведенных во вторую степень.
Пример:
Ввод:
nums = [-4,-1,0,3,10]Вывод:
[0,1,9,16,100]Объяснение: после возведения в квадрат получаем следующий массив -
[16,1,0,9,100], а результирующий будет выглядеть следующим образом - 0,1,9,16,100]. Ввод:
nums = [-7,-3,2,3,11]Вывод:
[4,9,9,49,121]Решить задачу надо за линейное время.
Решение задачи
👍4
Палиндром наибольшей длины, полученный с помощью соединений из слов, состоящих из двух букв
Сложность: Средняя
Условие задачи: дан массив строк, каждый элемент которого состоит из двух букв английского алфавита в нижнем регистре.
Необходимо создать палиндром наибольшей длины путем выбора некоторых элементов из массива строк и компаниовки их в любом порядке. Каждый элемент массива можно использовать не более одного раза.
В ответе надо вернуть длину такого палидрома.
Палиндром - строка, одинаково читающаяся в обоих направлениях.
Пример:
Ввод:
Объяснение:
Ввод:
Объяснение:
Сложность: Средняя
Условие задачи: дан массив строк, каждый элемент которого состоит из двух букв английского алфавита в нижнем регистре.
Необходимо создать палиндром наибольшей длины путем выбора некоторых элементов из массива строк и компаниовки их в любом порядке. Каждый элемент массива можно использовать не более одного раза.
В ответе надо вернуть длину такого палидрома.
Палиндром - строка, одинаково читающаяся в обоих направлениях.
Пример:
Ввод:
words = ["lc","cl","gg"]
Вывод: 6Объяснение:
lc" + "gg" + "cl" = "lcggcl" или же "clgglc", но оба имеют максимальную длину 6. Ввод:
words = ["ab","ty","yt","lc","cl","ab"]
Вывод: 8 Объяснение:
"ty" + "lc" + "cl" + "yt" = "tylcclyt" или "lcyttycl"
Ввод: words = ["cc","ll","xx"]
Вывод: 2
Решение задачи👍4
Связный список-палидром
Сложность: Лёгкая
Условие задачи: дан связный список, необходимо осуществить проверку на то являтеся ли он палиндромом или же нет?
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дан связный список, необходимо осуществить проверку на то являтеся ли он палиндромом или же нет?
Пример:
Ввод:
head = [1,2,2,1]Вывод:
trueВвод:
head = [1,2]Вывод:
falseРешение задачи
👍4
Итератор бинарного дерева
Сложность: Средняя
Условие задачи: надо реализовать класс BSTIterator, представляющий из себя итератор вдоль бинарного дерева, сцепленного по правилу: левый потомок, корень, правый потомок.
Класс должен содержать в себе следующие методы:
- BSTIterator(TreeNode root). Данный метод инициализирует объект класса. root передаются в конструктор в качестве входного аргумента. Указатель должен быть инициализирован несуществующим числом, которое меньше любого из элементов бинарного дерева;
- boolean hasNext(). Возвращает true в случае если существует потомок у правого поддерева. В ином случае возвращает false;
- int next(). Перемещает указатель в правую ветвь, возвращая число в указателе.
При инициализации указатель на несуществующий наименьший элемент, вызывая метод next(), будет возвращать наименьший элемент бинарного дерева.
Пример:
Ввод:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Вывод: [null, 3, 7, true, 9, true, 15, true, 20, false]
Объяснение:
Сложность: Средняя
Условие задачи: надо реализовать класс BSTIterator, представляющий из себя итератор вдоль бинарного дерева, сцепленного по правилу: левый потомок, корень, правый потомок.
Класс должен содержать в себе следующие методы:
- BSTIterator(TreeNode root). Данный метод инициализирует объект класса. root передаются в конструктор в качестве входного аргумента. Указатель должен быть инициализирован несуществующим числом, которое меньше любого из элементов бинарного дерева;
- boolean hasNext(). Возвращает true в случае если существует потомок у правого поддерева. В ином случае возвращает false;
- int next(). Перемещает указатель в правую ветвь, возвращая число в указателе.
При инициализации указатель на несуществующий наименьший элемент, вызывая метод next(), будет возвращать наименьший элемент бинарного дерева.
Пример:
Ввод:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Вывод: [null, 3, 7, true, 9, true, 15, true, 20, false]
Объяснение:
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False
Решение задачи👍4
Удаление элементов из связного списка
Сложность: Лёгкая
Условие задачи: дан указетель на связный список и целое число (
Итогом должен быть возврат на начало изменненного списка (все опреции будут производиться непосредственно с самим списком).
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дан указетель на связный список и целое число (
val). Надо извлечь из сипска все узлыва, значение в которых равняется val. Итогом должен быть возврат на начало изменненного списка (все опреции будут производиться непосредственно с самим списком).
Пример:
Ввод:
head = [1,2,6,3,4,5,6], val = 6Вывод:
[1,2,3,4,5]Ввод:
head = [], val = 1Вывод:
[]Решение задачи
👍3
Расписание курсов
Сложность: Средняя
Условие задачи: дается количество курсов, сами курсы пронумерованны с нуля. Помимо этого дан массив, в котором хранятся зависимости. Зависимость
Ответ на задачу должен содержать в себе такую последовательность курсов, при которой все курсы будут пройдены.
Если невозможно осуществить проход по всем курсам, то в ответе надо вывести пустой массив.
Пример:
Ввод:
Ввод:
Сложность: Средняя
Условие задачи: дается количество курсов, сами курсы пронумерованны с нуля. Помимо этого дан массив, в котором хранятся зависимости. Зависимость
prerequisites[i] = [ai, bi] предполагает, что курс ai может быть пройден только в случае, если пройден курс bi. Ответ на задачу должен содержать в себе такую последовательность курсов, при которой все курсы будут пройдены.
Если невозможно осуществить проход по всем курсам, то в ответе надо вывести пустой массив.
Пример:
Ввод:
numCourses = 2, prerequisites = [[1,0]]
Вывод: [0,1]
Объяснение: чтобы пройти все курсы, изначально надо пройти курс под номером "0", а после имеется возможность пройти курс под номером "1". Ввод:
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Вывод: [0,2,1,3]
Решение задачи👍3🎉1
Наиближайший общий предок
Сложность: Средняя
Условие задачи: дано бинарное дерево поиска, надо найти ближайшего родителя для обоих потомков.
Наиближайший общий родитель определяется между двумя узлами p и q как наименьший узел в дереве, который имеет как p, так и q в качестве потомков (где мы разрешаем узлу быть потомком самого себя).
Пример:
Ввод:
Вывод:
Объяснение: *на картинке
Решение задачи
Сложность: Средняя
Условие задачи: дано бинарное дерево поиска, надо найти ближайшего родителя для обоих потомков.
Наиближайший общий родитель определяется между двумя узлами p и q как наименьший узел в дереве, который имеет как p, так и q в качестве потомков (где мы разрешаем узлу быть потомком самого себя).
Пример:
Ввод:
[6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8Вывод:
6Объяснение: *на картинке
Решение задачи
👍1
Суммы чисел
Условие задачи:
Даётся массив целых чисел и целочисленное целевое значение, требуется вернуть индексы двух чисел так, чтобы в сумме они составляли целевое значение. Каждый случай имеет ровно одно решение, и нельзя использовать один и тот же элемент дважды. Ответ можно вернуть в любом порядке.
Примеры:
Ввод:
Ввод:
Условие задачи:
Даётся массив целых чисел и целочисленное целевое значение, требуется вернуть индексы двух чисел так, чтобы в сумме они составляли целевое значение. Каждый случай имеет ровно одно решение, и нельзя использовать один и тот же элемент дважды. Ответ можно вернуть в любом порядке.
Примеры:
Ввод:
nums = [2,7,11,15], target = 9
Вывод: [0,1]
Поскольку nums [0] + nums [1] == 9, мы возвращаем [0, 1].Ввод:
nums = [3,2,4], target = 6
Вывод: [1,2]
Ввод: nums = [3,3], target = 6
Вывод: [0,1]
Решение задачи👍3
Подмножества II
Сложность задачи: Средняя
Условие задачи:
Получив целочисленный массив nums, который может содержать дубликаты, вернуть все возможные подмножества (множество мощности).
Множество-решение не должно содержать повторяющихся подмножеств.
Примеры:
Ввод:
Сложность задачи: Средняя
Условие задачи:
Получив целочисленный массив nums, который может содержать дубликаты, вернуть все возможные подмножества (множество мощности).
Множество-решение не должно содержать повторяющихся подмножеств.
Примеры:
Ввод:
nums = [1,2,2]
Вывод: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Ввод: nums = [0]
Вывод: [[],[0]]
Решение задачи👍5👎3
Наименьший элемент в сдвинутом отсортированном массиве
Сложность: Средняя
Условие задачи: дан массив длины n, в порядке возрастания. При этом сдвинутый от 1 до n раз.
Например для массива nums = [0,1,2,4,5,6,7] получим:
[4,5,6,7,0,1,2] если сдвинуть 4 раза.
[0,1,2,4,5,6,7] если сдвинуть 7 раз.
Все элементы в массиве уникальные, надо отыскать в нем минимальный.
Решение должно быть за O(log n) по времени.
Пример:
Ввод: nums = [3,4,5,1,2]
Вывод: 1
Решение задачи
Сложность: Средняя
Условие задачи: дан массив длины n, в порядке возрастания. При этом сдвинутый от 1 до n раз.
Например для массива nums = [0,1,2,4,5,6,7] получим:
[4,5,6,7,0,1,2] если сдвинуть 4 раза.
[0,1,2,4,5,6,7] если сдвинуть 7 раз.
Все элементы в массиве уникальные, надо отыскать в нем минимальный.
Решение должно быть за O(log n) по времени.
Пример:
Ввод: nums = [3,4,5,1,2]
Вывод: 1
Решение задачи
👍2
Преобразование параметров матрицы
Сложность: Лёгкая
Условие задачи: дана матрица (
Значения в новой матрицы должны быть взяты из исходной.
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: дана матрица (
m x n), необходимо выполнить преобразования чтобы матрица имела параметры количества строк и столбцов (r x c). Значения в новой матрицы должны быть взяты из исходной.
Пример:
Ввод:
mat = [[1,2],[3,4]], r = 1, c = 4
Вывод: [[1,2,3,4]]
Ввод: mat = [[1,2],[3,4]], r = 2, c = 4
Вывод: [[1,2],[3,4]]
Решение задачи👍3❤1👎1
Удаление дубликатов из отсортированного связного списка
Сложность: Средняя
Условие задачи: дается указатель на начало отсортированного связного списка, необходимо удалить все дублируемые значения в списке. Надо вернуть связный список, также отсортированный.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается указатель на начало отсортированного связного списка, необходимо удалить все дублируемые значения в списке. Надо вернуть связный список, также отсортированный.
Пример:
Ввод:
head = [1,2,3,3,4,4,5]Вывод:
[1,2,5]Ввод:
head = [1,1,1,2,3]Вывод:
[2,3]Решение задачи
👍4
Прямой обход дерева
Сложность: Лёгкая
Условие задачи: дано дерево, необходимо преобразовать дерево прямого прохода (корень -> левый потомок -> правый потомок).
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: дано дерево, необходимо преобразовать дерево прямого прохода (корень -> левый потомок -> правый потомок).
Пример:
Ввод:
root = [1,null,3,2,4,null,5,6]
Вывод: [1,3,5,6,2,4]
Ввод: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Вывод: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Решение задачи👍3
К-ый наименьший элемент в бинарном дереве поиска
Сложность: Средняя
Условие задачи: на вход подается бинарное дерево поиска, необходимо осуществить в нем поиск К-наименьшего элемента (при условии индексирования с 1).
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается бинарное дерево поиска, необходимо осуществить в нем поиск К-наименьшего элемента (при условии индексирования с 1).
Пример:
Ввод:
root = [3,1,4,null,2], k = 1Вывод:
1Объяснение:
Ввод:
root = [5,3,6,2,4,null,null,1], k = 3Вывод:
3Решение задачи
👍3
Первая плохая версия
Сложность: Лёгкая
Условие задачи: производится разработка нового программного продукта, и на последней проверке было выявлено, что версия ПО не прошла проверку качества. Каждая следующая версия зависит от предыдущей, то есть если текущая версия не проходит проверки, то все последующие также не годны для какого-либо обслуживания.
Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.
Также дается интерфейс
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: производится разработка нового программного продукта, и на последней проверке было выявлено, что версия ПО не прошла проверку качества. Каждая следующая версия зависит от предыдущей, то есть если текущая версия не проходит проверки, то все последующие также не годны для какого-либо обслуживания.
Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.
Также дается интерфейс
bool isBadVersion(version), который производит проверку на то, является ли проверяемая версия неисправной. Решить задачу необходимо за минимальное количество вызовов чекера. Пример:
Ввод:
n = 5, bad = 4Вывод:
4Объяснение:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
4 - первая испорченная версия.Ввод:
Вывод:
Решение задачи
👍6
Мутация генов
Сложность: Средняя
Условие задачи: подается 8-символьная строка, состоящая из символов:
Необходимо осуществить расследование мутации от начального гена до конечного.
Пример одной мутации:
Помимо этого есть хранилицще генов, в котором хранятся всевозможные вариации мутаций, которые могут происходить.
Задача следующая, дается начальный и конечный гены, а также банк мутаций, необходимо вычислить наименьшее количество мутации, чтобы прийти к конечному результату. Если не существует таких преобразований для получения требуемого результата, надо вернуть -1.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: подается 8-символьная строка, состоящая из символов:
'A', 'C', 'G', и 'T'. Необходимо осуществить расследование мутации от начального гена до конечного.
Пример одной мутации:
"AACCGGTT" --> "AACCGGTA". Помимо этого есть хранилицще генов, в котором хранятся всевозможные вариации мутаций, которые могут происходить.
Задача следующая, дается начальный и конечный гены, а также банк мутаций, необходимо вычислить наименьшее количество мутации, чтобы прийти к конечному результату. Если не существует таких преобразований для получения требуемого результата, надо вернуть -1.
Пример:
Ввод:
start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]Вывод:
1Ввод:
start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]Вывод:
2Решение задачи
👍3