文章目錄

• • 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:vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {unordered_map<string, unordered_set<string>> g;unordered_map<string, int> indegree;unordered_set<string> 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]]++;//記錄入度}}queue<string> q;for(auto& p : indegree){if(p.second == 0)//入度為0的進入隊列q.push(p.first);}vector<string> 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阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2115. 从给定原材料中找到所有可以做出的菜（拓扑排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。