力扣119.杨辉三角II-C语言实现

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

在这里插入图片描述

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

示例:

输入: 3
输出: [1,3,3,1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/pascals-triangle-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题

模板:

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* getRow(int rowIndex, int* returnSize){ }

答题:

对于本题杨辉三角的解决办法,可以通过对于元素的直接求出,比如题目要求的是第k层杨辉三角(至少两层处理三角,所以第二层又记为1).
比如求取第4层,我们需要的是第三层的数字进行一个加法运算得到,所以我们对于这个就可以递推到第一层,然后进行一个暴力的算法,我们求一个元素只需上一层的两个元素,,但是是一个不断推到上层的过程。所以循环必不可少,我们先进行一个基础的初始化:
1:首先对于层数的转换,第一层其实就是有两个元素了,后面都是层级的元素个数比层数多一个吗,所以我们可以得到:

*returnSize=rowIndex+1; //层级内的个数修正

我们需要返回的是第k层的数组,所以需要对这数组进行一个初始化:

int *row=malloc(sizeof(int)*(*returnSize)); //建立起指针(字节大小为于类型已指出) memset(row,0,sizeof(int)*(*returnSize)); //对于这个数组内填充满0 row[0]=1; //第一个元素始终是1

依据我们上面的分析很明显已经得知了怎样才能得到第k层,就是依次向下推进然后就可以得到。
建立按层数向下的循环:

for(int i=1;i<=rowIndex;++i){ }

满足内部一个向上推进的逻辑:

for (int j = i; j > 0; --j) { row[j] += row[j - 1]; }

最后综合可得:(题解超链接)

int* getRow(int rowIndex, int* returnSize) { *returnSize = rowIndex + 1; int* row = malloc(sizeof(int) * (*returnSize)); memset(row, 0, sizeof(int) * (*returnSize)); row[0] = 1; for (int i = 1; i <= rowIndex; ++i) { for (int j = i; j > 0; --j) { row[j] += row[j - 1]; } } return row }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsxxwz.html