使用常见食材的团体菜肴

Question

我正在研究以下问题：

假设您有一个菜肴列表，其中每道菜都与配料列表相关联。将具有常见成分的菜肴分组在一起。

例如：

输入：

"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"] 

"Chicken Curry" --> ["Chicken", "Curry Sauce"] 

"Fried Rice" --> ["Rice", "Onions", "Nuts"] 

"Salad" --> ["Spinach", "Nuts"] 

"Sandwich" --> ["Cheese", "Bread"] 

"Quesadilla" --> ["Chicken", "Cheese"] 

输出：

("Pasta", "Fried Rice") 

("Fried Rice, "Salad")

("Chicken Curry", "Quesadilla")

("Sandwich", "Quesadilla") 

另外，时间和空间的复杂性是什么？

我想出了下面的代码。有没有更好的方法来解决这个问题？看起来算法是图论中的连接组件。

public static void main(String[] args) {

    List<String> ing1 = Arrays.asList("Tomato Sauce", "Onions", "Garlic");

    List<String> ing2 = Arrays.asList("Chicken", "Curry Sauce");

    List<String> ing3 = Arrays.asList("Rice", "Onions", "Nuts");

    List<String> ing4 = Arrays.asList("Spinach", "Nuts");

    List<String> ing5 = Arrays.asList("Cheese", "Bread");

    List<String> ing6 = Arrays.asList("Chicken", "Cheese");

    Map<String, List<String>> map = new HashMap<>();

    map.put("Pasta", ing1);

    map.put("Chicken Curry", ing2);

    map.put("Fried Rice", ing3);

    map.put("Salad", ing4);

    map.put("Sandwich", ing5);

    map.put("Quesadilla", ing6);

    System.out.println(group(map));

}

private static List<List<String>> group(Map<String, List<String>> map) {

    List<List<String>> output = new ArrayList<>();

    if (map == null || map.isEmpty()) {

        return output;

    }

    Map<String, List<String>> holder = new HashMap<>();

    for (Map.Entry<String, List<String>> entry : map.entrySet()) {

        String key = entry.getKey();

        List<String> value = entry.getValue();

        for (String v : value) {

            if (!holder.containsKey(v)) {

                holder.put(v, new ArrayList<String>());

            }

            holder.get(v).add(key);

        }

    }

    return new ArrayList<List<String>>(holder.values());

}

Answer 1

我们可以使用图论对这种方法进行实际的复杂性估计。“连接组件”方法将具有复杂性，其中是所有成分和菜肴的集合，并且是包含所有关系的集合，其中每个都是一道菜并且是菜肴的成分 。（即假设您将此图存储在邻接列表中，而不是邻接矩阵中）O(|V| + |E|)VE(a, b)abbG = (V, E)在任何需要找出每道菜的所有成分才能找到结果的算法中，您都必须调查每道菜及其所有成分。这将导致需要时间的调查（即遍历），这意味着没有这样的算法可以比您的方法更好。O(|V| + |E|)

Answer 2

让我们首先把这个问题变成一个图形问题。每道菜和每种成分都将是一个.菜肴和配料之间的每个关系都将是.vertexedge让我们分析一下解决方案的最大大小。假设总体上有菜肴和配料，则最大溶液输出是当每道菜都相关时。在这种情况下，输出的大小，因此这是您可以实现的时间复杂度的下限。我们可以很容易地创建一个输入，我们必须迭代所有顶点和边，因此时间复杂度的另一个下限是 。此外，我们必须保存所有顶点和边，因此空间复杂性的下限也是如此。NMN^2N * MM * N现在，让我们分析一下您的解决方案。您迭代所有菜肴=，对于每个菜肴，您迭代所有值=，并与您一起检查字典中是否如此。你的空间复杂性也是如此。我会说你的解决方案很好。NMO(1)O(N * M)O(M * N)

Answer 3

让我们首先把这个问题变成一个图形问题。每道菜和每种成分都将是一个.菜肴和配料之间的每个关系都将是.vertexedge让我们分析一下解决方案的最大大小。假设总体上有菜肴和配料，则最大溶液输出是当每道菜都相关时。在这种情况下，输出的大小，因此这是您可以实现的时间复杂度的下限。我们可以很容易地创建一个输入，我们必须迭代所有顶点和边，因此时间复杂度的另一个下限是 。此外，我们必须保存所有顶点和边，因此空间复杂性的下限也是如此。NMN^2N * MM * N现在，让我们分析一下您的解决方案。您迭代所有菜肴=，对于每个菜肴，您迭代所有值=，并与您一起检查字典中是否如此。你的空间复杂性也是如此。我会说你的解决方案很好。NMO(1)O(N * M)O(M * N)

Answer 4

你只需要在这里建立一个反向地图。我认为你可以通过使用Java8中引入的API以更富有表现力的方式编写代码。Stream基本步骤：从地图中提取所有成分对于每种成分，获得一组菜肴，您将拥有许多这样的集合 - 将所有此类集合收集到一个集合中 - 因此该方法的返回类型变为Set<Set<String>>以下是实现：private static Set<Set<String>> buildReverseMap(Map<String, Set<String>> map) {&nbsp; &nbsp; // extracting all the values of map in a Set&nbsp; &nbsp; Set<String> ingredients = map.values()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .stream()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .flatMap(Set::stream)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .collect(Collectors.toSet());&nbsp; &nbsp; return ingredients.stream()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // map each ingredient to a set&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map(s ->&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.entrySet()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .stream()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .filter(entry -> entry.getValue().contains(s))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map(Map.Entry::getKey)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .collect(Collectors.toSet())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ).collect(Collectors.toSet());}时间复杂度分析：假设你有菜肴和配料，在最坏的情况下，每个Dest可以有每种成分。对于每种成分，您需要迭代每道菜，并检查它是否包含当前成分。这种检查可以摊销完成，因为我们可以为每道菜提供配料。NMO(1)HashSet<String>因此，对于每种成分，您将迭代每道菜，并检查该菜肴是否包含该成分。这给出了要摊销的时间复杂性。O(1)O(M*N)空间复杂性分析：就像在最坏的情况下一样，你可以让每个dist都由每种可用的成分组成。O(M*N)注意：您可以返回 ，而不仅仅是通过更改为List<Set<String>>Set<Set<String>>.collect(Collectors.toSet()).collect(Collectors.toList())