Записи с тегом ‘Разбор задач’

Снова классика задач на перебор вариантов — есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала — не ограничено.

Очередная задача с литкода (№60. Permutation Sequence). В общем случае формулируется так: дан набор элементов, требуется вернуть этот набор после k перестановок.

№560 leetcode Subarray Sum Equals K.

Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k.

Задачу можно сформулировать так: представьте себе участок реки покрытый льдом и в первый день он полностью скован крепким льдом, позволяющим переправится по любому его участку. Разбив участок реки на R x C секторов, мы заявляем, что каждый день очередной сектор из сетки R x C становится не безопасным для пересечения. Нужно определить последний день, когда реку еще можно перейти по крепкому льду.

Да это, кстати, задача #1970 Last Day Where You Can Still Cross с литкода.

Решаем задачу с литкода №1575 Count All Possible Routes.

Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым можно добраться до города-назначения, при заданном запасе топлива.

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

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

Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами — [начало интервала, конец интервала]. Требуется удалить минимальное число элементов, чтобы интервалы не перекрывали друг друга.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так — дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, точка входа — [row, column] — как координаты в лабиринте.

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

Серия задач StoneGame на leetcode — образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого.

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

Следующая задача описывается так — нужно сгенерировать n-разрядный «серый код».

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными.