​Валидный судоку

Сложность: средняя

Условие:
Определите, валидна ли доска судоку 9 x 9. Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:
1. Каждая строка должна содержать цифры 1–9 без повторения.
2. Каждый столбец должен содержать цифры 1–9 без повторения.
3. Каждый из девяти подблоков сетки 3 x 3 должен содержать цифры 1–9 без повторения.

Доска судоку (частично заполненная) может быть валидной, но не обязательно решаемой. Только заполненные ячейки должны быть проверены в соответствии с указанными правилами.

Примеры:
Пример 1 (на картинке):
Ввод: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Вывод: true

Пример 2:
Ввод: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Вывод: false
Объяснение: то же, что и в примере 1, за исключением того, что цифра 5 в верхнем левом углу изменена на 8. Поскольку в верхнем левом подблоке 3x3 есть две восьмерки, это неверно.

Решение задачи

Перевернуть порядок следования элементов связного списка

Сложность: Лёгкая

Условие задачи: дан указатель на начало связного списка, надо вернуть его элементы в обратном порядке.

Пример:

Ввод: head = [1,2,3,4,5]
Вывод: [5,4,3,2,1]

Решение задачи

Умножение строк

Сложность задачи: Средняя

Условие задачи:
Даны два неотрицательных целых числа num1 и num2, представленные в виде строк, вернуть произведение num1 и num2, также представленное в виде строки.

Примечание. Вы не должны использовать какую-либо встроенную библиотеку BigInteger или напрямую преобразовывать входные данные в целое число.

Пример:
Ввод: num1 = "2", num2 = "3"
Вывод: "6"

Ввод: num1 = "123", num2 = "456"
Вывод: "56088"

Решение задачи

Определение количества островов

Сложность: Средняя

Условие задачи: дан двумерный массив размера 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

Решение задачи

Создание скобок

Для заданных n пар скобок напишите функцию, генерирующую все комбинации правильных пар скобок.

Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]

Ввод: n = 1
Вывод: ["()"]

Решение задачи

Мокрые бандиты

Сложность: Средняя

Условие задачи: Мы - профессиональные грабители, обчищающие дома под Рождество и в каждом ограбленном нами доме оставляем характерный символ: невыключенный кран с водой.

Перед нами стоит задача: ограбить на максимальную сумму дома, находящиеся на проспекте Линкольна, но у данных домов есть характерная черта: при ограбление соседних домов срабатывает сигнализация, вызывающая полицию.

Нам необходимо выяснить какие дома надо ограбить, чтобы получить максимальный куш.

Пример:

Ввод: nums = [1,2,3,1]
Вывод: 4

Объяснение: Грабим 1-ый дом (money = 1), а после навещаем 3-ий дом (money = 3).
Суммарный куш: 1 + 3 = 4.

Решение задачи

Строки отличающиеся на один символ

Сложность задачи: Средняя

Условие задачи:
Дан список строк dict, где все строки имеют одинаковую длину.

Верните true, если в одном и том же индексе есть 2 строки, которые отличаются только на 1 символ, в противном случае возвращает false.

Пример:
Ввод: dict = ["abcd","acbd", "aacd"]
Вывод: true
Объяснение: Строки "abcd" и "aacd" отличаются только одним символом в индексе 1.

Ввод: dict = ["ab","cd","yz"]
Вывод: false

Решение задачи

Проверка бинарного дерева

Сложность: Средняя

Условие задачи: требуется проверить является ли исходное дерево бинарным деревом поиска.

Правильное бинарное дерево удовлетворяет следующим условиям:
- элементы левого поддеревоа должно быть меньше родителя.
- элементы правого поддерева должны быть больше, чем значение в родительском узле.
- левое и правое поддеревья должны быть также бинарными деревьями поиска.

Пример:

Ввод: root = [5,1,4,null,null,3,6]
Вывод: False
Объяснение: 4 < 5, но при этом находится в правом поддереве.

Ввод: root = [2,1,3]
Вывод: True

Решение задачи

Самая длинная подстрока без повторений

Сложность: Средняя.

Условие задачи: дана строка надо найти самую длинную подстроку, в которой не будет повторений.

Пример:

Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: ответом является подстрока "abc", длина которой равна 3.

Ввод: s = "bbbbb"
Вывод: 1

Ввод: s = "pwwkew"
Вывод: 3
Объяснение: ответ - "wke" (длина = 3).

Решение задачи

Объединить два отсортированных списка

Вам даны 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]

Решение задачи

То же дерево

Сложность задачи:
Низкая

Условие:
Получив корни двух бинарных деревьев 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 = [[0,30],[5,10],[15,20]]
Вывод: 2

Ввод: intervals = [[7,10],[2,4]]
Вывод: 1

Решение задачи

Комбинации

Сложность: Средняя

Условие задачи: даны два целых положительных числа 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]]

Решение задачи

Далеко на сколько это возможно

Сложность: Средняя

Условие задачи: дан двумерный массив, где 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

Решение задачи

Изъятие дубликатов из односвязного списка

Сложность: Лёгкая

Условие задачи: дан отсортированный по значениям односвязный список. Нужно удалить из него все дублирующиеся элементы и вернуть также остортриованный список.

Пример:

Ввод: head = [1,1,2]
Вывод: [1,2]

Ввод: head = [1,1,2,3,3]
Вывод: [1,2,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

Решение задачи

Реализация класса MinStack

Сложность: Средняя

Условиеи задачи: разработай пользовательский класс 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

Решение задачи

Матрица Топлица

Сложность: Лёгкая Средняя Тяжёлая

Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.

Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.

Пример:

Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true

Решение задачи

Перелет с наименьшей ценой

Сложность: Средняя

Условие задачи: есть 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

Решение задачи