type
status
date
slug
summary
tags
category
icon
password
创建时间
Jan 8, 2025 01:22 AM
你有
n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。同时给你一个字符串数组
supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
注意两道菜在它们的原材料中可能互相包含。
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]中的字符串互不相同。
拓扑排序
思路：本题首先要读懂题目。题目中有个条件十分重要——「所有
recipes 和 supplies 中的值互不相同」，这个条件告诉我们，图中没有自环，方便我们处理，不需要特殊讨论。因此我们可以直接使用拓扑排序的思想；步骤
- 构图：
- 使用
unordered_map来构图。其实和vector构图是一样，题中的节点标识是字符串类型，我们没办法使用下标来进行标识，故而采用哈希表。同理，节点度也采用同样的处理方式。 - 此外，要注意理解题目的意思，图的方向不要构造反了。
- 拓扑排序：
- 初始化时，队列中的节点，需要经过校验后，才能放入。满足两个条件：节点度为 0 以及在
supplies中。 - 在拓扑排序的过程中，需要判断是否是菜谱中的菜，如果是，需要放入答案中。这样也使用哈希表来加速访问。
在初始化时，不需要判断节点度是否为 0，题目说明了「所有
recipes 和 supplies 中的值互不相同」，因此supplies中的节点必然是度为 0 的。📎 参考
- 无