美文网首页
119. Pascal's Triangle II

119. Pascal's Triangle II

作者: Icytail | 来源:发表于2017-11-18 03:49 被阅读0次

    Description:

    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?

    My code:

    /**
     * @param {number} rowIndex
     * @return {number[]}
     */
    var getRow = function(rowIndex) {
        //第 n 行的第  k 个数字为组合数 C (k - 1)/(n - 1)
        var getFactorial = function(num) { // 求阶乘
            let factorial = 1;
            for(let i = 1; i <= num; i++) {
                factorial *= i;
            }
            return factorial;
        };
        var arr = [];
        for(let i = 0; i <= rowIndex; i++) {
            if(i == 0 || i == rowIndex) {
                arr.push(1);
            } else {
                arr.push(getFactorial(rowIndex) / (getFactorial(i) * getFactorial(rowIndex - i)));
            }
        }
        return arr;
    };
    

    Note: 题目说有没有办法优化到空间复杂度为O(k),暂时还没想到……

    相关文章

      网友评论

          本文标题:119. Pascal's Triangle II

          本文链接:https://www.haomeiwen.com/subject/vmosvxtx.html