Все записи категории ‘Программирование’

В теории программирования большой класс задач связан с перебором подмножеств, и на 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.