杨辉三角II

题目

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

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

示例:

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

进阶：

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

思路

• 简单版本可以构建杨辉三角,之后取前一行进行相加得到索引一行
• 数学公式版本

代码

• 简单版本

    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        result.add(1);
        List<Integer> preList = new ArrayList<>();
        if(rowIndex == 0){
            return result;
        }
        preList.add(1);
        for(int i = 1;i < rowIndex;i++){
            List<Integer> temp = new ArrayList<>();
            temp.add(1);
            for(int j = 1;j < i;j++){
                temp.add(preList.get(j) + preList.get(j-1));
            }
            temp.add(1);
            preList = temp;
        }
        for(int i = 1;i < preList.size();i++){
            result.add(preList.get(i) + preList.get(i-1));
        }
        result.add(1);
        return result;
    }

• 数学公式版本

public static List<Integer> tGetRow(int rowIndex)
    {
        rowIndex++;   //从0开始
        List<Integer> res = new ArrayList<Integer>();
        res.add(1);
        long tem = 1;
        for (int i = 1; i < rowIndex; i++)
        {
            tem = tem * (rowIndex - i) / i;
            res.add((int)tem);
        }
        return res;
    }