Проверка симметричности дерева

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

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

Пример:

Ввод: 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

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

Треугольник

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

Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на 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.

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

Комбинация сумм 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]
]

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

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

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

Условие задачи:
Строка 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» также будет правильным ответом.

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

Количество анклавов

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

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

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

Расписание курсов

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

Условие задачи: дается количество курсов, сами курсы пронумерованны с нуля. Помимо этого дан массив, в котором хранятся зависимости. Зависимость
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]

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

Записка о выкупе

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

Условие задачи: дано две строки: ransomNote и magazine. Требуется осуществить проверку, может ли строка ransomNote быть получена путем использования букв из строки magazine.

Одна буква из magazine может быть исопльзована единажды в ransomNote.

Пример:

Ввод: ransomNote = "a", magazine = "b"
Вывод: false

Ввод: ransomNote = "aa", magazine = "ab"
Вывод: false

Ввод: ransomNote = "aa", magazine = "aab"
Вывод: true

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

Удаление элементов из связного списка

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

Условие задачи: дан указетель на связный список и целое число (val). Надо извлечь из сипска все узлыва, значение в которых равняется val.

Итогом должен быть возврат на начало изменненного списка (все опреции будут производиться непосредственно с самим списком).

Пример:

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

Ввод: head = [], val = 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]

Решить задачу надо за линейное время.

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

Столкновение астероидов

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

Условие задачи: дан массив астероидов (каждое значение - вес астероида, а знак - направление движения). Каждый из астероидов двигается с одинаковой скоростью.

При столкновени двух астероидов, асторид с меньшим весов уничтожается (у целого астероида вес остается неизменным после столкновения).

Вывести надо результирующий массив после всевозможных столкновений.

Пример:

Ввод: asteroids = [5,10,-5]
Вывод: [5,10]
Объяснение: 3-ий астероид сталкивается со 2-ым и уничтожается.

Ввод: asteroids = [8,-8]
Вывод: [ ]

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

Перенос каждого указателя вправо

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

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

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

Пример:

Ввод: root = [1,2,3,4,5,6,7]
Вывод: [1,#,2,3,#,4,5,6,7,#]

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

Схожие деревья

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

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

Два дерева считаются схожими по последним потомкам в случае если последовательность последних потомков и в первом и во втором деревьях идентична.

Пример:

Ввод: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Вывод: true
Объяснение: *во вложении

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

Сцепка бинарного дерева из центрированного и прямого проходов

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

Условие задачи: даны два списка preorder и inorder, где preorder - центрированный порядок дерева (сenter > left > rigth), inorder - прямой проход (left > center > right). Оба - описывают структуру одного дерева, необходимо сконструировать бинарное дерево.

Пример:

Ввод: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Вывод: [3,9,20,null,null,15,7]

Ввод: preorder = [-1], inorder = [-1]
Вывод: [-1]

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

Гармоничная подпоследовательность наибольшей длины

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

Условие задачи: Мы определяем гармоничный массив как массив, в котором разница между его максимальным значением и минимальным значением равна ровно 1.

Дается целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех его возможных подпоследовательностей.

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

Пример:

Ввод: nums = [1,3,2,2,5,2,3,7]
Вывод: 5
Объяснение: [3,2,2,2,3] - гармоничная подпоследовательность наибольшей длины.

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

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

Заправочная станция

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

Условие задачи: вдоль кольцевого маршрута расположено n заправочных станций, где количество газа на i-й станции равно gas[i].

У вас есть автомобиль с неограниченным запасом бензина, и проезд от i-й станции до следующей (i + 1)-й станции обходится в стоимость [i] бензина. Вы начинаете путешествие с пустым баком на одной из заправочных станций.

Учитывая два целочисленных массива gas и cost, верните индекс начальной заправочной станции, если вы можете объехать круг один раз по часовой стрелке, в противном случае верните -1. Если существует решение, оно гарантированно будет уникальным

Пример:

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

Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1

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

Распределение конфет

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

Условие задачи: у Алисы есть конфеты, где i-я конфета относится к типу Candytype[i]. Алиса заметила, что начала набирать вес, поэтому обратилась к врачу.

Доктор посоветовал Алисе съесть только n / 2 конфет, которые у нее есть (n всегда четное). Алисе очень нравятся ее конфеты, и она хочет съесть максимальное количество различных видов конфет, все еще следуя советам врача.

Учитывая целочисленный массив candyType длины n, верните максимальное количество различных типов конфет, которые она может съесть, если она съест только n / 2 из них.

Пример:

Ввод: candyType = [1,1,2,2,3,3]
Вывод: 3
Объяснение: Алиса может съесть только 6/2 = 3 конфеты. Поскольку существует только 3 вида, она может съесть по одному из каждого вида.

Ввод: piles = [4,3,6,7], k = 3
Вывод: 12

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