LeetCode119. Pascal's Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

img
In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1
2
Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?


my ac in c++

12 ms 8.4 MB

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
vector<int> getRow(int rowIndex) {
if (rowIndex < 0)
return{};
if (rowIndex == 0)
return{ 1 };
if (rowIndex == 1)
return{ 1,1 };
vector<int> ret,sub(2,1);
for(int row=2;row<=rowIndex;row++)
{
ret = {};
//first
ret.push_back(1);

//middle
for (int col =0; col<row-1; col++)//1.
ret.push_back(sub[col]+sub[col+1]);

//last
ret.push_back(1);
sub = ret;
}

return ret;
}

思路

  1. 参考[118] 杨辉三角的思路,迭代dp。观察图,发现前两行是固定的,直接返回就好。
  2. dp,开两个数组ret和sub,sub把前面结果保存下来,sub初始化是index=1的时候,就是第二行[1,1]。
  3. 迭代ret: 清空, 塞1,塞中间,塞1。
  4. 更新sub:保存当前ret。

细节

  1. 不要用迭代器,用下标做。用迭代器判断的时候很容易出错的!

Follow up: O(k) space

LC in cpp

0 ms

1
2
3
4
5
6
7
8
9
10
vector<int> getRow(int rowIndex) {
vector<int> res(rowIndex + 1);
res[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
for (int j = i; j >= 1; --j) {
res[j] += res[j - 1];
}
}
return res;
}

思路

  1. res.size()是rowIndex,初始化一个size大小的容器,全部值为0.
  2. res[0]永远是1.
  3. res[rowIndex]永远是1.
  4. 想象成一个栈,从后res[rowIndex]往前迭代,每次更新为前一个数加自身的和。因为res本身就是一个上次的结果了,为了不改变以前的结果,所以要从后往前!!这也算是一种动态规划吧,而且不用额外空间!!

思路

Thanks for Support.