P66. 帕斯卡三角形

https://algocasts.io/episodes/jwmBr5m8

“没用额外空间,所以空间复杂度是O(1)”. 提到这个是真的好:ok_hand:。又填了一个坑。多谢多谢。

因为之前看书不仔细,都是一看有return且不是常量上来就默认空间复杂是至少是n,而且这个题写法也大都是把List list放在for循环外,也没细想,一直以为是n + n = 2n, 所以是n。

正好这个题一眼看到有return的结构,但空间是O(1)就懵逼了。。大佬就是大佬,视频没有废话的,菜鸡处处能捡到宝:smiley:

@ky

哈哈,有收获就好 。

空间复杂度只看那些为了求解一个问题额外使用的辅助空间,返回结果无论用了多少空间,都不算在内。

确实是处处捡到宝,不止一次了。自己基础差很多时候注意不到,其实视频讲解里真的没一句废话,句句有落点。
话说这题,刚突然想到,要是遇到OA是那种ACM的OJ形式,自己写main函数那种,因为用了List<List>就又变成O(n^2), 但具体到这个题,需要化简为O(n!)么?

@ky

没太明白你的问题。无论是不是自己写 main 函数,这个题目的空间复杂度都是 O(1)。List<List<Integer>> result 是求解出来的结果,这个就是你想要的东西,不会把这部分的空间算到复杂度分析中。因为无论你用什么算法,给 result 的空间都是必需要的且相同的。

额…就是我看到网上一些OJ和leetcode形式不同,需要读取input, 所有代码都在main函数里,结果直接打印出来。比如杭州电子科大的OJ,所以这种情况下List<List> result 算额外空间?但是好像这种OJ都不太问时间空间复杂度:sweat_smile:

    public static void main(String[] args) {
        System.out.println("Please enter a number: ");
        Scanner cin = new Scanner(System.in);
        int num = cin.nextInt();
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            List<Integer> list = Arrays.asList(new Integer[i + 1]);
            list.set(0,1);
            list.set(i,1);
            for (int j = 1; j < i; j++) {
                list.set(j, res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            res.add(list);
        }
        for (List<Integer> l : res) {
            System.out.println(l);
        }
    }

@ky

Hmm,像这种情况,我觉得说算和不算都有道理。建议不要纠结于这种情况。:rofl:

哈哈哈哈哈,好的。十分感谢秒回:grin: