LeetCode解题记录（九）

数组篇 （简单）九
119 杨辉三角(2)
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

这题与八几乎雷同，唯一的区别在于要求更低了，不需要返回三角的所有数组，只要返回最底层的数组即可。原本按照上题解法也可解决这题，但题目更简洁后，对时间复杂度的要求也更高了，原题解法超时，只得另寻他法。
题解运用递归思想，创建两个List，一个用来保存上一层的数组，另一个用于保存本层数组。首先先得到第0层数组（1），之后
逐层向上。举个例子，如果输入的数字是3，那么这个三角则有0,1,2,3共计四层。由3向上层层递归，回到2，2再向上至1,1向上至0,0直接返回数组（1），之后可得到1对应数组（1,1），1返回后得到2，最后得到3对应数组。从2开始for循环发挥作用，向上一层的数组相加得到下一层结果。
解：

class Solution {
   public List<Integer> getRow(int rowIndex) {
	List<Integer> list = new ArrayList<Integer>();
	List<Integer> ret = new ArrayList<Integer>();
	if(rowIndex == 0){
		ret.add(1);
		return ret;
	}  
	list = getRow(rowIndex-1);//上行list
	ret.add(1);
	for(int i = 0; i < rowIndex-1; i++)
	{
		ret.add(list.get(i) + list.get(i+1));
	}
	ret.add(1);
	return ret;
}
}