当前位置:网站首页>Leetcode-2115: find all the dishes that can be made from the given raw materials
Leetcode-2115: find all the dishes that can be made from the given raw materials
2022-07-03 00:47:00 【Chrysanthemum headed bat】
leetcode-2115: Find all the dishes you can make from a given raw material
subject
Do you have n
Information about different dishes . Here's an array of strings recipes
And a two-dimensional string array ingredients
. The first i
The name of this dish is recipes[i]
, If you have it all Raw materials ingredients[i]
, Then you can To make a This dish . The raw material of a dish may be Another way food , in other words ingredients[i]
May contain recipes
Another string in .
And give you an array of strings supplies
, It contains all the raw materials you had at the beginning , You have an unlimited number of raw materials .
Please return to all the dishes you can make . You can In any order Return to them .
Note that the two dishes may contain each other in their raw materials .
Example 1:
Input :recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output :["bread"]
explain :
We can make "bread" , Because we have raw materials "yeast" and "flour" .
Example 2:
Input :recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output :["bread","sandwich"]
explain :
We can make "bread" , Because we have raw materials "yeast" and "flour" .
We can make "sandwich" , Because we have raw materials "meat" And can make raw materials "bread" .
Example 3:
Input :recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output :["bread","sandwich","burger"]
explain :
We can make "bread" , Because we have raw materials "yeast" and "flour" .
We can make "sandwich" , Because we have raw materials "meat" And can make raw materials "bread" .
We can make "burger" , Because we have raw materials "meat" And can make raw materials "bread" and "sandwich" .
Example 4:
Input :recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
Output :[]
explain :
We can't make any dishes , Because we only have raw materials "yeast" .
Problem solving
Method 1 : Violent simulation
Made from existing raw materials , Put the newly cooked dishes , Also added to raw materials , Repeat until no new dishes are added , Just return the result
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){
// Record existing raw materials
set.insert(s);
}
int preLen;// The current length of all raw materials
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;// If true It means you can cook this dish
for(int j=0;j<tmp.size();j++){
if(!set.count(tmp[j])){
ok=false;
break;
}
}
if(ok){
// If this dish can be made
set.insert(recipes[i]);// This dish is added as raw material
res.push_back(recipes[i]);// Save results
}
}
if(set.size()<=preLen) break;// If the raw materials are no longer increased , It means that the rest of the dishes can't be made
}
return res;
}
};
Method 2 : A topological sort
Starting from raw materials , When the corresponding degree of the dish is 0 When , It indicates that the raw materials are complete , Add the dishes to the raw materials .
Get a penetration of 0 The point of , It's a dish that can be made .
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;
}
};
边栏推荐
- The "2022 China Digital Office Market Research Report" can be downloaded to explain the 176.8 billion yuan market in detail
- [MCU project training] eight way answering machine
- 关于XML一些介绍和注意事项
- 【AutoSAR 五 方法论】
- Markdown tutorial
- 指针进阶(一)
- AttributeError: ‘tuple‘ object has no attribute ‘layer‘问题解决
- 微信小程序获取某个元素的信息(高、宽等),并将px转换为rpx。
- About the practice topic of screen related to unity screen, unity moves around a certain point inside
- antv x6节点拖拽到画布上后的回调事件(踩大坑记录)
猜你喜欢
Why is the website slow to open?
【雅思阅读】王希伟阅读P1(阅读判断题)
How SQLSEVER removes data with duplicate IDS
Shell 实现文件基本操作(sed-编辑、awk-匹配)
leetcode-2280:表示一个折线图的最少线段数
AEM: Nanlin fan Ben et al. - plant rhizosphere growth promoting bacteria control soybean blight
【AutoSAR 九 C/S原理架构】
Pageoffice - bug modification journey
Sentry developer contribution Guide - configure pycharm
Liad: the consumer end of micro LED products is first targeted at TVs above 100 inches. At this stage, it is still difficult to enter a smaller size
随机推荐
AEM: Nanlin fan Ben et al. - plant rhizosphere growth promoting bacteria control soybean blight
LeedCode1480. Dynamic sum of one-dimensional array
Attributeerror: 'tuple' object has no attribute 'layer' problem solving
Markdown tutorial
logback配置文件
Unity learns from spaceshooter to record the difference between fixedupdate and update in unity for the second time
Rust字符串切片、结构体和枚举类
Explain in detail the significance of the contour topology matrix obtained by using the contour detection function findcontours() of OpenCV, and how to draw the contour topology map with the contour t
An excellent orm in dotnet circle -- FreeSQL
1.11 - 总线
数组与集合性能比较
Hdu3507 (slope DP entry)
【luogu P4320】道路相遇(圆方树)
【AutoSAR 五 方法论】
lex && yacc && bison && flex 配置的问题
AttributeError: ‘tuple‘ object has no attribute ‘layer‘问题解决
使用jenkins之二Job
Automated defect analysis in electronic microscopic images
Some introduction and precautions about XML
机器学习:numpy版本线性回归预测波士顿房价