LeetCode 118. Pascal's Trian

题目

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

image

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解析

使用C语言来解答此题主要是考察指针的使用，包括一维指针和二维指针，指针即是数组，也是数组的使用，要注意的是malloc在分配内存时指向。
另外，在解题过程中，我把第一行区分出来了，从第二行开始，对于第i行的第j个元素arr[i][j]，其中i不是第一个也不是最后一个，有
a[i][j] = a[i-1][j] + a[i-1][j-1]
这样便解决了杨辉三角的问题。

代码（C语言）

int** generate(int numRows, int** columnSizes) {
    if (numRows == 0) {
        (*columnSizes) = NULL;
        
        return NULL;
    }
    
    *columnSizes = (int*)malloc(sizeof(int) * numRows);
    int** returnArr = (int**)malloc(sizeof(int*) * numRows);
    
    for (int i = 0; i < numRows; ++i) {
        int curRowLen = i + 1;
        (*columnSizes)[i] = curRowLen;
        
        (*(returnArr + i)) = (int*)malloc(sizeof(int) * curRowLen);
        
        if (i == 0) {
            (*(returnArr + i))[0] = 1;
        } else {
            (*(returnArr + i))[0] = (*(returnArr + i))[curRowLen - 1] = 1;
            
            for (int j = 1; j < (curRowLen / 2 + curRowLen % 2); ++j) {
                (*(returnArr + i))[j] = (*(returnArr + i - 1))[j] +
                        (*(returnArr + i - 1))[j - 1];
                
                (*(returnArr + i))[curRowLen - 1 - j] = (*(returnArr + i))[j];
            }
        }
    }
    
    return returnArr;
}