118. Pascal's Triangle

  • 37.2%

https://leetcode.com/problems/pascals-triangle/

Given numRows, generate the first numRows of Pascal’s triangle.

1
2
3
4
5
6
7
8
9
10
For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

方法一:

我的代码实现:

October 17, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<vector<int>> generate(int numRows) {
if(numRows==0) return vector<vector<int>>();
vector<vector<int>> res(numRows, vector<int>(1, 1));
for(int i=2; i<=numRows; i++){
res[i-1].resize(i);
res[i-1][0] = res[i-1][i-1] = 1;
for(int j=0; j<i-2; j++)
res[i-1][j+1] = res[i-2][j] + res[i-2][j+1];
}
return res;
}
};

resize这个函数好用,同时想明白逻辑r[i][j] = r[i-1][j-1] + r[i-1][j],就可以实现了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> r(numRows);

for(int i = 0; i<numRows; i++){
r[i].resize(i+1);
r[i][0] = r[i][i] = 1;

for(int j=1; j<i; j++)
r[i][j] = r[i-1][j-1] + r[i-1][j];
}
return r;
}
};

2ms, 3.04%, June.21th, 2016

https://leetcode.com/discuss/20606/my-concise-solution-in-java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public List<List<Integer>> generate(int numRows)
{
List<List<Integer>> allrows = new ArrayList<List<Integer>>();
ArrayList<Integer> row = new ArrayList<Integer>();
for(int i=0;i<numRows;i++)
{
row.add(0, 1);
for(int j=1;j<row.size()-1;j++)
row.set(j, row.get(j)+row.get(j+1));
allrows.add(new ArrayList<Integer>(row));
}
return allrows;

}
}

0ms, 26.23%, June.21th, 2016

https://leetcode.com/discuss/13921/maybe-shortest-c-solution

resize这个函数好用,同时想明白逻辑r[i][j] = r[i-1][j-1] + r[i-1][j],就可以实现了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> r(numRows);

for(int i = 0; i<numRows; i++){
r[i].resize(i+1);
r[i][0] = r[i][i] = 1;

for(int j=1; j<i; j++)
r[i][j] = r[i-1][j-1] + r[i-1][j];
}
return r;
}
};

68ms, 9.44%, June.21th, 2016

https://leetcode.com/discuss/54525/python-4-lines-short-solution-using-map

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0:
return []
res = [[1]]
for i in range(1, numRows):
res += [map(lambda x, y:x+y, res[-1] + [0], [0] + res[-1])]
return res
谢谢你,可爱的朋友。