Jump Game VI

Задача из серии Jump Game, на динамическое программирование и очереди одновременно. Разберём сначала классическую ошибку — решение через жадный алгоритм, посмотрим почему это не работает, и напишем рабочее решение через дпшечку. Далее оптимизируем с квадрата до линии с помощью очередей.

Word Ladder

Даны два слова, начальное и конечное, а также словарь различных слов. Вернуть длину кратчайшего пути между начальным и конечным словом, если разрешён переход между словами с разницей в один символ. Эта задача, по-моему, классический пример на графы. Слова — вершины, а описанный переход — рёбра.

Sliding Window Maximum

Найти максимумы в скользящем окне. Перейдём от брутфорса к решению с очередью. Вариация этой задачи попалась мне на онсайте в Facebook.

Minimum Number of Removals to Make Mountain Array

Какое минимальное количество элементов нужно удалить из массива, чтобы сделать его Mountain Array? Задача, которая строится на Longest Increasing Subsequence — классическая задача на динамическое программирование.

Move Zeroes

Дан массив целых чисел. Написать функцию, которая поставит все нули в конец массива. Разберём решение за линию и без дополнительной памяти.

Html Entity Parser

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

Number of Dice Rolls With Target Sum

Сколько есть возможных вариантов выкинуть кубики с заданной суммой? Ещё одна задача на динамическое программирование.

Unique Paths

Задача «про робота», в разных вариациях, часто встречается на собеседованиях. Нужно найти количество уникальных путей из одного угла поля в другой. Разберём решение через динамическое программирование.

Container With Most Water

Хороший пример задачи на «жадинку» — жадные алгоритмы. Напишем решение за квадрат, найдём где происходит лишняя работа, и перепишем за линию с помощью жадного алгоритма.

Find Median From Data Stream

Медиана — значение, которое делит набор данных на две половины так, что значения в одной меньше, чем в другой. Есть поток данных из которого мы читаем числа, надо в любой момент найти медиану среди прочитанных чисел. Разберём решение через кучи.