Все записи категории ‘На первой полосе’

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как «Largest Color Value in a Directed Graph».

Суть задачи: дан направленный граф, при этом каждый узел имеет еще один параметр — его в задаче называют цвет. Спектр цветов ограничен, т.к. разные цвета обозначены в задаче разными латинскими буквами, т.е. максимальная палитра составляет всего 26 «цветов».

Требуется найти путь по графу, который собирает максимальное число узлов одного цвета. Дополнительно говорится, что если в графе есть петля, то нужно вернуть -1.

Решаем задачу с литкода о перетасовке строки.

Даны две строки, нужно определить является ли вторая строка результатом перетасовки букв в первой. Правила перетасовки следующие:

Мы произвольно делим строку на две подстроки, которые обозначим SX и SY. Далее мы можем переставить SX и SY местами, а можем не делать этого. Алгоритм может повторяться для SX и SY, до тех пор, пока строку можно еще разделить.

Как говорили учителя в школе — а теперь для самых умных задача со звездочкой. «Longest cycle in a graph» отмечена как сложная задача на leetcode. Давайте разберем как её решить.

Разбираю задачу #200 с литкода, число островов (number of islands).

Задан двумерный массив, в котором участки суши помечены как «1», а участки воды — как «0». Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют единый остров, только если соединяются напрямую по X или по Y (т.е. по диагонали они не соединяются).

Leetcode задача #168. Excel Sheet column title.
Задача помечена как простая, тем не менее, не сразу понял как её решать.

Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, … 26 -> Z, 27 -> AA …