119. 杨辉三角 II

刷题记录
留言

119. 杨辉三角 II

题目

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

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

示例 1:

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

示例 2:

1
2
输入: rowIndex = 0
输出: [1]

示例 3:

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

提示:

  • 0 <= rowIndex <= 33

注意要点

没啥注意的，考察数组知识。这里记录一些可以节约时间、空间的奇淫巧技

最普通做法 二维数组

二维数组，模拟铺开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> yanghui(rowIndex+1);
        for(int i=0;i<=rowIndex;i++){
        	// 首先将该层的数组空间申请下来	
            yanghui[i].resize(i+1);
            // 初始化两边的1
            yanghui[i][0]=yanghui[i][i]=1;
            // 依次将中间填上去
            for(int j=1;j<i;j++){
                yanghui[i][j] = yanghui[i-1][j-1]+yanghui[i-1][j];
            }
        }
        return yanghui[rowIndex];
    }
};

两个一维数组

二维数组我们可以发现，当前层只跟上一层有关系，那么只记录上一层就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> pre,cur;

        for(int i=0;i<=rowIndex;i++){
            cur.resize(i+1);
            cur[0]=cur[i]=1;
            for(int j=1;j<i;j++){
                cur[j] = pre[j-1]+pre[j];
            }
            pre = cur;
        }
        return cur;
    }
};

一个一维数组

我们还发现当前层的数只和上一层的该位置的数和前一个位置数有关，那么我们可以不破坏前一个数，倒着更新当前数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> cur(rowIndex+1);
        // 显然我们需要在循环开始前将最开始的1进行标注
        cur[0]=1;
        // 因为跟i-1相关，所以i要从1开始
        for(int i=1;i<=rowIndex;i++){
        	// 倒着填内容
            for(int j=i;j>0;j--){
                cur[j] = cur[j]+cur[j-1];
            }
        }
        return cur;
    }
};