119. Pascal's Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3 Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

 

解题思路：

/* 执行用时 : 4 ms, 在Pascal's Triangle II的C提交中击败了98.97% 的用户 内存消耗 : 7.1 MB, 在Pascal's Triangle II的C提交中击败了6.10% 的用户 */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* getRow(int rowIndex, int* returnSize){ //给返回数组分配空间 int * result = (int *)malloc((rowIndex+1)*sizeof(int)); int i = 0,j = 0,pre = 1; //进行rowIndex+1次，因为rowIndex是索引 for(i = 0;i<=rowIndex;i++){ result[0] = result[i] = 1;//将第一个和最后一个置为1 pre = 1;//保存前一层此位置的值，因为会被覆盖 for(j = 1;j<=i/2;j++){//利用对称性质 result[j] = pre + result[j];//更新j位置的值 pre = result[j] - pre;//前一层j位置的值 result[i-j] = result[j]; } }//for *returnSize = rowIndex+1;//应返回rowIndex+1,不然最后一个不会有输出。 return result; } /* 输入 3 输出 [1,3,3] 预期结果 [1,3,3,1] 错误在于返回数组大小为rowIndex，由于rowIndex是索引，所以实际大小要加1 */

改进：从后向前更新数组。如此可以不用设置pre来保存值；算法实现更加简单，空间复杂度将降低。

后记:

注意rowIndex为索引，返回的数组大小以及设置循环条件时需要加1由于前一个元素要被后一个运用，但每次更新都会覆盖掉上一层此位置的值，所以需要设置变量pre保存。利用好对称性，可以简化代码

LeetCode 118. Pascal's Triangle(杨辉三角) -- c语言

链接：https://blog.csdn.net/d_benhua/article/details/90417386