题目描述
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
pic
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
解题思路
在该题的上一题中，是给定k返回k+1行的杨辉三角。
这里当j=0 || j=i时，ret[i][j] = 1，否则ret[i][j] = ret[i-1][j] + ret[i-1][j-1]。
这里要求使用O(k)的空间复杂度。每次生成第i行时，直接在当前行更新元素，但要从后往前遍历。
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex+1, 1);
for(int i=1;i<=rowIndex;i++){
for(int j=i;j>0;j--){
if(j==0 || j==i)
row[j] = 1;
else
row[j] = row[j-1] + row[j];
}
}
return row;
}
网友评论