119.杨辉三角2

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1:

1
2
输入: rowIndex = 3
输出: [1,3,3,1]

关键在于直接从后往前更新每个元素的值，这和[88.合并两个有序数组][https://leetcode.cn/problems/merge-sorted-array/]的思路不谋而合

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    // getRow方法接受一个整数rowIndex，返回帕斯卡三角形中第rowIndex行的所有元素
    public List<Integer> getRow(int rowIndex) {
        // 创建一个ArrayList来存储目标行的所有元素
        List<Integer> row = new ArrayList<Integer>();
        // 帕斯卡三角形的第一个元素总是1
        row.add(1);
        // 从第二个元素开始遍历至rowIndex指定的位置
        for (int i = 1; i <= rowIndex; ++i) {
            // 先在行尾添加一个0，作为计算当前行新元素的占位符
            row.add(0);
            // 从行尾开始向前遍历，更新每个元素的值
            // 每个元素都是它自身加上它前一个元素的和
            // 这里从行尾开始遍历是为了确保在更新元素值时使用的是上一行的元素值
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        // 返回构建完成的行
        return row;
    }
}