Java ArrayList初始化

Question

我一直在尝试理解以下使用深度优先搜索 (DFS) 打印出所有长度为 k 的唯一组合的代码，这些组合由数字 [1..n]

组成

请参阅私有 dfs 函数中注释 "doubt" 的行

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (n <= 0 || n < k)
        return result;
    ArrayList<Integer> item = new ArrayList<Integer>();
    dfs(n, k, 1, item, result); 
    return result;
}

private void dfs(int n, int k, int start, ArrayList<Integer> item,
        ArrayList<ArrayList<Integer>> res) {
    if (item.size() == k) {
        res.add(new ArrayList<Integer>(item)); /*doubt*/
        return;
    }

    for (int i = start; i <= n; i++) {
        item.add(i);
        dfs(n, k, i + 1, item, res);
        item.remove(item.size() - 1);
    }
}

如果我将其更改为 res.add(item)，它 returns 结果为空列表的列表。 ListObject.add(E e) 是一个完全有效的函数，为什么它在这里不起作用？

Answer 1

所以你的问题涉及这两个备选方案：

// works
res.add(new ArrayList<Integer>(item));

// won't work, results in empty lists
res.add(item);

new ArrayList<Integer>(item)的目的是创建一个与原来的内容相同的新列表，有效地克隆原来的。

如果您不克隆原始文件，它将保持空白。第一次调用dfs，item为空，再看这个循环：

for (int i = start; i <= n; i++) {
    item.add(i);
    dfs(n, k, i + 1, item, res);
    item.remove(item.size() - 1);
}

添加到 item 的每个元素稍后都会被删除。这就是为什么在没有克隆步骤的情况下最终得到空列表的原因。如果不克隆，您不仅会得到一个空列表列表，而且所有空列表实际上都是您在 combine 中创建的原始 ArrayList，在第一次调用 dfs 之前。

Answer 2

这是因为 item.remove(item.size() - 1); 正在修改您刚刚添加到结果列表中的同一个列表。所以它总是最终删除所有项目。您拥有的解决方案实际上是复制项目列表并将它们存储在结果列表中。没有人引用该列表，因此它不会被修改。

Java ArrayList初始化

Java ArrayList initialization

java

arraylist

function-parameter