题目:
Given an index k, return the kth row of the Pascal's triangle.
给定k,求杨辉三角第k行的数字
For example, given k = 3,
Return [1,3,3,1]
.
杨辉三角
[ 0 [1], 1 [1,1], 2 [1,2,1], 3 [1,3,3,1], 4 [1,4,6,4,1] ]
Note:
Could you optimize your algorithm to use only O(k) extra space?
你可以只使用O(k)的存储空间使你的算法最优吗?即空间复杂度为 O(k)
代码:
class Solution { public: vector<int> getRow(int rowIndex) { //滚动数组 vector<int> array; for (int i = 0; i <= rowIndex; i++) { // 0 [1], // 1 [1,1], // 2 [1,2,1], // 3 [1,3,3,1], // 4 [1,4,6,4,1] //每次循环,确定第i行的数据,下次循环的结果由上次循环得到的数据确定 //比如第5行,先确定第4个元素4是由第四行的第4个元素1与第3个元素3想加得到 //第3个元素6是由第四行的第3个元素3和第2个元素3求和得到 for (int j = i - 1; j > 0; j--) { array[j] = array[j - 1] + array[j]; } array.push_back(1); } return array; } };