119. Pascal's Triangle II

Leetcode link

解题思路

• TC: O(n)
• SC: O(n)

这是一道简单题，只要求我们求得 Pascal's triangle 中的某一行的所有数字 这道题有挑战的点在于题目要求我们只能使用 O(rowIndex) 的空间，也就是说，我们应该直接计算出对应的行，而非把整个三角形都算出来

有了这个思路之后我们还需要三个信息：

1. Pascal's triangle 的第 n 行第 r 个值可以用 $\tbinom{n}{r}$ 来表示（其中 n 跟 r 都是 0-index 的）
2. 承上，$\tbinom{n}{r + 1} = \tbinom{n}{r} \times \frac{n-r}{r+1}$ （具体推导过程省略，可以用组合数公式自己算一下就有了）
3. 每一行的第一个数都是 1

综合上述三个信息，我们就可以直接计算出任意一行的 Pascal's triangle 了，具体代码如下

Javascript

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    const res = [1];
    for(let i=0;i<rowIndex;i++) {
        let num = res[i];
        num *= rowIndex - i;
        num /= i + 1;
        res.push(num);
    }
    // console.log('res', res);
    return res;
};