题解 | #杨辉三角(二)#

题意整理

• 给定一个非负索引值num，返回杨辉三角中从上到下第num层。索引值从0开始。
• 杨辉三角中，每个数是左上方和右上方的数之和。

方法一（数组模拟）

1.解题思路

首先新建一个二维数组，用于存储所有数字。遍历每一层，确定每一层子数组，根据每个数等于左上方和右上方的数之和，确定每一层子数组的每一个值。最后返回第num层的子数组即可。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        //新建数组，用于存储所有数字
        int[][] res=new int[num+1][];
        for(int i=0;i<=num;i++){
            //存储当前层数字
            res[i]=new int[i+1];
            //当前层第1个数字
            res[i][0]=1;
            for(int j=1;j<i;j++){
                //每个数等于左上方和右上方的数之和
                res[i][j]=res[i-1][j-1]+res[i-1][j];
            }
            //当前层最后1个数字
            res[i][i]=1;
        }
        
        return res[num];
    }
}

3.复杂度分析

• 时间复杂度：总共两层循环，需要执行$(num+1)\ast (num+2)\mathrm{/}2(num+1)*(num+2)/2$次，所以时间复杂度是$O(nu{m}^2)O(num^2)$。
• 空间复杂度：需要额外大小为$(num+1)\ast (num+2)\mathrm{/}2(num+1)*(num+2)/2$的res数组，所以空间复杂度为$O(nu{m}^2)O(num^2)$。

方法二（滚动list）

1.解题思路

方法一使用了二维数组来存储所有的数字，经过观察可以发现，每一层的数字可以全部由前一层来确定，所以可以使用滚动list的方式，大大地降低空间复杂度。 具体的实现是，每次用一个临时容器tmp确定前一层的所有数字，然后用list容器替换掉。最终list容器存储的数字即是第n层的所有数字，将其用stream流的方式转换为数组。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        //新建数组，记录每一层的数字
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<=num;i++){
            //存储当前层数字
            List<Integer> tmp=new ArrayList<>();
            //当前层第1个数字
            tmp.add(1);
            //如果是第1层
            if(i==1){
                //当前层最后1个数字
                tmp.add(1);
            }
            //如果是第2层及以上
            else if(i>=2){
                for(int j=1;j<i;j++){
                    //每个数等于左上方和右上方的数之和
                    tmp.add(list.get(j-1)+list.get(j));
                }
                //当前层最后1个数字
                tmp.add(1);
            }
            //赋值给list
            list=new ArrayList<>(tmp);
        }
        
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

3.复杂度分析

• 时间复杂度：总共两层循环，需要执行$(num+1)\ast (num+2)\mathrm{/}2(num+1)*(num+2)/2$次，所以时间复杂度是$O(nu{m}^2)O(num^2)$。
• 空间复杂度：最坏情况下，需要额外大小为$num+1num+1$的list和tmp容器，所以空间复杂度为$O(num)O(num)$。