Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return
Return
[1,3,3,1]
.[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
Note:
Could you optimize your algorithm to use only O(k) extra space?
» Solve this problemCould you optimize your algorithm to use only O(k) extra space?
[解题报告]
把上面的例子变一下型就清楚了。
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
定义T[i][j]为该三角形第i行,第j列的元素,所以可以获得递推函数为
T[i][j] = T[i-1][j] + T[i-1][j-1] if i>0
&& j>0
Or
= 1 if
i=0
Or
=
T[i-1][j] if j=0
滚动数组实现。注意Line11,要从后往前加,否则会产生冗余计算。
[Code]
1: vector<int> getRow(int rowIndex) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: vector<int> result;
5: result.resize(rowIndex+2);
6: for(int i =0; i< rowIndex+2; i++)
7: result[i] = 0;
8: result[1]=1;
9: for(int i =0; i< rowIndex; i++)
10: {
11: for(int j =rowIndex+1; j>0; j--)
12: {
13: result[j] = result[j-1] + result[j];
14: }
15: }
16: result.erase(result.begin());
17: return result;
18: }
No comments:
Post a Comment