Архив за Апрель, 2023

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

Речь идет о № 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.

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

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