Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return
Return
[1,3,3,1]
.
Note:
Could you optimize your algorithm to use only O(k) extra space?
Could you optimize your algorithm to use only O(k) extra space?
Solution 1: same idea as DP optimize the space. Note if iterate from end to start for each line will be easier as no need to record the pre element.
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res=new ArrayList<>();
for (int i=0; i<=rowIndex; i++) {
res.add(1);
for (int j=i-1; j>0; j--) {
res.set(j,res.get(j)+res.get(j-1));
}
}
return res;
}
}
没有评论:
发表评论