118. 杨辉三角

难度：简单

题目

给定一个非负整数numRows，生成杨辉三角的前numRows行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Reference

题解

基本思路： 根据杨辉三角的定义，通过递归逐行构造出每一行的值

代码如下：

/**
 * 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)
{
    *returnSize = numRows;
    if (numRows == 0)
        return NULL;
    if (numRows == 1)
    {
        *returnColumnSizes = (int *)malloc(sizeof(int));
        **returnColumnSizes = 1;
        int **ret = (int **)malloc(sizeof(int *));
        *ret = (int *)malloc(sizeof(int));
        **ret = 1;
        return ret;
    }
    int retSize = 0,
        *oldRetColSizes = NULL,
        **rec = generate(numRows - 1, &retSize, &oldRetColSizes), 
        i = 0;
        **ret = (int **)memcpy(malloc(sizeof(int *) * numRows), rec, (numRows - 1) * sizeof(int *));
        *newRetColSizes = memcpy((int *)malloc(sizeof(int) * numRows), oldRetColSizes, (numRows - 1) * sizeof(int));
        *tempArray = (int *)malloc(sizeof(int) * numRows);

    free(oldRetColSizes);
    free(rec);

    newRetColSizes[numRows - 1] = numRows;
    for (i = 1; i < numRows - 1; i++)
        tempArray[i] = *(ret[numRows - 2] + i) + *(ret[numRows - 2] + i - 1);
    tempArray[0] = 1;
    tempArray[numRows - 1] = 1;
    ret[numRows - 1] = tempArray;

    *returnColumnSizes = newRetColSizes;
    return ret;
}

评论