我在帕斯卡三角形代码中面临的逻辑错误是什么?

What is the logical error I am facing in Pascal's Triangle code?

提问人:Samik Pandit 提问时间:9/18/2022 更新时间:9/18/2022 访问量:39

问:

错误的代码:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> finallist = new ArrayList<List<Integer>>();
        if (numRows == 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            finallist.add(list1);
            return finallist;
        }
        else if (numRows == 2){
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            list1.add(1);
            list2.add(1);
            list2.add(1);
            finallist.add(list1);
            finallist.add(list2);
            return finallist;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> alist = new ArrayList<>();
        list1.add(1);
        list2.add(1);
        alist.add(1);
        list2.add(1);
        alist.add(1);
        finallist.add(list1);
        finallist.add(list2);
        for (int j = 3;j <= numRows;j++) {
            List<Integer> list3 = new ArrayList<>();
            list3.add(1);
            for (int i = 0; i < alist.size() - 1; i++) {
                list3.add(alist.get(i) + alist.get(i + 1));
            }
            list3.add(1);
            finallist.add(list3);
            alist.clear();
            alist.addAll(list3);
            list3.clear();
        }
        return finallist;
    }
}

显示的输出: 输入:5

输出:[[1],[1,1],[],[],[]]

预期:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

正确代码:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> finallist = new ArrayList<List<Integer>>();
        if (numRows == 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            finallist.add(list1);
            return finallist;
        }
        else if (numRows == 2){
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            list1.add(1);
            list2.add(1);
            list2.add(1);
            finallist.add(list1);
            finallist.add(list2);
            return finallist;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> alist = new ArrayList<>();
        list1.add(1);
        list2.add(1);
        alist.add(1);
        list2.add(1);
        alist.add(1);
        finallist.add(list1);
        finallist.add(list2);
        for (int j = 3;j <= numRows;j++) {
            List<Integer> list3 = new ArrayList<>();
            list3.add(1);
            for (int i = 0; i < alist.size() - 1; i++) {
                list3.add(alist.get(i) + alist.get(i + 1));
            }
            list3.add(1);
            finallist.add(list3);
            alist.clear();
            alist.addAll(list3);
        }
        return finallist;
    }
}

在我错误的代码中,我在外循环之外声明了“list3”。将“alist”添加到我的“finallist”中,这实际上是我的答案。清除之前的“alist”后,这些元素再次从“list3”复制到“alist”。由于我必须在“list3”中输入下一行的元素,因此我正在清除“list3”的元素,以便为下一行输入元素。

在我的正确代码中,唯一的区别是我在内部循环之外声明了“list3”,但在外部循环内部,我不需要为下一行迭代清除“list3”。当“list3”在内部循环之外被调用/声明时,它将被自动清除,即元素被自动刷新。

我认为很可能我在“错误代码”中的“object.clear”部分犯了一些逻辑错误,这些元素没有插入到最后一个部分,而是被清除了。

谁能消除我的疑虑?

java 列表 arraylist 嵌套列表 pascals-triangle

评论


答:

0赞 ILikeTrains 9/18/2022 #1

错误代码的问题是,您在外部循环中添加到列表的每个 list3 实例都会被清除。

您会看到,通过将列表 x 添加到另一个列表 y 中,您不是将值从列表 x 复制到另一个列表 y,而是将对列表 x 的引用提供给列表 y。

通过清除列表 x,在将列表 x 提供给列表 y 后,您可以清除所有值。

这就是为什么在前两个列表(您没有清除)之后,循环中添加到最终列表的所有列表都是对空列表的引用,因此:

[[1], [1, 1], [], [], []]

您可以像这样查看最终列表:

finnalList[l1, l2, l3, l4, l5]

l1 -> 列表[[1]]

l2 -> 列表[[1, 1]]

l3 ->列表[[]]

l4 -> 列表[[]]

l5 -> 列表[[]]

您不是在复制列表中的值,而是在最终列表中提供对这些列表的引用(您在错误的代码中清除了这些值)。