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)的額外空間嗎?

思路

不考慮只使用O(k)額外空間的情況下，只要參考LeetCode 118. Pascal's Triangle這題，就很簡單。

但上面的很像會超出時間，還是要用同一個陣列不斷改變裡面值的方式來做才行。毎一階的Pascal's三角形都可以重上一階算出，

計算方法，毎一階開頭一定是1，接下來位子n的數子為上一階陣列pAry[n-1] + pAry[n]

* ex. k = 4
* 第一階  array =    [1]
* 第二階  array =   [1,1]
* 第三階  array =  [1,2,1]
* 第四階  array = [1,3,3,1]

解題

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    if(rowIndex == 0) return [1];
    if(rowIndex == 1) return [1,1];

    var ary = [1];

    for(var i = 1 ; i <= rowIndex ; i++){
        // 儲存 ary[n-1]的數字
        var prev = ary[i-1];
        for(var j = 1 ; j < i ; j++ ){
            // preVrow[n]的數字，如果preVrow沒有n，設為0
            var cur = ary[j] ?　ary[j] : 0;

            // 目前row[n]的值為 "上一個prevRow[n-1] + prevRow[n]"
            ary[j] = prev + cur;

            prev = cur;
        }
        ary.push(1);
    }
    return ary;
};