5947. 从给定原材料中找到所有可以做出的菜

5947. 从给定原材料中找到所有可以做出的菜

目录

1. 题意

给定 一维数组 recipes 表示菜谱,二维数组 ingredients 每道菜的原材料, 一维数组 supplies 提供的材料,找出能做出的所有菜。

输入:recipes = [“bread”], ingredients = [[“yeast”,“flour”]], supplies = [“yeast”,“flour”,“corn”]
输出:[“bread”]
解释:我们可以做出 “bread” ,因为我们有原材料 “yeast” 和 “flour” 。


2. 算法

哈希表 + 拓扑排序

3. 思路

  1. 建图。用hash存储,对于给定的菜谱,我们可以建边,从这道菜的原材料向这道菜连边,而菜谱入度++。
  2. topsort。 先将已有的原材料入队。在图中跑一遍拓排,原材料连向的点入度- -,那么,对于每道菜,如果入度为 0 则表明可以做成,并且当作已有原材料入队,入答案数组。
  3. 具体细节,见代码注释~~

代码

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        int n = recipes.size();
        unordered_map<string, vector<string>> mp; // 图
        unordered_map<string, int> d;  // 入度
        for (int i = 0; i < n; i++) {
            for (auto &x: ingredients[i]) {
                // 原材料能提供的菜
                mp[x].push_back(recipes[i]);
            }
            // 菜入度 = 其原材料个数
            d[recipes[i]] = ingredients[i].size();
        }

        vector<string> ans; // 答案数组
        queue<string> q; // 队列
        // 初始材料入队
        for (auto &x : supplies) {
            q.push(x);
        }

        // topsort
        while(!q.empty()) {
            auto x = q.front();
            q.pop();
            if(mp.count(x)) {
                for (auto &y : mp[x]) {
                    // 入度为0, 说明能做出这道菜
                    if(--d[y] == 0) {
                        ans.push_back(y);
                        q.push(y);
                    }
                }
            }
        }
        return ans;

    }
};
上一篇:tmux 学习


下一篇:不知道的地方(2)