题目
你有 n
道不同菜的信息。给你一个字符串数组recipes
和一个二维字符串数组ingredients
。第 i
道菜的名字为 recipes[i]
,如果你有它 所有 的原材料 ingredients[i]
,那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜,也就是说 ingredients[i]
可能包含 recipes
中另一个字符串。
同时给你一个字符串数组 supplies
,它包含你初始时拥有的所有原材料,每一种原材料你都有无限多。
请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
注意两道菜在它们的原材料中可能互相包含。
示例 1:
输入:recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"] 输出:["bread"] 解释: 我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。
示例 2:
输入:recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] 输出:["bread","sandwich"] 解释: 我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。 我们可以做出 "sandwich" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
示例 3:
输入:recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] 输出:["bread","sandwich","burger"] 解释: 我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。 我们可以做出 "sandwich" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 。 我们可以做出 "burger" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。
示例 4:
输入:recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"] 输出:[] 解释: 我们没法做出任何菜,因为我们只有原材料 "yeast" 。
解题
方法一:暴力模拟
以现有的原料制作,把新做出来的菜,也添加到原料中,反复循环直到没有新的菜增加,就返回结果
class Solution { public: vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) { vector<string> res; unordered_set<string> set; for(string& s:supplies){//记录现有的原材料 set.insert(s); } int preLen;//当前所有原材料的长度 while(true){ int preLen=set.size(); for(int i=0;i<recipes.size();i++){ if(set.count(recipes[i])) continue; vector<string> tmp=ingredients[i]; bool ok=true;//如果为true说明可以做这道菜 for(int j=0;j<tmp.size();j++){ if(!set.count(tmp[j])){ ok=false; break; } } if(ok){//如果本这次菜品可以做 set.insert(recipes[i]);//本次菜品添加为原材料 res.push_back(recipes[i]);//保存结果 } } if(set.size()<=preLen) break;//如果原材料不再增加了,说明剩下的菜品都没法制作了 } return res; } };
方法二:拓扑排序
从原材料出发,当菜品对应的入度为0的时候,说明原材料齐全,把菜品再加入到原材料中。
得到入度为0的点,就是可以做的菜品。
class Solution { public: vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) { unordered_map<string,vector<string>> graph; unordered_map<string,int> indeg; int n=recipes.size(); for(int i=0;i<n;i++){ for(int j=0;j<ingredients[i].size();j++){ graph[ingredients[i][j]].push_back(recipes[i]); indeg[recipes[i]]++; } } queue<string> q; for(string& s:supplies){ q.push(s); } vector<string> res; while(!q.empty()){ string x=q.front(); q.pop(); for(string& y:graph[x]){ if(--indeg[y]==0){ q.push(y); res.push_back(y); } } } return res; } };