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.
In Pascal‘s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3 Output: [1,3,3,1]
Follow up:
Could you optimize your algorithm to use only O(k) extra space?
class Solution:
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
start = ans = [1]
for i in xrange(0, rowIndex):
ans = start + [1]
for j in xrange(1, len(ans)-1):
ans[j] = start[j]+start[j-1]
start = ans
return ans
还可以少一个临时变量，从后向前计算相加：
class Solution:
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
ans = [1]
for i in xrange(0, rowIndex):
ans = ans + [1]
for j in xrange(len(ans)-2, 0, -1):
ans[j] = ans[j]+ans[j-1]
return ans
也有使用dummy变量的做法：
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
row = [1]
for _ in range(rowIndex):
row = [x + y for x, y in zip([0]+row, row+[0])]
return row
另外就是数学解法，没有懂，TODO：
class Solution {
public:
vector<int> getRow(int k) {
vector<int> ans(k+1,1);
for(int i=1;i<=k/2;++i){
ans[k-i]= ans[i]=long(ans[i-1])*(k-i+1)/i;
}
return ans;
}
};
leetcode 119. Pascal's Triangle II
原文：https://www.cnblogs.com/bonelee/p/9180711.html