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?
思路：延续之前的思路。毕竟“抄”过一个Pascal's Triangle. 这个就会更得心应手一点哈哈。
public class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> pre= new ArrayList<Integer>(); pre.add(1); for(int i = 0; i < rowIndex; i++){ List<Integer> curr = new ArrayList<Integer>(); curr.add(1); if (pre.size() >=2){ for(int j = 1; j <= pre.size()-1; j++ ){ curr.add(pre.get(j-1) + pre.get(j)); } } curr.add(1); pre = curr; } return pre; } } 方法二：实现了extra space的要求 虽然我不明白为什么我用了两个arraylist就不符合额外空间O(k)的要求了。毕竟我觉得O(k)是可以用两个k长度的数组的。 但是这个方法毕竟更好一些。 比如由1，3，3，1 生成 1，4，6，4，1的时候。其实不太需要额外的空间。 只是将1，3，3，1这个数组改变一下就可以了。改变的方法：首先，1，3，3，1是四位的，而要生成的比它多一位，也就是最后一位的1.所以不考虑长度的变化，我们直接在1，3，3，1上面改变即可。1，3，3，1 1，4，6，4，1
竖直对应起来看一下，那么每一位都是它和它前一位数字的和。所以需要从后向前修改。先改最后的1，变为4.毕竟这一位1是没有用处的。
public class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> res = new ArrayList<Integer>(); if(rowIndex < 0) return res; res.add(1); for(int i = 1; i <= rowIndex; i++){ for(int j = res.size() - 2; j>=0; j--){ res.set(j+1, res.get(j) + res.get(j+1)); } res.add(1); } return res; } } 今天好像才刷了三四道。我这个效率低到令人发指。不知道刷完easy之后，每天5道medium的话，是什么情景。我好饿。。。
