L24.【LeetCode条记】 杨辉三角

目录
1.题目
2.分析
模仿二维数组的大抵思想
杨辉三角的特点
二维数组的元素设置代码
 两个参数returnSize和returnColumnSizes
理解"有效"的含义
完备代码
提交效果

---

1.题目

   给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
  在「杨辉三角」中，每个数是它左上方和右上方的数的和。
  

  
  示例 1:

1. <strong>输入:</strong> numRows = 5
2. <strong>输出:</strong> [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

复制代码

示例 2:

1. <strong>输入:</strong> numRows = 1
2. <strong>输出:</strong> [[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数组时,留意:开发的空间==总行数*每个指针所占的内存空间

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

复制代码

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

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

复制代码

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

杨辉三角的特点

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

二维数组的元素设置代码

1.     for (int i=0;i<numRows ;i++)
2.     {
3.         arr[i][0]=arr[i][i]=1;
4.         for (int j=1;j<i;j++)
5.         {
6.             arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
7.         }
8.     }

复制代码

留意:j从1开始循环,两个缘故原由: ① 第一、二行不用执行arr[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

完备代码

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

1. int**generate(int numRows, int* returnSize, int** returnColumnSizes)
2. {
3.     *returnSize = numRows;
4.     *returnColumnSizes=(int*)malloc(sizeof(int)*numRows);
5.     int**arr=(int**)malloc(sizeof(int*)*numRows);
6.     for (int i=0;i<numRows ;i++)
7.     {
8.         arr[i]=(int*)malloc(sizeof(int)*(i+1));
9.         (*returnColumnSizes)[i]=i+1;
10.         arr[i][0]=arr[i][i]=1;
11.         for (int j=1;j<i;j++)//j从1开始原因是每行的第一个元素被填充为1
12.         {
13.             arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
14.         }
15.     }
16.     return arr;
17. }

复制代码

提交效果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。