Leetcode：Pascal's Triangle II

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?

Answer

原本想嘗試只用 *p = *(p-1) * (line - i)/i 來運算，但是送出之後往往卡在 Row = 30 這位置，而原因是 overflow … 所以我只好另外宣告一個 long long int 暫存值來規避測試時造成的 overflow 。

C

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

int* getRow(int rowIndex, int* returnSize）{
    int i, *p;
    long long int tmp;
    //修正
    rowIndex++;
    //宣告陣列所需記憶體
    p = (int*) malloc(rowIndex * sizeof(int));
    *p = 1;
    *(p+rowIndex-1) = 1;
    tmp = 1;
    for( i = 0 ; i < rowIndex ; i++ ){
        tmp = tmp * ( rowIndex - i ) / i ;
        *(p+i) = tmp;
    }
    return p;
}

Min:0ms
 _/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Python

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

class Solution(object):
    def getRow(self, rowIndex):
        x = [1]
        tmp = 1
        rowIndex += 1
        for i in range(1, rowIndex):
            tmp = tmp * (rowIndex - i ) / i
            x.append(tmp)
        return x

Min:36ms
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Javascript

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

var getRow = function(rowIndex){
    var x = [1], t = 1;
    rowIndex++;
    for(var i = 1; i < rowIndex; i++){
        t = t * (rowIndex * i) / i;
        x.push(t);
    }
    return x;
}

Min:112ms
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/