求杨辉三角的第 k 行（时间复杂度为O（k））

119. 杨辉三角 II

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

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

以下时间复杂度为O（k）,空间复杂度O（1）。

示例:

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

分析：

杨辉三角的第n行其实就是（a+b）^n展开式的系数，而第i项展开式的系数为C（n,i）；

组合公式可得出C（n,i) = n! / (i! * (n-i)! )，即第i+1项是第i项的 (n-i)/(i+1)倍，根据这个规律我们可以推出第n行的每一项。

代码：

//组合公式C（n,i)=n!/(i!*(n-i)!)
//i+1项是第i项的(n-i)/(i+1)
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        long num = 1;
        for(int i=0; i<=rowIndex; i++){
            result.add((int)num);
            num = num*(rowIndex-i)/(i+1);
        }
        return result;
    }
}