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

Речь идет о № 839 с leetcode.

Формулируется проблема таким образом — дан массив строк, которые отличаются (или не отличаются) друг от друга перестановкой букв. Подобными считаются 2 строки, отличающиеся друг от друга только одной перестановкой или равные друг другу.

При этом если строка 1 подобна строке 2, а строка 2 подобна строке 3, то все три должны попасть в одну группу подобия. Хотя строка 1 может не быть подобна строке 3.

Результатом является кол-во групп подобия.

В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример — 78 Subsets и 90 Subsets II.

Формулировка следующая — есть набор (множество) чисел, нужно составить все возможные подмножества, включая и пустое. Разница между двумя задачами лишь в том, что в первой (№78) задаче элементы множества уникальные, а во второй (№90) — нет. Но в обоих случаях требуется составить уникальные подмоножества.

Разбираем задачу № 1639 Number of Ways to Form a Target String Given a Dictionary c leetcode.com. Дан словарь, где слова имеют одинаковую длину — words. Также дано дополнительно слово — target, которое нужно составить из словарных слов по следующим правилам:

Вы можете брать буквы из любого слова words и составлять target, буква за буквой, но если вы взяли букву с позиции j в некотором слове, то следующую букву можно брать только с позиции не меньше чем j + 1.

Требуется вернуть кол-во путей (вариантов), какими возможно составить target.

Решаем задачу № 2218 с leetcode — Maximum Value of K Coins From Piles.

В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да — суть именно такая. У нас есть стопки монет, и дано число операций, за каждую из которых, мы можем взять монету из произвольной кучи.

Нужно вернуть максимальную сумму, которую возможно набрать при таких условиях.

Сегодня расскажу о решении задачи №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 …

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

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