leetcode118：杨辉三角（pascals-triangle）

[carloscn]

问题描述：

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

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

示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2: 输入: numRows = 1 输出: [[1]]  

提示: 1 <= numRows <= 30

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/pascals-triangle

[carloscn]

分析：

由于C语言的特殊性，我们构建一个三角形结构体用来描述杨辉三角，内部包含一个二级指针的数组列表和一个数组深度，数组列表表示各层级三角形，数组深度既可以代表杨辉三角的深度，也可以代表每一层级的长度信息。

struct triangle_t {
    size_t depth;
    int64_t *array_list[30];
};

一个for循环用来创建数组，然后按照gif动画的规律创建数组即可。

static int32_t gen_pascals_triangle(struct triangle_t* triangle, size_t n)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;
    int64_t *new_array = NULL;

    if (n > 30 || 0 == n) {
        ret = -1;
        LOG("input error n is over the 30, or is 0.\n");
        goto finish;
    }

    UTILS_CHECK_PTR(triangle);
    triangle->depth = 0;

    for (i = 0; i < n; i ++) {
        new_array = NULL;
        new_array = (int64_t*)malloc(sizeof(int64_t) * (i + 1));
        UTILS_CHECK_PTR(new_array);

        new_array[0] = new_array[i] = 1;
        triangle->array_list[i] = new_array;
        triangle->depth ++;

        if (i < 2)
            continue;

        for (j = 1; j <= triangle->depth - 2; j ++) {
            new_array[j] = (triangle->array_list[i - 1])[j] + \
                           (triangle->array_list[i - 1])[j - 1];
        }
    }

finish:
    return ret;
}

最后不要忘了，还需要对数组创建的堆上的空间进行回收，否则会有内存泄漏。

static void free_triangle(struct triangle_t* triangle)
{
    size_t i = 0;

    if (NULL == triangle) {
        return;
    }

    for (i = 0; i < triangle->depth; i ++) {
        if (NULL != triangle->array_list[i])
            free(triangle->array_list[i]);
    }

    triangle->depth = 0;
}

[carloscn]

code：

https://github.com/carloscn/structstudy/blob/master/c_programming/array/14_pascals-triangle_118.c

result:

depth = 10

depth = 30

[carloscn]

知识积累

“杨辉三角”出现在杨辉编著的《详解九章算法》一书中。杨辉，杭州钱塘人，中国南宋末年数学家，数学教育家，著作甚多。他编著的数学书共五种二十一卷，著有《详解九章算法》十二卷（1261年）、《日用算法》二卷、《乘除通变本末》三卷、《田亩比类乘除算法》二卷、《续古摘奇算法》二卷。其中后三种合称《杨辉算法》，朝鲜、日本等国均有译本出版，流传世界。

数学家们曾研究过各种正整数在杨辉三角这个无限大的数阵中出现了多少次，奇怪的是数学家们找不到在杨辉三角出现的次数超过8的正整数。1971年，在杨辉三角中出现的次数都小于等于N。