Заливка
Сложность: Лёгкая
Условие задачи: дается изображение, которое представлено двумерной матрицей, где каждая ячейка означает значение пикселя.
Также даются три числа 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
Путь минимальной суммы
Сложность: Средняя
Условие задачи: дается двумерная матрица, заполненная неотрицательными числами. Необходимо найти путь из левого верхнего угла в правый нижний, который имеет наименьшую сумму.
Двигаться можно лишь вправо и вниз.
Пример:
Ввод: grid = [[1,3,1],[1,5,1],[4,2,1]]
Вывод: 7
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается двумерная матрица, заполненная неотрицательными числами. Необходимо найти путь из левого верхнего угла в правый нижний, который имеет наименьшую сумму.
Двигаться можно лишь вправо и вниз.
Пример:
Ввод: grid = [[1,3,1],[1,5,1],[4,2,1]]
Вывод: 7
Объяснение: *во вложении
Решение задачи
👍4
Сводные диапазоны
Сложность: Лёгкая
Условие задачи: дается массив из уникальных целых чисел цисел. Срез [a,b] - включает в себя множество значений из данного отрезка включительно.
Необходимо верноть наименьший отсортированный список диапазонов, покрывающих все в массиве. Это означает, что каждый элемент из исходного массива должен быть включен только в единственный диапазон, и нет такого элемнта из исходного массива, что этот элемент будет в одном из диапазонов, но будет остутствовать в исходном массиве.
• "a->b" if a != b
• "a" if a == b
Пример:
Ввод: nums = [0,1,2,4,5,7]
Вывод: ["0->2","4->5","7"]
Объяснение:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Ввод: nums = [0,2,3,4,6,8,9]
Вывод: ["0","2->4","6","8->9"]
Решение задачи
Сложность: Лёгкая
Условие задачи: дается массив из уникальных целых чисел цисел. Срез [a,b] - включает в себя множество значений из данного отрезка включительно.
Необходимо верноть наименьший отсортированный список диапазонов, покрывающих все в массиве. Это означает, что каждый элемент из исходного массива должен быть включен только в единственный диапазон, и нет такого элемнта из исходного массива, что этот элемент будет в одном из диапазонов, но будет остутствовать в исходном массиве.
• "a->b" if a != b
• "a" if a == b
Пример:
Ввод: nums = [0,1,2,4,5,7]
Вывод: ["0->2","4->5","7"]
Объяснение:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Ввод: nums = [0,2,3,4,6,8,9]
Вывод: ["0","2->4","6","8->9"]
Решение задачи
👍4
Змейка из машин
Сложность: Средняя
Условие задачи: есть n машин, направляющихся в одно и то же место на расстоянии target по однополосной дороге.
Дается два целочисленных массива длины n, в первом хранится положение, а во втором скорость соответствующей машины.
Машины не могут обгонять друг друга, и в случае если быстрая машина догнала медленную, то движение она у же продолжает со скоростью медленной машины.
Змейка из машин - группа нескольких или одной машины, достигающих одновременно целевого пункта (расстояние между машинами в одной змейке не учитывается).
Необходимо вычислить количество таких змеек.
Пример:
Ввод: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Вывод: 3
Объяснение:
Ввод: target = 10, position = [3], speed = [3]
Вывод: 1
Решение задачи
Сложность: Средняя
Условие задачи: есть n машин, направляющихся в одно и то же место на расстоянии target по однополосной дороге.
Дается два целочисленных массива длины n, в первом хранится положение, а во втором скорость соответствующей машины.
Машины не могут обгонять друг друга, и в случае если быстрая машина догнала медленную, то движение она у же продолжает со скоростью медленной машины.
Змейка из машин - группа нескольких или одной машины, достигающих одновременно целевого пункта (расстояние между машинами в одной змейке не учитывается).
Необходимо вычислить количество таких змеек.
Пример:
Ввод: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Вывод: 3
Объяснение:
Ввод: target = 10, position = [3], speed = [3]
Вывод: 1
Решение задачи
👍7
Римские цифры
Сложность: Лёгкая
Условие задачи: существует алфавит римских цифр, на вход подается число, записанное римскими цифрами, необходимо конвертировать данное число в арабскую запись.
Пример:
Ввод: s = "III"
Вывод: 3
Ввод: s = "LVIII"
Вывод: 58
Решение задачи
Сложность: Лёгкая
Условие задачи: существует алфавит римских цифр, на вход подается число, записанное римскими цифрами, необходимо конвертировать данное число в арабскую запись.
Пример:
Ввод: s = "III"
Вывод: 3
Ввод: s = "LVIII"
Вывод: 58
Решение задачи
👍6
Минимальная глубина бинарного дерева
Сложность: Лёгкая
Условие задачи: дано бинарное дерево. Необходимо найти минимальную глубину дерева.
Глубина дерева - количество узлов от корня до ближайшего потомка.
Пример:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: 2
Ввод: root = [2,null,3,null,4,null,5,null,6]
Вывод: 5
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево. Необходимо найти минимальную глубину дерева.
Глубина дерева - количество узлов от корня до ближайшего потомка.
Пример:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: 2
Ввод: root = [2,null,3,null,4,null,5,null,6]
Вывод: 5
Решение задачи
👍2❤1
Максимальное количество единиц
Сложность: Лёгкая
Условие задачи: дается бинарный массив (состоит только из 0 и 1). Необходимо вычислить максимальную длину подмассива, в котором присутствуют только 1.
Пример:
Ввод: nums = [1,1,0,1,1,1]
Вывод: 3
Решение задачи
Сложность: Лёгкая
Условие задачи: дается бинарный массив (состоит только из 0 и 1). Необходимо вычислить максимальную длину подмассива, в котором присутствуют только 1.
Пример:
Ввод: nums = [1,1,0,1,1,1]
Вывод: 3
Решение задачи
👍4🔥2❤1
Пути в бинарном дереве
Сложность: Лёгкая
Условие задачи: дается корень бинарного дерева, необходимо вывести все пути от корня до последнего потомка в каждом из ветвлений.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дается корень бинарного дерева, необходимо вывести все пути от корня до последнего потомка в каждом из ветвлений.
Пример:
Ввод:
root = [1,2,3,null,5]Вывод:
["1->2->5","1->3"]Ввод:
root = [1]Вывод:
["1"]Решение задачи
Сумма минимумов подмассивов
Сложность: Средняя
Условие задачи: дается массив целых чисел, необходимо посчитать сумму минимумов подмассивов, ответ может быть большим, необходимо посчитать результат по модулю 10^9 + 7.
Пример:
Ввод: arr = [3,1,2,4]
Вывод: 17
Объяснение:
Подмассивы: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], минимумы этих подмассивов: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, которые в сумме дают 17.
Решение задачи
Сложность: Средняя
Условие задачи: дается массив целых чисел, необходимо посчитать сумму минимумов подмассивов, ответ может быть большим, необходимо посчитать результат по модулю 10^9 + 7.
Пример:
Ввод: arr = [3,1,2,4]
Вывод: 17
Объяснение:
Подмассивы: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], минимумы этих подмассивов: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, которые в сумме дают 17.
Решение задачи
👍6
Поиск слова
Сложность: Средняя
Условие задачи: дается двумерная матрица, отражающая структуру поля, а также искомое слово. Необходимо осуществить проверку наличия слова в матрице символов.
Слово можно составлять из соседей справа, слева, сверху или снизу.
Пример:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается двумерная матрица, отражающая структуру поля, а также искомое слово. Необходимо осуществить проверку наличия слова в матрице символов.
Слово можно составлять из соседей справа, слева, сверху или снизу.
Пример:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Объяснение: *во вложении
Решение задачи
👍5❤1
Шаблон слова
Сложность: Лёгкая
Условие задачи: дается шаблон и строка, необходимо проверить соответствует ли строка шаблону.
Под соответствием имеется биекция двух строковых наборов, которая в результате дает непустое слово.
Пример:
Ввод: pattern = "abba", s = "dog cat cat dog"
Вывод: true
Ввод: pattern = "abba", s = "dog cat cat fish"
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: дается шаблон и строка, необходимо проверить соответствует ли строка шаблону.
Под соответствием имеется биекция двух строковых наборов, которая в результате дает непустое слово.
Пример:
Ввод: pattern = "abba", s = "dog cat cat dog"
Вывод: true
Ввод: pattern = "abba", s = "dog cat cat fish"
Вывод: false
Решение задачи
👍4
Подсчет подостровов
Сложность: Средняя
Условие задачи: дается два двумерных массива, содержащих нули (означают воду) и единицы (суша). Остров - совокупность единиц, соединенных между собой в четырех направлениях (по горизонтали или вертикали).
Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.
Необходимо вычислить количество подостровов на втором поле.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается два двумерных массива, содержащих нули (означают воду) и единицы (суша). Остров - совокупность единиц, соединенных между собой в четырех направлениях (по горизонтали или вертикали).
Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.
Необходимо вычислить количество подостровов на втором поле.
Пример:
Ввод:
grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]Вывод:
3Объяснение:
Ввод:
grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]Вывод:
2 Решение задачи
👍1
Избыточность соединения
Сложность: Средняя
Условие задачи: дается ненправленный граф, не имеющий циклов.
Узлы графа соединены между собой и отражаются списком соединения
В графе имеется избытоное ребро, которое может быть безболезнено извлечено из списка связности.
Необходимо вывести ребро, которое можно удалить без потери информации.
Пример:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается ненправленный граф, не имеющий циклов.
Узлы графа соединены между собой и отражаются списком соединения
edges[i] = [ai, bi]. В графе имеется избытоное ребро, которое может быть безболезнено извлечено из списка связности.
Необходимо вывести ребро, которое можно удалить без потери информации.
Пример:
Ввод:
edges = [[1,2],[1,3],[2,3]]Вывод:
[2,3]Решение задачи
👍2
Подмассив с наибольшим произведением
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
👍2
Последний из камней
Сложность: Лёгкая
Условие задачи: на вход подается массив из камней, где i-ый элемент обозначает вес соответствующего камня.
Осуществляется игра в камни: берутся два камня с наибольшим весом и сталкиваются. Результат их столкновения может быть следующим:
- оба уничтожаются при условии одинакового веса;
- при условии неравенства весов из веса большего вычитается меньший вес, а после снова добавляется в массив.
Игра продолжается до тех пор пока есть хотя бы один камень, необходимо вернуть это самый последний вес. При отсутствии камней в конце - вернуть ноль.
Пример:
Ввод: stones = [2,7,4,1,8,1]
Вывод: 1
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подается массив из камней, где i-ый элемент обозначает вес соответствующего камня.
Осуществляется игра в камни: берутся два камня с наибольшим весом и сталкиваются. Результат их столкновения может быть следующим:
- оба уничтожаются при условии одинакового веса;
- при условии неравенства весов из веса большего вычитается меньший вес, а после снова добавляется в массив.
Игра продолжается до тех пор пока есть хотя бы один камень, необходимо вернуть это самый последний вес. При отсутствии камней в конце - вернуть ноль.
Пример:
Ввод: stones = [2,7,4,1,8,1]
Вывод: 1
Решение задачи
👍6