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

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

输入需要第几行，返回杨辉三角形中的这一行
注意：这里的行数是从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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码(滚动数组优化)

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++){
            list.add(1);
            // 每次增加1
            for(int j = i-1; j>0; j--){
            // 逆序往前增加
                list.set(j,list.get(j-1)+list.get(j));
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法：线性递推

分析：

代码

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;
    }
}
1
2
3
4
5
6
7
8
9
10