目录
- 一、问题描述
- 二、示例及约束
- 三、代码
- 方法一:数学
- 四、总结
一、问题描述
给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
二、示例及约束
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
● 1 <= numRows <= 30
三、代码
方法一:数学
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret(numRows);//创建二维数组ret,初始数组的行数为numRows
for (int i = 0; i < numRows; i++) {
ret[i].resize(i + 1);//每行初始化为i + 1列
ret[i][0] = ret[i][i] = 1; //每行最左和最右元素固定为1
/*每个数是它左上方和右上方的数的和
for (int j = 1; j < i; ++j) {
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}*/
for (int j = 1; j <= i / 2; j++) {
//对于杨辉三角而言,左右是对称的,因此遍历一半即可
ret[i][j] = ret[i - 1][j -1] + ret[i - 1][j];
if (i - j != j) {
//当i是奇数的时候,最中间的数是加法得到的,不能对称赋值得到
ret[i][i - j] = ret[i][j];//对称赋值
}
}
}
return ret;
}
};
四、总结
时间复杂度:
方法一:O(
n
u
m
R
o
w
s
2
numRows^2
numRows2)。
空间复杂度:
方法一:O(1),不考虑返回的数组空间。
方法 | 时间复杂度 | 空间复杂度 |
---|---|---|
方法一 | O( n u m R o w s 2 numRows^2 numRows2) | O(1) |