【题目概要】
118. Pascal's Triangle Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]【思路分析】
迭代生成的思想，1和2层是相对特殊的两层，作为基础可以生成3层后面的所有层，其中首元素和尾元素均为1，中间的数有以下规律（对应列的数n = 上一行的对应列数+上一行的掐前一列数）： nums[row][col] = nums[row-1][col-1] + nums[row-1][col]【代码示例1】
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** generate(int numRows, int* returnSize, int** returnColumnSizes){ int **re = (int**)malloc(sizeof(int*)*numRows); for(int row=0; row<numRows; row++) { int col = 1; re[row] = (int*)malloc(sizeof(int)*(row+1)); //首元素为1 re[row][0] = 1; for(col=1; col<row; col++) { re[row][col] = re[row-1][col-1] + re[row-1][col]; } //尾元素需要比较下是否是第一层和第二层，只有不小于2层，才能进去 if(col <= row) re[row][col] = 1; //每一层的列数等于行数的值，从1开始 (*returnColumnSizes)[row] = row+1; } *returnSize = numRows; return re; }【代码示例2】
[说明]本次是从后往前遍历和计算，示例1中是从前往后计算 int** generate(int numRows, int* returnSize, int** returnColumnSizes){ int **re = (int**)malloc(sizeof(int*)*numRows); for(int row=0; row<numRows; row++) { re[row] = (int*)malloc(sizeof(int)*(row+1)); re[row][row] = 1; // 针对每一行，将其前面的值补齐 for(int col=row-1; col>0; col--) { re[row][col] = re[row-1][col] + re[row-1][col-1]; } re[row][0] = 1; (*returnColumnSizes)[row] = row+1; } *returnSize = numRows; return re; }