网站开发技术 下载,海外服务器租用平台,广告营销专业,做网站是要写代码的吗拓扑排序 题面
题目链接#xff1a;2115. 从给定原材料中找到所有可以做出的菜 - 力扣#xff08;LeetCode#xff09; 你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] #xff0c;如果你有它 所有… 拓扑排序 题面
题目链接2115. 从给定原材料中找到所有可以做出的菜 - 力扣LeetCode 你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] 如果你有它 所有 的原材料 ingredients[i] 那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。 同时给你一个字符串数组 supplies 它包含你初始时拥有的所有原材料每一种原材料你都有无限多。 请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。 注意两道菜在它们的原材料中可能互相包含。 解题思路
做出一个菜可以由这个菜作为原料做出另一个且原料无限
很容易幻想出一个有向图从原料指向各个目标菜而拥有公共原料且之间存在互相作为原料的情况则可以看作图的后序 了解过或者学习过拓扑排序的到这里应该就能判断谁作为队列的初始元素了
但是题目给出的是原料有哪些需要做的菜有哪些它们又各自需要哪些作为原料
所以我们需要用哈希表存储这些关系避免大量重复的遍历寻找
哈希表1一个原料能做出哪些菜
哈希表2一个菜的入度为几因为每个元素都为string类型所以也是需要用哈希表
拓扑排序套路写法
class Solution {
public:vectorstring findAllRecipes(vectorstring recipes,vectorvectorstring ingredients,vectorstring supplies) {unordered_mapstring, int indegree;unordered_mapstring, vectorstring out;queuestring q;vectorstring ans;for (string i : supplies)q.push(i);for (int i 0; i recipes.size(); i) {indegree[recipes[i]] ingredients[i].size();for(string var:ingredients[i]){out[var].push_back(recipes[i]);}}while (!q.empty()) {string now q.front();q.pop();for(string aim:out[now]){if(--indegree[aim]0){ans.push_back(aim);q.push(aim);}}}return ans;}
};
