题目描述

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 在杨辉三角中，每个数是它左上方和右上方的数的和。

1. 示例: 输入: 3 输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

解题思路

思路一：其实有一定排列组合数学基础的会发现，第i行（i从0开始）第j个元素的值其实就为 C i j C^j_i Cij，但是排列组合会涉及到阶乘，因此会超过long数据类型的范围，不可取。 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- 思路二：既然杨辉三角的当前行涉及到上一行的两两数值和，因此：

采用双循环，外层循环外先把第一个1先放入，

在外层循环中在数组末尾添加一个0（意思是行数+1，数组的容量也+1，至于为什么添加一个0，是因为内循环要涉及到加法，这里的加法需从0开始），

在内层循环中，从末尾新添加的数字0开始，把当前值和前一个值之和作为当前值的新值，直到循环至第1个数为止（这里的1是下标1，下标从0开始），因为第0个数总为1，不会变。

代码详解

思路二代码

class Solution {
          
   
    public List<Integer> getRow(int rowIndex) {
          
   
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1); // 外层循环外添加最开头的1，如果rowIndex = 0，则直接返回[1]
        for(int i = 1; i <= rowIndex; ++i) {
          
   
            list.add(0); // 运行至此处说明层数+1了
            for(int j = i; j > 0; --j) {
          
   
                list.set(j, list.get(j) + list.get(j-1)); // 当前值 = 当前值 + 前一个位置的值
            }
        }
        return list;
    }
}

注意点

1. 思路一是纯数学思路，但数值一大便会超出int甚至long类型的范围，导致计算出错。
2. 思路二是把第118题逐层展示的杨辉三角块，转换成在一个数组里不断进行更新的形式。不过我在118题的题解中没有使用这种更加巧妙的方法。我太菜了。