LeetCode118. Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

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

Example:

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

LC in cpp: v.resize(row+1)

思路

  • 初始化外部容器,每行内部容器resize(row+1),头尾(尾是row)是1,中间是上层的和。
  • Unfortunately resize initializes the values in the vector.
  • To gain maximum efficiency ,you should use your own allocator with resize.

my code

12 ms 8.8 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret(numRows);//1.
for (int row = 0; row<numRows; row++)
{
ret[row].resize(row + 1);//2.
ret[row][0] = ret[row][row] = 1;//3.

for (int col = 1; col<row; col++)
{
ret[row][col] = ret[row - 1][col - 1]
+ ret[row - 1][col];//4.
}
}
return ret;
}

细节

  1. 记得初始化,不然开始就数组越界
  2. v.resize(row+1);重新定义容器大小,注意是row+1
  3. 头尾是1,因为size是row+1,所以尾是row,不是row-1
  4. 中间是上层之和

LC official solution:DP

Intuition

  • If we have the a row of Pascal’s triangle, we can easily compute the next row by each pair of adjacent values.
  • the iterative approach can be classified as dynamic programming

Algorithm

  1. generate the overall triangle list, which will store each row as a sublist.
  2. special case of 0 row, return [1]
  3. If numRows > 0:initialize triangle with [1] as its first row, and proceed to fill the rows

Complexity Analysis

  • O(n^2) Time : n(n+1)/2=n^2
  • O(n^2) Space

my code

8 ms 8.8 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret;
if (!numRows)
return ret;//0.
ret.push_back(vector<int>(1,1));//0 row,1.
for (int row = 1; row<numRows; row++)//1~numrows-1 row
{
vector<int> sub;
sub.push_back(1);//first col
for(int col=1;col<row;col++)//2.
sub.push_back(ret[row - 1][col - 1]
+ ret[row - 1][col]) ;//middle col
sub.push_back(1);//last col
ret.push_back(sub);
}
return ret;
}

细节

  1. 开始一定要判空,不然空容器会返回[1]的!!

  2. vector (1)写错,塞进去的是0,想塞1,这样写vector(1,1)

  3. 自己画图到第三层,row实际上是2,col<row就行了
  4. 各种数组越界。自己画图试试再写啊!

总结

  1. 第一种方法用的是resize,先已经分配了rows个容器了,这样性能不好,会初始化两次。
  2. 第二张方法是动态规划(迭代),用的push_back。
    1. 判空,返空。
    2. 开始初始化第一行,push_back(vector\(1,1))。这里一定要写两个参数,不然就只是定义了大小,默认初始化是0的。
    3. 再push_back,构造剩下的索引row为 1~(numrows-1),每行建个sub一维容器。
      1. sub第一个塞1。
      2. 从sub第二个开始,塞上层的和。解释一下,col<row,最好自己画图,因为row是num-1,而每行的size其实是row+1,最后一个不塞,所以要塞的最后一个索引是(row+1)-1-1,即row-1,所以是col<row。
      3. sub最后一个塞1。
Thanks for Support.