Leetcode：Pascal's triangle

Pascal's triangle 

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Answer 

原本想用 push 直接推送陣列到空白的一維陣列，但是久試的結果就是上層的推送也會因為下層推送而改變，因此只能追尋土法煉鋼的精神，先宣告陣列長，再分別宣告陣列寬，慢慢填入數字。

Javascript 

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

var generate = function(numRows){
    //宣告陣列長
    var x = new Array();
    for( var i = 0; i < numRows; i++){
        //宣告各陣列寬
        var x[i] = new Array();
        for( var j = 0; j <= i; j++ ){
            //判斷是否為頭尾，否則取上層相加
            ( j === 0 || j === i ) ? x[i][j] = 1 : x[i][j] = x[i-1][j] + x[i-1][j-1];
        }
    }
    return x;
}

Min:120ms 
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/ 

為了節省迴圈時不斷判斷是否為最初和最末值時間，於是直接將判斷提出迴圈外。

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

var generate = function(numRows){
    //宣告陣列長
    var x = new Array();
    for( var i = 0; i < numRows; i++){
        //宣告各陣列寬
        var x[i] = new Array();
        x[i][i]=1;
        x[i][0]=1;
        for( var j = 0; j <= i; j++ ){
            //取上層相加
            x[i][j] = x[i-1][j] + x[i-1][j-1];
        }
    }
    return x;
}

Min:116ms
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

對此我也依樣畫葫蘆嘗試用 python

Python 

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

class Solution(object):
    def generate(self, numRows):
        if numRows == 0:
            return []
        x=[[1]]
        if numRows == 1:
            return x
        for i in range(1, numRows):
            x.append([])
            x[i].append(1)
            for j in range(1, i):
                x[i].append(x[i][j-1] * (i+1-j) / j )
            x[i].append(1)
        return x

Min:40ms 
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

class Solution(object):
    def generate(self, numRows):
        if numRows == 0:
            return []
        x=[[1]]
        if numRows == 1:
            return x
        for I in range(1, numRows):
            x.append([])
            x[i].append(1)
            for j in range(1, i):
                x[i].append(x[i-1][j] + x[i-1][j])
            x[i].append(1)
        return x

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

而在C上面就遇到了一些麻煩，C語言裡面沒有所謂的動態陣列，只能動態分配記憶體，於是學習了使用指標和 malloc() 函數來動態分配所需要的記憶體，而因為儲存內容是 int ，所以每個資料的記憶體大小為 sizeof(int)。

C 

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

int** generate(int numRows, int** columnSizes, int* returnSize) {

    *returnSize = numRows;
    int **p, i, j;

    //設定X軸記憶體
    p = (int**) malloc( numRows * sizeof(int*) );
    *columnSizes = (int*) malloc( numRows * sizeof(int) );
    for( i = 0 ; i < numRows ; i++){
        //設定Y軸記憶體
        p[i] = (int*) malloc( (i + 1) * sizeof(int) );
        p[i][0] = p[i][i] = 1;
        (*columnSizes)[i] = i+1;
        if (numRows >= 2){
            for(j = 1 ; j < i ; j++){
                //設定Y軸各值
                p[i][j] = p[i-1][j-1] + p[i-1][j];
            }
        }
    }
    return p;
}

Min:0ms