分享程序员开发的那些事...
更新时间：2022-09-25 22:24:05
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