119. Pascal's Triangle II

  • 35.5%

https://leetcode.com/problems/pascals-triangle-ii/?tab=Description

Given an index k, return the kth row of the Pascal’s triangle.

1
2
For example, given k = 3,
Return [1,3,3,1].

Note:

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


方法一:

我的代码实现:

Oct 17, 2017

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

my code:

根据规则,同时从后向前加,就完成了。

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

java


3ms, 23.13%, June.21th, 2016

https://leetcode.com/discuss/40144/my-8-lines-java-solution-use-arraylist

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0;i<rowIndex+1;i++) {
res.add(1);
for(int j=i-1;j>0;j--) {
res.set(j, res.get(j-1)+res.get(j));
}
}
return res;
}
}

cpp


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

https://leetcode.com/discuss/8364/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> A(rowIndex+1, 0);
A[0] = 1;
for(int i=1; i<rowIndex+1; i++)
for(int j=i; j>=1; j--)
A[j] += A[j-1];
return A;
}
};

my code:

根据规则,同时从后向前加,就完成了。

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

python


Solution 1:

40ms, 94.22%, June.21th, 2016

https://leetcode.com/discuss/38977/very-simple-python-solution

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