友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

2115. 从给定原材料中找到所有可以做出的菜

你有 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] 只包含小写英文字母。

  • 所有 recipessupplies 中的值互不相同。

  • ingredients[i] 中的字符串互不相同。

思路分析

拓扑排序。

在拓扑排序的基础上,对起点做了限制;对遍历中涉及的点,只有一部分满足要求。

2115 10
  • 一刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-09-22 14:39:30
 */
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
  int n = recipes.length;
  Map<String, Integer> inDegree = new HashMap<>();
  Map<String, Set<String>> graph = new HashMap<>();
  for (int i = 0; i < n; i++) {
    String target = recipes[i];
    List<String> start = ingredients.get(i);
    for (String s : start) {
      graph.computeIfAbsent(s, key -> new HashSet<>()).add(target);
    }
    inDegree.put(target, inDegree.getOrDefault(target, 0) + start.size());
  }
  // 只有 recipes 统计入度,那么,所有 supplies 都可以作为起点
  Deque<String> queue = new ArrayDeque<>(Arrays.asList(supplies));
  while (!queue.isEmpty()) {
    String cur = queue.poll();
    for (String s : graph.getOrDefault(cur, Collections.emptySet())) {
      Integer ingress = inDegree.getOrDefault(s, 0) - 1;
      if (ingress == 0) {
        queue.offer(s);
      }
      inDegree.put(s, ingress);
    }
  }
  List<String> result = new ArrayList<>();
  for (String recipe : recipes) {
    if (inDegree.getOrDefault(recipe, 0) == 0) {
      result.add(recipe);
    }
  }
  return result;
}