题目主要信息

给定一个非负索引值 num ，请返回杨辉三角中从上到下第 num 层。索引值从 0 开始。

杨辉三角中，每个数是左上方和右上方的数之和。

方法一：直接模拟

具体方法

了解杨辉三角的应该知道，每一个位置的元素都等于上一层元素的前一列和上一层元素的同列元素之和。$result[i][j]=result[i-1][j-1]+result[i-1][j]result[i]\; [j]\; =\; result[i-1]\; [j-1]\; +\; result[i-1]\; [j]$ 之和。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        // write code here
        int [][]result = new int[num+2][num+1];
        for(int i=0;i<=num;i++){
            for(int j=0;j<=num;j++)
                result[i][j] = 1;
        }
       // Arrays.fill(result,1);
        if(num == 0 || num == 1)
            return result[num];
        // 直接模拟 
        for(int i = 2;i <= num ; i++){
            for(int j=1;j<i;j++){
                // 每一个位置的元素等于上一层的前一个和上一层的同列元素想加
                result[i][j] = result[i-1][j-1]+result[i-1][j];
            }
        }
        return result[num];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}nu{m}^2\mathrm{）}O（num^2）$,需要遍历两次
• 空间复杂度：$O\mathrm{（}nu{m}^2\mathrm{）}O（num^2）$,二维的数组

方法二：滚动数组

具体方法

方法一中使用二维的数组空间复杂度较大，可以发现每一层的数字有上一层确定。可以使用滚动数组降低空间复杂度。

具体的实现是，每次用一个临时容器cur确定前一层的所有数字，然后用pre容器替换掉。最终pre容器存储的数字即是第n层的所有数字，将其用stream流的方式转换为数组。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        // write code here
        // 最终的结果
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= num; ++i) {
            // 临时存当前层
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    // 由左上方和上方
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        // 转化为int数组
        return pre.stream().mapToInt(Integer::valueOf).toArray();
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}nu{m}^2\mathrm{）}O（num^2）$,需要遍历两次
• 空间复杂度：$O\mathrm{（}num\mathrm{）}O（num）$,临时的cur。