Given an index k, return the kth row of the Pascal‘s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
【思路】
我们为了满足空间复杂度的要求，我们新建两个ArrayList，一个负责存储上一个Pascal行的结果，一个根据上一个Pascal行得出当前Pascal行的结果，这个过程循环进行，代码如下：
1 public class Solution { 2 public List<Integer> getRow(int rowIndex) { 3 List<Integer> prelist = new ArrayList<>(); 4 prelist.add(1); 5 if(rowIndex <= 0) return prelist; 6 List<Integer> curlist = new ArrayList<>(); 7 for(int i = 1; i <= rowIndex; i++){ 8 curlist.add(1); 9 for(int j = 0; j < prelist.size() - 1; j++){ 10 curlist.add(prelist.get(j) + prelist.get(j+1)); 11 } 12 curlist.add(1); 13 List<Integer> temp = prelist; 14 prelist = curlist; 15 curlist = temp; 16 curlist.clear(); 17 } 18 return prelist; 19 } 20 }
LeetCode OJ 119. Pascal's Triangle II
原文：http://www.cnblogs.com/liujinhong/p/5512977.html