Day 26 - LeetCode 119. Pascal's Triangle II

LeetCode 119. Pascal's Triangle II

題目

Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3, Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?

翻譯

給一個指標k，回傳第k階的Pascal's三角形。
範例：
k=3，回傳[1,3,3,1]。
注意：你能改善演算法只用O(k)的額外空間嗎?

想法

跟LeetCode 118 差不多, 重點都是上一階的前一位數跟本位數相加

詳細參閱

公式算法
https://discuss.leetcode.com/topic/70081/a-math-solution-with-o-k-time-complexity-and-o-1-space

---

Code

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    
    let ans = [];

    for ( let i = 0; i <= rowIndex; i++ ) {
        for ( let j = 0; j <= i; j++ ) {
            if ( !ans[i] ) {
                ans[i] = new Array(j);
            }
            if ( j === 0 || j === i ) {
                ans[i][j] = 1;
            } else {
                //上一階的前位數＋本位數
                ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
            }
        }  
    }
    return ans[rowIndex];
}

Run