数据结构习题–杨辉三角形(返回某一行)

输入需要第几行，返回杨辉三角形中的这一行
注意：这里的行数是从0开始

方法：递推(复杂度行数的平方)

分析：

当处于每行的第一个和最后一个时，添加的数为1
除此之外，每个数等于上一行的左边一个数(该数的索引减1)与右边一个数(该数的索引)之和

代码（方法一）

public List<Integer> getRow(int rowIndex) {List<List<Integer>> triangle = new ArrayList<>();for (int i = 0; i < rowIndex + 1; i++) {List<Integer> array = new ArrayList<>();for (int j = 0; j < i + 1; j++) {if (j == 0 || j == i){array.add(1);}else {array.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));}}triangle.add(array);}return triangle.get(rowIndex);}

代码(滚动数组优化)

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> list = new ArrayList<>();for(int i = 0; i <= rowIndex; i++){list.add(1);// 每次增加1for(int j = i-1; j>0; j--){// 逆序往前增加list.set(j,list.get(j-1)+list.get(j));}}return list;}
}

方法：线性递推

分析：

代码

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();row.add(1);for (int i = 1; i <= rowIndex; ++i) {row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));}return row;}
}