leetcode刷题日记:118.Pascal‘s Triangle(杨辉三角)

日记:118.Pascal‘s Triangle(杨辉三角)"/>

leetcode刷题日记:118.Pascal‘s Triangle(杨辉三角)

118.Pascal’s Triangle(杨辉三角）

题目给我们一个整数numRows表示杨辉三角形的行数，返回杨辉三角形的前numRows行，下面给出一个杨辉三角形看看它有哪些规律；


可以看出杨辉三角形的每一行的最左侧和最右侧的值都为1.

其余的第i行的第j个元素p[i][j]可以由下图确定：

可以看出p[i][j] = p[i-1][j]+p[i-1][j-1]，有了上述的思路我们可以写出代码如下：

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {int **p = (int **)malloc(sizeof(int **)*numRows);p[0] = (int *)malloc(sizeof(int*));p[0][0] = 1;*returnSize = numRows;*returnColumnSizes = (int *)malloc(sizeof(int)*numRows);(*returnColumnSizes)[0] = 1;for(int i=1; i<numRows;i++){(*returnColumnSizes)[i] = i+1;p[i] = (int *)malloc(sizeof(int)*(i+1));for(int j=0;j<=i;j++){if(j-1<0){p[i][j] = p[i-1][j]+0;}else if(j>i-1){p[i][j] = p[i-1][j-1]+0;}else{p[i][j] = p[i-1][j-1]+p[i-1][j];}}}return p;
}

运行结果截图：

119.Pascal’s Triangle II( 杨辉三角 II)

这道题要求返回杨辉三角形的第rowIndex行的值，杨辉三角形从第0行开始。有了上述的生成杨辉三角形的代码，我们只需要将杨辉三角的第i行的所有元素复制到x中，然后返回x即可,整体思路不变。

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

运行结果截图：

这一道题也可以采用我在杨辉三角这篇文章中的思路，因为根据二项式定理，可以求出杨辉三角形每一行的值。