L24.【LeetCode笔记】杨辉三角

1.题目

2.分析

模拟二维数组的大致思想

杨辉三角的特点

二维数组的元素设置代码

两个参数returnSize和returnColumnSizes

理解"有效"的含义

完整代码

提交结果

1.题目

给定一个非负整数 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

2.分析

和在洛谷平台上(https://www.luogu.com.cn/problem/P5732)有所不同,LeetCode要求传一个二级指针回去

存储杨辉三角应该用二维数组,但是却不能在generate函数内初始化二维数组arr[m][n],因为返回后generate函数的栈帧空间会销毁,导致二维数组arr被销毁,返回的指针为野指针

因此必须用malloc,使用由二维数组的本质可知:需要使用指针数组来模拟二维数组

(二维数组复习:13.5.【C语言】二维数组)

模拟二维数组的大致思想

指针数组的每一个元素都指向杨辉三角每一行的第一个元素

可以用下图说明:设numRows==4

因此在malloc开辟时arr数组时,注意:开辟的空间==总行数*每个指针所占的内存空间

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

还要设计每行所占的空间,可以利用循环

    for (int i=0;i<numRows ;i++)
    {
        arr[i]=(int*)malloc(sizeof(int)*(i+1));
    }

arr为二级指针,arr[i]变为一级指针(行指针)

杨辉三角的特点

观察下图可知,每行的第一个和最后一个元素均为1

二维数组的元素设置代码

    for (int i=0;i<numRows ;i++)
    {
        arr[i][0]=arr[i][i]=1;
        for (int j=1;j<i;j++)
        {
            arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
        }
    }

注意:j从1开始循环,两个原因: ① 第一、二行不用执行arr[i][j]=arr[i-1][j-1]+arr[i-1][j] ② 每行的第一个元素已经提前被设置为1,从第二个元素开始设置

两个参数returnSize和returnColumnSizes

这两个参数是为了方便LeetCode检查的,LeetCode需要知道你开辟的二维数组有多少行(returnSize),每一行有多少个"有效"列(ColumnSizes),换句话说,每一行有多少个"有效"元素

理解"有效"的含义

由于LeetCode不会进行智能检查,因此需要明确告诉LeetCode的检查元素的范围("有效"的范围)

例如下图:第0行只有数字1,需要告诉LeetCode1后面的内存空间不需要检查,非有效的内存单元

则(*returnColumnSizes)[0]=1;

returnSize告知LeetCode杨辉三角的行数numRows,则*returnSize=numRows

完整代码

将上述分析的代码段组合起来

int**generate(int numRows, int* returnSize, int** returnColumnSizes)
{
    *returnSize = numRows;
    *returnColumnSizes=(int*)malloc(sizeof(int)*numRows);
    int**arr=(int**)malloc(sizeof(int*)*numRows);
    for (int i=0;i<numRows ;i++)
    {
        arr[i]=(int*)malloc(sizeof(int)*(i+1));
        (*returnColumnSizes)[i]=i+1;
        arr[i][0]=arr[i][i]=1;
        for (int j=1;j<i;j++)//j从1开始原因是每行的第一个元素被填充为1
        {
            arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
        }
    }
    return arr;
}