律师行业做网站的必要性,中轻成都设计院,汽油价格最新调整最新消息,蓬莱市住房和规划建设管理局网站思路#xff1a;拓补排序#xff0c;哈希表
在思路上其实很好发现#xff0c;我们需要有一个明确的做菜顺序#xff0c;也就是说需要定下来我们根据原材料先做哪些菜#xff0c;然后做完该做的菜之后#xff0c;后来又能做哪些菜。
你也发现了#xff0c;这个顺序其实…思路拓补排序哈希表
在思路上其实很好发现我们需要有一个明确的做菜顺序也就是说需要定下来我们根据原材料先做哪些菜然后做完该做的菜之后后来又能做哪些菜。
你也发现了这个顺序其实就是拓补排序的顺序我们构造出来这样的一个图就行了虽然说处理起来很麻烦....需要用到哈希表进行映射才行。
这里哈希表用了两个一个是用来构建拓补排序的图的一个是用来存储入度的因为我们需要判断哪个可以先开始制作。
OK构造出来做菜的顺序了也与处理完了入度我们首先开始下手的肯定是原材料因为原材料肯定入度为0这是题目中推出的信息只有菜谱上的菜之间才可能会有入度。
在处理完原材料之后减去对应的入度之后我们开始判断食谱。
注意食谱这里你需要经过多次循环才能说得出结果根据数据范围定义循环的次数因为我们在每一次遍历完数组之后可能会有原先入度不是0但是遍历完之后入度为0的情况出现所以这里需要多次对于数组进行遍历。
class Solution {
public:vectorstring findAllRecipes(vectorstring recipes, vectorvectorstring ingredients, vectorstring supplies) {mapstring,intm;mapstring,vectorstrings;for(int i0;irecipes.size();i)m[recipes[i]]0;for(int i0;iingredients.size();i){for(int j 0;jingredients[i].size();j){m[ingredients[i][j]]0;}}for(int i0;irecipes.size();i){for(int j0;jingredients[i].size();j){s[ingredients[i][j]].push_back(recipes[i]);}m[recipes[i]]ingredients[i].size();}vectorstringres;for(int i0;isupplies.size();i){if(m[supplies[i]]0){for(int j0;js[supplies[i]].size();j){m[s[supplies[i]][j]]--;}}}vectorboolst(recipes.size(),false);int i0;int n1e5;while(n--){if(m[recipes[i]]0!st[i]){res.push_back(recipes[i]);st[i]true;for(int j0;js[recipes[i]].size();j){m[s[recipes[i]][j]]--;}}i(i1)%recipes.size();}return res;}
};
上代码
