Определение количества островов
Сложность: Средняя
Условие задачи: дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Требуется опеределить количество островов, расположенных на карте.
Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.
Пример:
Ввод:
Ввод:
Решение задачи
Сложность: Средняя
Условие задачи: дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Требуется опеределить количество островов, расположенных на карте.
Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.
Пример:
Ввод:
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Вывод: 1Ввод:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Вывод: 3Решение задачи
👍6
Создание скобок
Для заданных n пар скобок напишите функцию, генерирующую все комбинации правильных пар скобок.
Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]
Ввод: n = 1
Вывод: ["()"]
Решение задачи
Для заданных n пар скобок напишите функцию, генерирующую все комбинации правильных пар скобок.
Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]
Ввод: n = 1
Вывод: ["()"]
Решение задачи
👍4
Мокрые бандиты
Сложность: Средняя
Условие задачи: Мы - профессиональные грабители, обчищающие дома под Рождество и в каждом ограбленном нами доме оставляем характерный символ: невыключенный кран с водой.
Перед нами стоит задача: ограбить на максимальную сумму дома, находящиеся на проспекте Линкольна, но у данных домов есть характерная черта: при ограбление соседних домов срабатывает сигнализация, вызывающая полицию.
Нам необходимо выяснить какие дома надо ограбить, чтобы получить максимальный куш.
Пример:
Ввод:
Сложность: Средняя
Условие задачи: Мы - профессиональные грабители, обчищающие дома под Рождество и в каждом ограбленном нами доме оставляем характерный символ: невыключенный кран с водой.
Перед нами стоит задача: ограбить на максимальную сумму дома, находящиеся на проспекте Линкольна, но у данных домов есть характерная черта: при ограбление соседних домов срабатывает сигнализация, вызывающая полицию.
Нам необходимо выяснить какие дома надо ограбить, чтобы получить максимальный куш.
Пример:
Ввод:
nums = [1,2,3,1]
Вывод: 4
Объяснение: Грабим 1-ый дом (money = 1), а после навещаем 3-ий дом (money = 3).
Суммарный куш: 1 + 3 = 4.
Решение задачи👍2
Строки отличающиеся на один символ
Сложность задачи: Средняя
Условие задачи:
Дан список строк dict, где все строки имеют одинаковую длину.
Верните true, если в одном и том же индексе есть 2 строки, которые отличаются только на 1 символ, в противном случае возвращает false.
Пример:
Ввод:
Ввод:
Сложность задачи: Средняя
Условие задачи:
Дан список строк dict, где все строки имеют одинаковую длину.
Верните true, если в одном и том же индексе есть 2 строки, которые отличаются только на 1 символ, в противном случае возвращает false.
Пример:
Ввод:
dict = ["abcd","acbd", "aacd"]
Вывод: true
Объяснение: Строки "abcd" и "aacd" отличаются только одним символом в индексе 1.Ввод:
dict = ["ab","cd","yz"]
Вывод: false
Решение задачи👍4
Проверка бинарного дерева
Сложность: Средняя
Условие задачи: требуется проверить является ли исходное дерево бинарным деревом поиска.
Правильное бинарное дерево удовлетворяет следующим условиям:
- элементы левого поддеревоа должно быть меньше родителя.
- элементы правого поддерева должны быть больше, чем значение в родительском узле.
- левое и правое поддеревья должны быть также бинарными деревьями поиска.
Пример:
Ввод:
Вывод: False
Объяснение: 4 < 5, но при этом находится в правом поддереве.
Ввод:
Вывод: True
Решение задачи
Сложность: Средняя
Условие задачи: требуется проверить является ли исходное дерево бинарным деревом поиска.
Правильное бинарное дерево удовлетворяет следующим условиям:
- элементы левого поддеревоа должно быть меньше родителя.
- элементы правого поддерева должны быть больше, чем значение в родительском узле.
- левое и правое поддеревья должны быть также бинарными деревьями поиска.
Пример:
Ввод:
root = [5,1,4,null,null,3,6]Вывод: False
Объяснение: 4 < 5, но при этом находится в правом поддереве.
Ввод:
root = [2,1,3]Вывод: True
Решение задачи
👍4
Самая длинная подстрока без повторений
Сложность: Средняя.
Условие задачи: дана строка надо найти самую длинную подстроку, в которой не будет повторений.
Пример:
Ввод:
Ввод:
Сложность: Средняя.
Условие задачи: дана строка надо найти самую длинную подстроку, в которой не будет повторений.
Пример:
Ввод:
s = "abcabcbb"
Вывод: 3
Объяснение: ответом является подстрока "abc", длина которой равна 3. Ввод:
s = "bbbbb"
Вывод: 1
Ввод: s = "pwwkew"
Вывод: 3
Объяснение: ответ - "wke" (длина = 3).
Решение задачи👍5
Объединить два отсортированных списка
Вам даны head’ы двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем соединения узлов первых двух списков. Верните head объединенного связанного списка.
Пример 1 (на картинке):
Ввод: list1 = [1,2,4], list2 = [1,3,4]
Вывод: [1,1,2,3,4,4]
Пример 2:
Ввод: list1 = [], list2 = []
Вывод: []
Пример 3:
Ввод: list1 = [], list2 = [0]
Вывод: [0]
Решение задачи
Вам даны head’ы двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем соединения узлов первых двух списков. Верните head объединенного связанного списка.
Пример 1 (на картинке):
Ввод: list1 = [1,2,4], list2 = [1,3,4]
Вывод: [1,1,2,3,4,4]
Пример 2:
Ввод: list1 = [], list2 = []
Вывод: []
Пример 3:
Ввод: list1 = [], list2 = [0]
Вывод: [0]
Решение задачи
👍4
То же дерево
Сложность задачи:
Низкая
Условие:
Получив корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.
Примеры (картинки по порядку):
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true
Ввод: p = [1,2], q = [1,null,2]
Вывод: false
Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false
Ограничения:
Количество узлов в обоих деревьях находится в диапазоне [0, 100].
Решение задачи
Сложность задачи:
Низкая
Условие:
Получив корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.
Примеры (картинки по порядку):
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true
Ввод: p = [1,2], q = [1,null,2]
Вывод: false
Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false
Ограничения:
Количество узлов в обоих деревьях находится в диапазоне [0, 100].
Решение задачи
Конференц-залы II
Сложность задачи: Средняя
Условие задачи:
Дан массив интервалов времени проведения совещаний, intervals, где intervals[i] = [start(i), end(i)]. Найдите минимальное требуемое количество конференц-залов.
Пример:
Ввод:
Сложность задачи: Средняя
Условие задачи:
Дан массив интервалов времени проведения совещаний, intervals, где intervals[i] = [start(i), end(i)]. Найдите минимальное требуемое количество конференц-залов.
Пример:
Ввод:
intervals = [[0,30],[5,10],[15,20]]
Вывод: 2
Ввод: intervals = [[7,10],[2,4]]
Вывод: 1
Решение задачи👍5
Комбинации
Сложность: Средняя
Условие задачи: даны два целых положительных числа
Пример:
Ввод:
Ввод:
Сложность: Средняя
Условие задачи: даны два целых положительных числа
n и k. Надо вывести все комибинации, состоящие из k-чисел в диапазоне [1, n]. Пример:
Ввод:
n = 4, k = 2
Вывод:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Объяснение: число перестановок равно 6. Важным моментом является неупорядоченность чисел внутри самих комбинаций, то есть пары [1,2] и [2,1] являются одинаковыми. Ввод:
n = 1, k = 1
Вывод: [[1]]
Решение задачи👍4
Далеко на сколько это возможно
Сложность: Средняя
Условие задачи: дан двумерный массив, где 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
Решение задачи👍3
Изъятие дубликатов из односвязного списка
Сложность: Лёгкая
Условие задачи: дан отсортированный по значениям односвязный список. Нужно удалить из него все дублирующиеся элементы и вернуть также остортриованный список.
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: дан отсортированный по значениям односвязный список. Нужно удалить из него все дублирующиеся элементы и вернуть также остортриованный список.
Пример:
Ввод:
head = [1,1,2]
Вывод: [1,2]
Ввод: head = [1,1,2,3,3]
Вывод: [1,2,3]
Решение задачи👍3
Сцепка бинарного дерева
Сложность: Средняя
Условие задачи: дано бинарное дерево, необходимо вернуть элементы данного дерева, находящиеся на одном уровне.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дано бинарное дерево, необходимо вернуть элементы данного дерева, находящиеся на одном уровне.
Пример:
Ввод:
root = [3,9,20,null,null,15,7]Вывод:
[[3],[9,20],[15,7]]Объяснение:
Ввод:
root = [1]Вывод:
[[1]]Решение задачи
Проверка симметричности дерева
Сложность: Лёгкая
Условие задачи: дано бинарное дерево, надо удостовериться, является ли дерево отзеркаленным или нет.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево, надо удостовериться, является ли дерево отзеркаленным или нет.
Пример:
Ввод:
root = [1,2,2,3,4,4,3]Вывод:
trueВвод:
root =[1,2,2,null,3,null,3]Вывод:
falseРешение задачи
👍2
Реализация класса MinStack
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:
-
-
-
-
Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).
Пример:
Ввод:
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:
-
void push(int val), который добавляет элемент в стак;-
void pop(), удаляющий верхний элемент стака;-
int top(), возвращающий верхний элемент на стаке;-
int getMin(), возвращающий минимальный элемент в стаке на момент вызова метода. Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).
Пример:
Ввод:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Вывод:[null,null,null,null,-3,null,0,-2]
Объяснение:MinStack minStack = новый объект класса MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Решение задачи👍1
Матрица Топлица
Сложность: Лёгкая Средняя Тяжёлая
Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.
Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.
Пример:
Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true
Решение задачи
Сложность: Лёгкая Средняя Тяжёлая
Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.
Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.
Пример:
Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true
Решение задачи
👍5
Перелет с наименьшей ценой
Сложность: Средняя
Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.
Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.
Пример:
Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700
Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200
Решение задачи
Сложность: Средняя
Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.
Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.
Пример:
Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700
Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200
Решение задачи
👍4❤1
Треугольник
Сложность: Средняя
Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на i-ой позиции можно перемещаться на i-ую или i+1 позицию следующего ряда.
Пример:
Ввод:
Объяснение:
Минимальный путь выглядит следующим образом:
Решение задачи
Сложность: Средняя
Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на i-ой позиции можно перемещаться на i-ую или i+1 позицию следующего ряда.
Пример:
Ввод:
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Вывод: 11
Объяснение:
треуголльник выглядит следующим образом:
2
3 4
6 5 7
4 1 8 3
Минимальный путь выглядит следующим образом:
2 + 3 + 5 + 1 = 11.Решение задачи
👍3❤1
Комбинация сумм 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]
]
Решение задачи
👍2
Самая длинная счастливая строка
Сложность задачи: Средняя
Условие задачи:
Строка s называется счастливой, если она удовлетворяет следующим условиям:
• s содержит только буквы «a», «b» и «c».
• s не содержит подстроки «aaa», «bbb» или «ccc».
• s содержит не более a вхождений буквы «a».
• s содержит не более b вхождений буквы «b».
• s содержит не более c вхождений буквы 'c'.
Даны три целых числа a, b и c, вернуть максимально длинную счастливую строку. Если есть несколько самых длинных счастливых строк, верните любую из них. Если такой строки нет, вернуть пустую строку "".
Пример:
Ввод: a = 1, b = 1, c = 7
Вывод: "ccaccbcc"
Пояснение: «ccbccacc» также будет правильным ответом.
Решение задачи
Сложность задачи: Средняя
Условие задачи:
Строка s называется счастливой, если она удовлетворяет следующим условиям:
• s содержит только буквы «a», «b» и «c».
• s не содержит подстроки «aaa», «bbb» или «ccc».
• s содержит не более a вхождений буквы «a».
• s содержит не более b вхождений буквы «b».
• s содержит не более c вхождений буквы 'c'.
Даны три целых числа a, b и c, вернуть максимально длинную счастливую строку. Если есть несколько самых длинных счастливых строк, верните любую из них. Если такой строки нет, вернуть пустую строку "".
Пример:
Ввод: a = 1, b = 1, c = 7
Вывод: "ccaccbcc"
Пояснение: «ccbccacc» также будет правильным ответом.
Решение задачи
👍2
Количество анклавов
Сложность: Средняя
Условие задачи: дана двумерная решетка, где 0 - море, 1 - суша.
Движения могут осуществляться в одном из четрыех направлений: вверх, вниз, вправо, влево.
Необходимо посчитать количество анклавов. Анклавом является участок суши, который не прилегает ни к одной из границ заданной площадки.
Пример:
Ввод: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Вывод: 3
Объяснение: на данном поле есть три участка суши, отделенных от границ водой, и один элемент, прилегающий к границе.
Ввод: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: дана двумерная решетка, где 0 - море, 1 - суша.
Движения могут осуществляться в одном из четрыех направлений: вверх, вниз, вправо, влево.
Необходимо посчитать количество анклавов. Анклавом является участок суши, который не прилегает ни к одной из границ заданной площадки.
Пример:
Ввод: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Вывод: 3
Объяснение: на данном поле есть три участка суши, отделенных от границ водой, и один элемент, прилегающий к границе.
Ввод: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Вывод: 0
Решение задачи
👍1