Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies
2115. Find All Possible Recipes from Given Supplies
給你三個列表recipes/ingredients/supplies分別表示食譜、食譜[i]所需材料、提供的
材料，求出提供的材料可以完成幾種食譜中的食物，食譜做出來的東西也可以是材料且
提供的材料沒有數量限制。

思路:
1.先用map記錄每個材料可以做出哪些食譜的東西，再另外記錄每個食譜還缺幾個材料。
2.用1的map把提供的材料塞給所有需要的食譜(所需材料-1)，如果食譜所有食物都到齊
  了也把他加到材料裡面。
3.不斷重複1和2直到材料都分配完。
4.把材料都到齊的食譜返回。

Java Code:
-----------------------------------------------
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>>
ingredients, String[] supplies) {
        int n = recipes.length;
        Map<String, List<Integer>> map = new HashMap<>();
        int[] need = new int[n];
        for (int i = 0; i < n; i++) {
            need[i] = ingredients.get(i).size();
            for (String ingredient : ingredients.get(i)) {
                map.putIfAbsent(ingredient, new ArrayList<>());
                map.get(ingredient).add(i);
            }
        }

        Deque<String> suppliesList = new ArrayDeque<>();
        Collections.addAll(suppliesList, supplies);

        while (!suppliesList.isEmpty()) {
            String providedIngredient = suppliesList.poll();
            if (map.containsKey(providedIngredient)) {
                for (Integer recipeId : map.get(providedIngredient)) {
                    need[recipeId]--;
                    if (need[recipeId] == 0) {
                        suppliesList.add(recipes[recipeId]);
                    }
                }
                map.remove(providedIngredient);
            }
        }

        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (need[i] == 0) {
                res.add(recipes[i]);
            }
        }
        return res;
    }
}
-----------------------------------------------

--
https://i.imgur.com/ZUx84aU.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1742568960.A.1AB.html
推 JIWP: 大師