做网站的税是多少,商贸有限公司起名,ps插件国外网站,软件开发外包服务公司文章目录1. 题目2. 解题1. 题目
你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。 第 i 道菜的名字为 recipes[i] #xff0c;如果你有它 所有 的原材料 ingredients[i] #xff0c;那么你可以 做出 这道菜。一道菜的原材料可能是 另…
文章目录1. 题目2. 解题1. 题目
你有 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 。提示
n recipes.length ingredients.length
1 n 100
1 ingredients[i].length, supplies.length 100
1 recipes[i].length, ingredients[i][j].length, supplies[k].length 10
recipes[i], ingredients[i][j] 和 supplies[k] 只包含小写英文字母。
所有 recipes 和 supplies 中的值互不相同。
ingredients[i] 中的字符串互不相同。来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-all-possible-recipes-from-given-supplies 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
拓扑排序问题解决依赖先后顺序
class Solution {
public:vectorstring findAllRecipes(vectorstring recipes, vectorvectorstring ingredients, vectorstring supplies) {unordered_mapstring, unordered_setstring g;unordered_mapstring, int indegree;unordered_setstring rset(recipes.begin(), recipes.end());for(auto food : supplies)indegree[food] 0;//初始材料的入度为0for(int i 0; i recipes.size(); i){for(auto j : ingredients[i]){g[j].insert(recipes[i]);//建图indegree[recipes[i]];//记录入度}}queuestring q;for(auto p : indegree){if(p.second 0)//入度为0的进入队列q.push(p.first);}vectorstring ans;while(!q.empty()){string food q.front();q.pop();if(rset.find(food) ! rset.end())ans.push_back(food);for(auto nt : g[food]){if(--indegree[nt] 0)//入度减1以后没有依赖了进入队列q.push(nt);}}return ans;}
};448 ms 154 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
