1.没有什么特殊的地方完整代码如下1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. int** generate(int numRows, int* returnSize, int** returnColumnSizes) { 7. // 外层二维数组存放每一行一维数组指针 8. int** res (int**)malloc(sizeof(int*) * numRows); 9. // 记录每一行长度的数组 10. *returnColumnSizes (int*)malloc(sizeof(int) * numRows); 11. 12. for (int i 0; i numRows; i){ 13. int rowLen i 1; 14. int* tmp (int*)malloc(sizeof(int) * rowLen); 15. for (int j 0; j i; j){ 16. // 左右边界直接赋值1 17. if (j 0 || j i){ 18. tmp[j] 1; 19. continue; 20. } 21. // 中间值 上一行左上 上一行正上方 22. tmp[j] res[i - 1][j - 1] res[i - 1][j]; 23. } 24. res[i] tmp; 25. (*returnColumnSizes)[i] rowLen; 26. } 27. 28. *returnSize numRows; 29. return res; 30. }该算法时间复杂度为O(n2)空间复杂度为O(1)。2.可以利用杨辉三角的对称性来进一步简化代码1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. int** generate(int numRows, int* returnSize, int** returnColumnSizes) { 7. // 分配外层指针数组存储每一行一维数组地址 8. int** res (int**)malloc(sizeof(int*) * numRows); 9. // 分配记录每行长度的数组 10. *returnColumnSizes (int*)malloc(sizeof(int) * numRows); 11. 12. for (int i 0; i numRows; i){ 13. int rowLen i 1; 14. // 为第i行分配内存 15. res[i] (int*)malloc(sizeof(int) * rowLen); 16. // 杨辉三角每行首尾固定为1避免未初始化脏数据 17. res[i][0] 1; 18. res[i][i] 1; 19. 20. // 利用对称性只计算左半边右半边直接镜像赋值减少一半计算量 21. for (int j 1; j i / 2; j){ 22. // 当前值 上一行左上 上一行正上方 23. res[i][j] res[i - 1][j - 1] res[i - 1][j]; 24. // 对称位置复制当前值 25. res[i][i - j] res[i][j]; 26. } 27. // 记录当前行的元素个数 28. (*returnColumnSizes)[i] rowLen; 29. } 30. 31. // 外层数组总长度 32. *returnSize numRows; 33. return res; 34. }该算法时间复杂度为O(n2)空间复杂度为O(1)。
