Поиск первого вхождения
Сложность: Средняя
Условие задачи: дается две строки needle и haystack, верните индекс первого появления иглы в стоге сена или -1, если игла не является частью стога сена.
Пример:
Ввод: haystack = "sadbutsad", needle = "sad"
Вывод: 0
Ввод: haystack = "leetcode", needle = "leeto"
Вывод: -1
Решение задачи
Сложность: Средняя
Условие задачи: дается две строки needle и haystack, верните индекс первого появления иглы в стоге сена или -1, если игла не является частью стога сена.
Пример:
Ввод: haystack = "sadbutsad", needle = "sad"
Вывод: 0
Ввод: haystack = "leetcode", needle = "leeto"
Вывод: -1
Решение задачи
👍6👎4
Отсутствующее число
Сложность: Лёгкая
Условие задачи: дан массив arr из натуральных чисел, отсортированных в строго возрастающем порядке, и целое число k.
Возвращает k-е положительное целое число, отсутствующее в этом массиве.
Пример:
Ввод: arr = [2,3,4,7,11], k = 5
Вывод: 9
Ввод: arr = [1,2,3,4], k = 2
Вывод: 6
Решение задачи
Сложность: Лёгкая
Условие задачи: дан массив arr из натуральных чисел, отсортированных в строго возрастающем порядке, и целое число k.
Возвращает k-е положительное целое число, отсутствующее в этом массиве.
Пример:
Ввод: arr = [2,3,4,7,11], k = 5
Вывод: 9
Ввод: arr = [1,2,3,4], k = 2
Вывод: 6
Решение задачи
👍7🎉1
Игра в прыжки IV
Сложность: Тяжёлая
Условие задачи: дается массив целых чисел arr, вы изначально располагаетесь по первому индексу массива.
За один шаг вы можете перейти от индекса i к индексу:
i + 1, где: i + 1 < длина обр.
i - 1, где: i - 1 >= 0.
j где: arr[i] == arr[j] и i != просто.
Возвращает минимальное количество шагов для достижения последнего индекса массива.
Обратите внимание, что вы не можете в любой момент выйти за пределы массива.
Пример:
Ввод: arr = [100,-23,-23,404,100,23,23,23,3,404]
Вывод: 3
Ввод: arr = [7]
Вывод: 0
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается массив целых чисел arr, вы изначально располагаетесь по первому индексу массива.
За один шаг вы можете перейти от индекса i к индексу:
i + 1, где: i + 1 < длина обр.
i - 1, где: i - 1 >= 0.
j где: arr[i] == arr[j] и i != просто.
Возвращает минимальное количество шагов для достижения последнего индекса массива.
Обратите внимание, что вы не можете в любой момент выйти за пределы массива.
Пример:
Ввод: arr = [100,-23,-23,404,100,23,23,23,3,404]
Вывод: 3
Ввод: arr = [7]
Вывод: 0
Решение задачи
👍6❤1👎1
Минимальное количество времени для путешествий
Сложность: Средняя
Условие задачи: дается массив time, где time[i] обозначает время, затраченное i-м автобусом на выполнение одной поездки.
Каждый автобус может совершать несколько поездок подряд; то есть следующая поездка может начаться сразу после завершения текущей поездки. Кроме того, каждый автобус работает независимо; то есть поездки одного автобуса не влияют на поездки любого другого предприятия.
Вам также дается целое число общих поездок, которое обозначает количество поездок, которые все автобусы должны совершить в общей сложности. Возвращает минимальное время, необходимое всем автобусам для завершения как минимум общего количества поездок.
Пример:
Ввод: time = [1,2,3], totalTrips = 5
Вывод: 3
Ввод: time = [2], totalTrips = 1
Вывод: 2
Решение задачи
Сложность: Средняя
Условие задачи: дается массив time, где time[i] обозначает время, затраченное i-м автобусом на выполнение одной поездки.
Каждый автобус может совершать несколько поездок подряд; то есть следующая поездка может начаться сразу после завершения текущей поездки. Кроме того, каждый автобус работает независимо; то есть поездки одного автобуса не влияют на поездки любого другого предприятия.
Вам также дается целое число общих поездок, которое обозначает количество поездок, которые все автобусы должны совершить в общей сложности. Возвращает минимальное время, необходимое всем автобусам для завершения как минимум общего количества поездок.
Пример:
Ввод: time = [1,2,3], totalTrips = 5
Вывод: 3
Ввод: time = [2], totalTrips = 1
Вывод: 2
Решение задачи
Подмассив с фиксированными границами
Сложность: Тяжёлая
Условие задачи: дается целочисленный массив nums и два целых числа minK и maxK.
Подмассив nums с фиксированной привязкой - это подмассив, который удовлетворяет следующим условиям:
Минимальное значение в подмассиве равно minK.
Максимальное значение в подмассиве равно max.
Возвращает количество подмассивов с фиксированной привязкой.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Вывод: 2
Ввод: nums = [1,1,1,1], minK = 1, maxK = 1
Вывод: 10
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается целочисленный массив nums и два целых числа minK и maxK.
Подмассив nums с фиксированной привязкой - это подмассив, который удовлетворяет следующим условиям:
Минимальное значение в подмассиве равно minK.
Максимальное значение в подмассиве равно max.
Возвращает количество подмассивов с фиксированной привязкой.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Вывод: 2
Ввод: nums = [1,1,1,1], minK = 1, maxK = 1
Вывод: 10
Решение задачи
👍5
Случайный узел списка
Сложность: Средняя
Условие задачи: дается односвязный список, верните значение случайного узла из связанного списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс решения:
Инициализируется объект с помощью заголовка односвязного списка head.
int getRandom() случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью.
Пример:
Ввод: ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Вывод: [null, 1, 3, 2, 2, 3]
Решение задачи
Сложность: Средняя
Условие задачи: дается односвязный список, верните значение случайного узла из связанного списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс решения:
Инициализируется объект с помощью заголовка односвязного списка head.
int getRandom() случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью.
Пример:
Ввод: ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Вывод: [null, 1, 3, 2, 2, 3]
Решение задачи
👍6
Соединение связных списков
Сложность: Тяжёлая
Условие задачи: дается массив из k списков связанных списков, каждый связанный список сортируется в порядке возрастания.
Объедините все связанные списки в один отсортированный связанный список и верните его.
Пример:
Ввод: lists = [[1,4,5],[1,3,4],[2,6]]
Вывод: [1,1,2,3,4,4,5,6]
Ввод: lists = []
Вывод: []
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается массив из k списков связанных списков, каждый связанный список сортируется в порядке возрастания.
Объедините все связанные списки в один отсортированный связанный список и верните его.
Пример:
Ввод: lists = [[1,4,5],[1,3,4],[2,6]]
Вывод: [1,1,2,3,4,4,5,6]
Ввод: lists = []
Вывод: []
Решение задачи
👍9❤2
Скобочная пунктуация
Сложность: Лёгкая
Условие задачи: дана строка, содержащая в себе только символы:
Пример:
Ввод:
Ввод:
Ввод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дана строка, содержащая в себе только символы:
'(', ')', '{', '}', '[', ']'. Надо выполнить проверку на то, корректно ли открыты и закрыты все скобки. Пример:
Ввод:
s = "()"
Вывод: TrueВвод:
s = "()[]{}"
Вывод: TrueВвод:
s = "(]"
Вывод: FalseРешение задачи
❤6
От предка до потомка
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, содержащего только цифры от 0 до 9.
Каждый путь от корня к листу в дереве представляет собой число.
Например, путь от корня к листу 1 -> 2 -> 3 представляет число 123.
Возвращает общую сумму всех чисел от корня до конца. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-разрядное целое число.
Конечный узел - это узел без дочерних элементов.
Пример:
Ввод: root = [1,2,3]
Вывод: 25
Ввод: root = [4,9,0,5,1]
Вывод: 1026
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, содержащего только цифры от 0 до 9.
Каждый путь от корня к листу в дереве представляет собой число.
Например, путь от корня к листу 1 -> 2 -> 3 представляет число 123.
Возвращает общую сумму всех чисел от корня до конца. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-разрядное целое число.
Конечный узел - это узел без дочерних элементов.
Пример:
Ввод: root = [1,2,3]
Вывод: 25
Ввод: root = [4,9,0,5,1]
Вывод: 1026
Решение задачи
👍3
Симметрия в дереве
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, проверьте, является ли оно зеркалом самого себя (т.е. симметричным вокруг своего центра).
Пример:
Ввод: root = [1,2,2,null,3,null,3]
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, проверьте, является ли оно зеркалом самого себя (т.е. симметричным вокруг своего центра).
Пример:
Ввод: root = [1,2,2,null,3,null,3]
Вывод: false
Решение задачи
👍3
Проверка полноты бинарного дерева
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
👍8
Количество изолированных островов
Сложность: Средняя
Условие задачи: дан двумерный массив, содержащий 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
Решение задачи
👍5
Замена элемента на правый максимум
Сложность: Лёгкая
Условие задачи: дан массив, необходимо заменить каждый элемент на максимальный из тех, что находятся справа. В случае отсутствия такого элемента, используется -1.
Пример:
Ввод: arr = [17,18,5,4,6,1]
Вывод: [18,6,6,6,1,-1]
Решение задачи
Сложность: Лёгкая
Условие задачи: дан массив, необходимо заменить каждый элемент на максимальный из тех, что находятся справа. В случае отсутствия такого элемента, используется -1.
Пример:
Ввод: arr = [17,18,5,4,6,1]
Вывод: [18,6,6,6,1,-1]
Решение задачи
👍5🤔1
Заливка
Сложность: Лёгкая
Условие задачи: дается изображение, которое представлено двумерной матрицей, где каждая ячейка означает значение пикселя.
Также даются три числа sr, sc, color. Надо осуществить заливку, начиная с image[sr][sc].
Заливка осуществляется в четырех направлениях от текущей ячейки, при этом изменяются только ячейки, которые имеют идентичное значение пикселя с базовой ячейкой.
Пример:
Ввод: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Вывод: [[2,2,2],[2,2,0],[2,0,1]]
Решение задачи
Сложность: Лёгкая
Условие задачи: дается изображение, которое представлено двумерной матрицей, где каждая ячейка означает значение пикселя.
Также даются три числа sr, sc, color. Надо осуществить заливку, начиная с image[sr][sc].
Заливка осуществляется в четырех направлениях от текущей ячейки, при этом изменяются только ячейки, которые имеют идентичное значение пикселя с базовой ячейкой.
Пример:
Ввод: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Вывод: [[2,2,2],[2,2,0],[2,0,1]]
Решение задачи
👍4
Конвертация отсортированного массива в бинарное дерево поиска
Сложность: Лёгкая
Условие задачи: дан целочисленный массив, упорядоченный по возрастанию. Необходимо конвертировать его в сбалансированное по высоте дерево (бинарное).
Сбалансированное по высоте бинарное дерево - это бинарное дерево, глубина между потомками которого на каждом узле отличается не более чем на единицу.
Пример:
Ввод: nums = [-10,-3,0,5,9]
Вывод: [0,-3,9,-10,null,5]
Объяснение: [0,-10,5,null,-3,null,9] также является ответом
Ввод: nums = [1,3]
Вывод: [3,1]
Объяснение: [1,null,3] также является ответом
Решение задачи
Сложность: Лёгкая
Условие задачи: дан целочисленный массив, упорядоченный по возрастанию. Необходимо конвертировать его в сбалансированное по высоте дерево (бинарное).
Сбалансированное по высоте бинарное дерево - это бинарное дерево, глубина между потомками которого на каждом узле отличается не более чем на единицу.
Пример:
Ввод: nums = [-10,-3,0,5,9]
Вывод: [0,-3,9,-10,null,5]
Объяснение: [0,-10,5,null,-3,null,9] также является ответом
Ввод: nums = [1,3]
Вывод: [3,1]
Объяснение: [1,null,3] также является ответом
Решение задачи
👍2
Игра в угадайку
Сложность: Лёгкая
Условие задачи: играем в угадайку по следующей схеме:
Выбирается число от 1 до n. Надо отгадать загаданное число. После каждой неудачной попытки говорится больше или меньше заданное число.
Надо реализовать API:
-1: загаданное число больше выбранного;
1: загаданное число меньше выбранного;
0: загаданное число и выбранное совпали.
Необходимо вернуть загаданное число.
Пример:
Ввод: n = 10, pick = 6
Вывод: 6
Решение задачи
Сложность: Лёгкая
Условие задачи: играем в угадайку по следующей схеме:
Выбирается число от 1 до n. Надо отгадать загаданное число. После каждой неудачной попытки говорится больше или меньше заданное число.
Надо реализовать API:
-1: загаданное число больше выбранного;
1: загаданное число меньше выбранного;
0: загаданное число и выбранное совпали.
Необходимо вернуть загаданное число.
Пример:
Ввод: n = 10, pick = 6
Вывод: 6
Решение задачи
👍5
Поиск в двумерной матрице II
Сложность: Средняя
Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:
- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).
Пример:
Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true
Решение задачи
Сложность: Средняя
Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:
- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).
Пример:
Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true
Решение задачи
👍6
Перенос указателя вправо
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо перенести каждый указатель на следующий узел на соответствующий правый правый элемент на текущем уровне либо же передать указатель на NULL в случае отсутствия узла.
Пример:
Ввод:
Вывод:
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо перенести каждый указатель на следующий узел на соответствующий правый правый элемент на текущем уровне либо же передать указатель на NULL в случае отсутствия узла.
Пример:
Ввод:
root = [1,2,3,4,5,null,7]Вывод:
[1,#,2,3,#,4,5,7,#]
Решение задачи👍1
Идеальные квадраты
Сложность: Средняя
Условие задачи: дается целое число, необходимо вернуть минимальное количество чисел, из которых извлекается квадратный корень, дающих в сумме целевое число.
Пример:
Ввод: n = 12
Вывод: 3
Объяснение: 12 = 4 + 4 + 4.
Ввод: n = 13
Вывод: 2
Решение задачи
Сложность: Средняя
Условие задачи: дается целое число, необходимо вернуть минимальное количество чисел, из которых извлекается квадратный корень, дающих в сумме целевое число.
Пример:
Ввод: n = 12
Вывод: 3
Объяснение: 12 = 4 + 4 + 4.
Ввод: n = 13
Вывод: 2
Решение задачи
❤2👍1