Leetcode - 118. Pascal's Triangle

想法:

這題的 general 公式很簡單

就是對於 [i][j] 的數值 (i 為 row number, j 為 column number)

計算方式是將 [i-1][j-1] 和 [i-1][j] 的數值相加

然後每個 row 的第一個和最後一個都會是 1

但這題卡住我最久的是 pointer 的問題

這時候就要複習到 function 中的 call by pointer

returnSize 是一個 pointer，他指向一個 int 的空間

returnSize 的意思是回傳的二維 array 有幾個 array (也就是有幾個 row)

所以將 "returnSize 這個 pointer 所指向的空間的值" (*returnSize) 指定為 numRows 的值

returnColumnSizes 是一個 pointer，他指向一個 int pointer array 的空間

returnColumnSizes 的意思是每個 row 有幾個 column

所以將 "returnColumnSizes 這個 pointer 所指向的空間，並且加上 index，找到存放對應 row 的 column size 的空間" (*returnColumnSizes[i]) 指定為每個 column 的大小

pascal_array 是一個 pointer，他指向一個 int pointer array 的空間 (就是一個 2D array)

每次尋訪到新的 row 時，都要記得宣告新的空間

所以每次 loop 一開始

"pascal_array 這個 pointer 所指向的空間，並且加上 index，找到存放對應 row 的 data 的 array" (pascal_array[i])

都要新宣告一個對應 column size 的空間存放這些 int

Code:

/**

 * Return an array of arrays of size *returnSize.

 * The sizes of the arrays are returned as *returnColumnSizes array.

 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().

 */

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

    *returnColumnSizes = (int*)malloc(sizeof(int) * numRows);

    *returnSize = numRows;

    int **pascal_array = (int**)malloc(sizeof(int*) * numRows);

   

    int i, j;

    for(i = 0; i < numRows; i++){

        pascal_array[i] = (int*)malloc(sizeof(int) * (i+1));

       

        //column 0

        pascal_array[i][0] = 1;

       

        //column i

        pascal_array[i][i] = 1;

       

        //column 1 ~ column i - 1

        for(j = 1; j < i; j++){

            pascal_array[i][j] = pascal_array[i-1][j-1] + pascal_array[i-1][j];

        }

       

        //calculate size

        (*returnColumnSizes)[i] = i+1;

       

    }

   

    return pascal_array;

}