【数学】leetcode 119. 杨辉三角 II

119. 杨辉三角 II

题目描述

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

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

示例1：

输入： rowIndex = 3
输出： [1,3,3,1]

示例2：

输入： rowIndex = 0
输出： [1]

示例3：

输入： rowIndex = 1
输出： [1,1]

提示

• $0<=rowIndex<=33$

方法：数学

解题思路

杨辉三角具有如下性质：

• 矩阵的每一行的行首元素为 1，且对角线元素为 1；
• 其余位置上的元素等于其上一行的左右两个元素之和。

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int n = rowIndex + 1;
        vector<vector<int>> arr(n);
        for(int i = 0; i < n; i++) {
            arr[i].resize(i + 1);
            arr[i][0] = 1, arr[i][i] = 1;
            for(int j = 1; j < i; j++)
                arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
        }
        return arr[rowIndex];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析

• 时间复杂度：$O(numRow{s}^2)$。
• 空间复杂度：$O(1)$。