从给定原材料中找到所有可以做出的菜 图解题解

这道题到底在问什么

输入

recipes=[bread], ingredients=[[yeast,flour]], supplies=[yeast,flour,corn]

输出

[bread](原料齐)

输入

bread 又是 sandwich 的原料

输出

[bread,sandwich](连锁推进)

最优解：一步一步想明白

1. 3记住「原料指向菜、need 记缺料数、归零即做出入队」,下面逐帧套它。
2. 4先把初始原料 yeast、flour、meat 标为起点(绿),它们一开始就备齐。接下来逐道菜建图:让每样原料连一条边指向「用到它的菜」,并记下每道菜的 need(需要几样原料)。
3. 5菜「bread」需要 yeast、flour 共 2 样:这几样各连一条边指向 bread,并设 need[bread] = 2(它的入度)。
4. 6菜「sandwich」需要 bread、meat 共 2 样:这几样各连一条边指向 sandwich,并设 need[sandwich] = 2(它的入度)。
5. 7菜「burger」需要 sandwich、meat、bread 共 3 样:这几样各连一条边指向 burger,并设 need[burger] = 3(它的入度)。
6. 8把三样初始原料 yeast、flour、meat 全部入队。右侧面板记着每道菜当前还缺几样:bread 缺 2、sandwich 缺 2、burger 缺 3。开始按队列逐个处理。
7. 9弹出已备齐的「yeast」。看依赖它的菜:bread。逐个把它们的 need 减 1。
8. 10「yeast」是「bread」的原料之一:need[bread] 减 1,现在还缺 1 样,先放着,等其余原料备齐。
9. 11弹出已备齐的「flour」。看依赖它的菜:bread。逐个把它们的 need 减 1。
10. 12「flour」是「bread」的原料之一:need[bread] 减到 0,原料全凑齐!做出「bread」,计入答案并入队(它接下来又能当别人的原料)。
11. 13弹出已备齐的「meat」。看依赖它的菜:sandwich、burger。逐个把它们的 need 减 1。
12. 14「meat」是「sandwich」的原料之一:need[sandwich] 减 1,现在还缺 1 样,先放着,等其余原料备齐。
13. 15「meat」是「burger」的原料之一:need[burger] 减 1,现在还缺 2 样,先放着,等其余原料备齐。
14. 16弹出已备齐的「bread」。看依赖它的菜:sandwich、burger。逐个把它们的 need 减 1。
15. 17「bread」是「sandwich」的原料之一:need[sandwich] 减到 0,原料全凑齐!做出「sandwich」,计入答案并入队(它接下来又能当别人的原料)。
16. 18「bread」是「burger」的原料之一:need[burger] 减 1,现在还缺 1 样,先放着,等其余原料备齐。
17. 19弹出已备齐的「sandwich」。看依赖它的菜:burger。逐个把它们的 need 减 1。
18. 20「sandwich」是「burger」的原料之一:need[burger] 减到 0,原料全凑齐!做出「burger」,计入答案并入队(它接下来又能当别人的原料)。
19. 21弹出已备齐的「burger」。没有哪道菜直接以它为原料(或依赖它的菜已处理),它不再解锁新东西,继续看下一个。
20. 22队列清空。一路连锁:yeast+flour 解锁 bread → bread+meat 解锁 sandwich → sandwich+meat+bread 解锁 burger。答案 = [bread, sandwich, burger],三道菜全部可做。
21. 23回看核心:拓扑排序按「原料就绪顺序」一层层推进,每道菜恰在它最后一样原料备齐的那一刻 need 归零、被做出。没有初始原料能打破的环(循环依赖)永远 need 不归零,自然落选。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict, deque
class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        g = defaultdict(list)
        need = {}
        for recipe, ing in zip(recipes, ingredients):
            need[recipe] = len(ing)
            for item in ing:
                g[item].append(recipe)
        q = deque(supplies)
        ans = []
        while q:
            item = q.popleft()
            for recipe in g[item]:
                need[recipe] -= 1
                if need[recipe] == 0:
                    ans.append(recipe)
                    q.append(recipe)
        return ans

#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string>> g;
        unordered_map<string, int> need;
        for (int i = 0; i < (int)recipes.size(); ++i) {
            need[recipes[i]] = ingredients[i].size();
            for (auto &item : ingredients[i]) g[item].push_back(recipes[i]);
        }
        queue<string> q;
        for (auto &s : supplies) q.push(s);
        vector<string> ans;
        while (!q.empty()) {
            string item = q.front(); q.pop();
            for (auto &recipe : g[item]) if (--need[recipe] == 0) {
                ans.push_back(recipe);
                q.push(recipe);
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> g = new HashMap<>();
        Map<String, Integer> need = new HashMap<>();
        for (int i = 0; i < recipes.length; i++) {
            need.put(recipes[i], ingredients.get(i).size());
            for (String item : ingredients.get(i)) g.computeIfAbsent(item, k -> new ArrayList<>()).add(recipes[i]);
        }
        Queue<String> q = new ArrayDeque<>(Arrays.asList(supplies));
        List<String> ans = new ArrayList<>();
        while (!q.isEmpty()) {
            String item = q.poll();
            for (String recipe : g.getOrDefault(item, Collections.emptyList())) {
                need.put(recipe, need.get(recipe) - 1);
                if (need.get(recipe) == 0) { ans.add(recipe); q.offer(recipe); }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问