Архив за Март, 2023

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

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

Мы произвольно делим строку на две подстроки, которые обозначим 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 …

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays).

Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей.

Увидел эту задачу на leetcode — https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS.

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

Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов.