java - 带递归的 LinkedList 的 LinkedList - 循环问题

Question

我有一个列表结构和一个名为树的递归函数。在下面的代码中，它永远不会到达 current == null 语句，因此它将永远运行。

如果我无法使用null，解决方案是什么？

private void tree(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> current = findBiggerPartitionContained(partitions, part);
    if (current == null) {
        return;
    }
    tree(partitions, current);
}

private LinkedList<String> findBiggerPartitionContained(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> max = new LinkedList<>();

    boolean flag = false;
    for (LinkedList<String> item : partitions) {
        if (item.size() > max.size() && part.containsAll(max)) {
            max = item;
            flag = true;
        }
    }

    if (!flag)
        return null;
    flag = false;
    return max;
}

Answer 1

大多数情况下，flag 将为 true，因为您的条件测试 item.size() > max.size()，并且 max 用空列表初始化。当 max 为空时，表达式 part.containsAll(max) 也将为 true，这会导致意外结果。

为了解决这个问题，您可以在 findBiggerPartitionContained 中使用它:

if (item.size() > max.size() && item.containsAll(part)) {
    max = item;
    flag = true;
}

这在树中:

if (current.equals(part)) {
    return;
} else {
    tree(partitions, current);
}

如果我理解正确，您正在寻找 partitions 中包含 part 的最大列表。也许以下内容更不容易出错并且更具可读性:

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

你可以用这个 MCVE 来测试它:

List<String> p0 = new LinkedList<>(Arrays.asList("a", "b", "c"));
List<String> p1 = new LinkedList<>(Arrays.asList("a", "b"));
List<String> p2 = new LinkedList<>(Arrays.asList("a", "b", "c", "d"));
List<String> p3 = new LinkedList<>(Arrays.asList("a", "b", "e", "d"));
List<List<String>> partitions = Arrays.asList(p0, p1, p2, p3);

List<String> part = new LinkedList<>(Arrays.asList("a", "b", "e"));

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

System.out.println(result);

请记住，这可能会返回 null 来处理缺失的 Optional s。