题目

给定一个非负索引 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

}

巴特西

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

题目

解题

最新文章

热门文章