杨辉三角

什么是杨辉三角

在杨辉三角中，每个数是它左上方和右上方的数的和。如下图所示。

杨辉三角

题目

题目1：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。——LeetCode118
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

题目2：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。——LeetCode119
输入: 3
输出: [1,3,3,1]

抽象化模型

如果把杨辉三角前五行存入一个二维数组中，设row为当前行数(从0起始)，rowS为row行的第一个元素下标，rowE为row行的最后一个元素下标。则row，rowS和rowE之间的关系如下图所示：

二维数组存储杨辉三角前五行

观察上图可知：

1. 当前行数为row，则数组最后一个元素的下标rowE等于row。
2. 当前行数row，下标为rowS的第一个元素和下标为rowE的最后一个元素固定为1。
3. 当前行数row的中间元素，下标i的元素等于row-1行的下标i和下标i-1元素的和。

题目1代码

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new LinkedList<>();
    //健壮性校验
    if(numRows <= 0){
        return res;
    }
    //从第1行开始，下标从0开始
    int row = 0;
    //生成numRows行的杨辉三角
    while(row < numRows){
        //第row行的数据存储在list中
        List<Integer> list = new LinkedList<>();
        //如果当前row大于1(也就是从第三行起)，需要获取前一行的数据进行计算
        List<Integer> preList = row > 1 ? res.get(row - 1) : null;
        //为符合示例图，便于理解，这里定义rowS和rowE。其实就是0和row。
        final int rowS = 0;
        int rowE = row; 
        //生成第row行的数据
        for(int i = rowS; i <= rowE; ++i){
            //如果是首尾两个元素，固定为1
            if(i == rowS || i == rowE){
                list.add(1);
            } else {
                //否则，是前一行的第i个元素与第i-1个元素之和
                list.add(preList.get(i) + preList.get(i - 1));
            }
        }
        //存储第row行的结果
        res.add(list);
        row++;
    }
    return res;
}

题目2代码

题目1的杨辉三角打印出来找到对应的行，即可解决问题。不过，这里结果只要指定的行，我们没有必要保存所有的行，可以使用一维数组记录每次算出来的第row行结果，一直算到要求的第k行停止。

public List<Integer> getRow(int rowIndex) {
    //结果放入list返回
    List<Integer> res = new LinkedList<>();
    //健壮性校验
    if(rowIndex < 0){
        return res;
    }
    //rowIndex从0开始，rowIndex行一共rowIndex+1个元素。
    //初始化长度为rowIndex+1的数组
    int[] temp = new int[rowIndex + 1];
    //row从0开始
    int row = 0;
    //计算每一行的元素，直到第rowIndex行
    while(row <= rowIndex){
        //为便于理解，与示例图一致，定义rowS和rowE。其实就是0和row。
        final int rowS = 0;
        int rowE = row;
        //从row行的最后一个元素下标rowE开始，往前遍历计算
        //从后向前，因为非首尾下标i的元素等于上一行的i和i-1元素之和
        //也就是上一行的i-1的元素即在计算本行的i时用到，也在计算本行的i-1时用到
        //如果从前往后，那么计算本行的i-1时就会把上一行的i-1元素覆盖掉，无法计算i位置的元素
        for(int i = rowE; i >= rowS; --i){
            //首尾元素固定为1
            if(i == rowS || i == rowE){
                temp[i] = 1;
            } else {//中间元素i为上一行的i-1和i元素之和
                temp[i] = temp[i-1] + temp[i];
            }
        }
        row++;
    }
    //数组转换为list返回
    for(int i = 0; i <= rowIndex; ++i){
        res.add(temp[i]);
    }
    return res;
}