119. Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
代码如下:(使用双数组处理，未优化版)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class
Solution {
public
:
vector<
int
> getRow(
int
rowIndex) {
vector<
int
> curVec;
vector<
int
> nextVec;
if
(rowIndex < 0)
return
curVec;
for
(
int
i = 0;i <= rowIndex; i++)
{
for
(
int
j = 0;j<=i;j++)
{
if
(j == 0)
nextVec.push_back(1);
else
{
if
(j >= curVec.size())
nextVec.push_back(curVec[j-1]);
else
nextVec.push_back(curVec[j] + curVec[j-1]);
}
}
curVec.swap(nextVec);
nextVec.clear();
}
return
curVec;
}
};
|
使用思路：
The basic idea is to iteratively update the array from the end to the beginning.
从后到前来更新结果数组。
参考自：https://discuss.leetcode.com/topic/2510/here-is-my-brief-o-k-solution
|
1
2
3
4
5
6
7
8
9
10
11
|
class
Solution {
public
:
vector<
int
> getRow(
int
rowIndex) {
vector<
int
> result(rowIndex+1, 0);
result[0] = 1;
for
(
int
i=1; i<rowIndex+1; i++)
for
(
int
j=i; j>=1; j--)
result[j] += result[j-1];
return
result;
}
};
|
2016-08-12 10:46:10
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837189
