Find All Possible Recipes from Given Supplies

Средняя№2115

Даны рецепты, ингредиенты каждого рецепта и припасы, которых сколько угодно. Ингредиент — это либо припас, либо другой рецепт, который нужно приготовить раньше; всё остальное взять негде. Нужно вернуть все рецепты, которые можно приготовить, в любом порядке. Наш пример: dough из flour, water; pasta из dough, eggs; crepe из flour, eggs, milk; cake из crepe, sugar. Припасы: flour, water, eggs, sugar. Ответ — dough и pasta.

2115 Find All Possible Recipes from Given SuppliesРазбор · 1×

Пример: Слева припасы, правее рецепты, стрелка — от ингредиента к рецепту, которому он нужен. Число над рецептом — сколько его ингредиентов ещё не хватает.

flourwatereggsmilksugardoughcrepepastacakeочередьначало слева—готово—
ждёт ингредиентыв очереди: это у нас естьтекущий предметрецепт, куда ведёт стрелкаприготовленне достать никогда

Проводим стрелку от каждого ингредиента к каждому рецепту, которому он нужен

01/37
сначала · назад · пуск · шаг
Скорость
1function findAllRecipes(recipes, ingredients, supplies):
2 neededBy = the recipes that need each ingredient
3 missing = number of ingredients of each recipe
4 queue = supplies
5 made = []
6 while queue is not empty:
7 item = queue.popFront()
8 for recipe in neededBy[item]:
9 decrease missing[recipe] by 1
10 if missing[recipe] is 0:
11 made.pushBack(recipe)
12 queue.pushBack(recipe)
13 return made
состояние
missing
–
queue
–
made
–
item
–
recipe
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У рецепта счётчик дойдёт до 0, только когда каждый его ингредиент выйдет из очереди, а в очередь попадают только припасы и приготовленные рецепты.
  2. Приготовленный рецепт идёт в очередь как припас, поэтому до рецепта, которому он нужен, тоже дойдёт очередь — как до пасты после теста.
  3. Ингредиент, которого нет в припасах и который нельзя приготовить, из очереди не выйдет никогда, поэтому у рецепта с ним — и у всех рецептов после него — счётчик остаётся больше 0. Так же выше 0 остаются рецепты, которые нужны друг другу по кругу.

Сложность

Время O(r + i + s) для r рецептов, i ингредиентов во всех списках и s припасов: каждая запись в списках становится одной стрелкой, по ней проходим один раз, и каждый предмет попадает в очередь не больше одного раза. Память O(r + i + s) на стрелки, счётчики и очередь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.