本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。


在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路分析

杨辉三角，是二项式系数在三角形中的一种几何排列,是智慧的结晶！
杨辉三角是经典的题目，而且有总结好的计算公式，熟记公式可以节省大量的时间和空间复杂度。
对于公式不熟悉的话，可以动态计算，因为杨辉三角的第i行只与第i-1行计算有关，因此可以用这个特性，保存pre和current,可以节省计算空间。

代码

public class DayCode {
    public static void main(String[] args) {
        int k = 33;
        List<Integer> ans = new DayCode().getRow(k);
        System.out.println("ans is " + ans);
    }

    /**
     * 常规思路，枚举杨辉三角每一行
     * https://leetcode-cn.com/problems/pascals-triangle-ii/
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            current = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    current.add(1);
                } else {
                    current.add(pre.get(j-1) + pre.get(j));
                }
            }
            pre = current;
        }
        return current;
    }
}
复制代码

常规思路枚举杨辉三角，不是最优解。
下面的代码是利用数学公式解决，时间复杂度和空间复杂度更优！

public class DayCode {
    public static void main(String[] args) {
        int k = 33;
        List<Integer> ans = new DayCode().getRow(k);
        System.out.println("ans is " + ans);
    }
    
    /**
     * https://leetcode-cn.com/problems/pascals-triangle-ii/
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>();
        ans.add(1);
        for (int i = 1;i <= rowIndex; i++) {
            ans.add((int) ((long) ans.get(i - 1) * (rowIndex - i + 1) / i));
        }
        return ans;
    }
}
复制代码