题目
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
leetcode-题图.gif示例1:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
解析:
动态规划法,根据每上一层的值,得到当前行对应的值 [i][j] = [i-1][j-1] + [i-1][j]
- 第一层循环控制行数i : 默认[i][0] = 1,[i][i] = 1
- 第二层循环控制列数j : triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
复杂度分析:
时间复杂度:
空间复杂度:
代码
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
if (numRows == 0) {
returnSize[0] = 0;
returnColumnSizes[0] = NULL;
return NULL;
}
int **res = (int **)malloc(sizeof(int *) * numRows);
res[0] = (int *)malloc(sizeof(int));
res[0][0] = 1;
returnColumnSizes[0] = (int *)malloc(sizeof(int) * numRows);
returnColumnSizes[0][0] = 1;
returnSize[0] = numRows;
for (int i = 1; i < numRows; ++i) {
res[i] = (int *)malloc(sizeof(int) * (i + 1));
res[i][0] = res[i][i] = 1;
returnColumnSizes[0][i] = i + 1;
for (int j = 1; j < i; ++j) {
res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
return res;
}
网友评论