杨辉三角118-力扣（二维数组+c）

迷南。 2023-01-16 03:26 113阅读 0赞

题目描述  
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5  
输出:  
\[  
\[1\],  
\[1,1\],  
\[1,2,1\],  
\[1,3,3,1\],  
\[1,4,6,4,1\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/pascals-triangle  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解  
分析：这道题目，思路比较容易想到，每一行的起点和末尾都是1，中间的某个值为：上一行的正上方以及左上方的加和。

这道题目需要掌握的地方是如何去动态申请列数不同的二维数组，这部分主要考察的就是对c语言中二维数组的理解，c中的二维数组的创建，是通过将多个一维数组的指针，放到一个一维的指针数组中，然后构建二维数组的，最终用一个指针指向这个一维的指针数组即可。

/** * 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){ 
        *returnSize = numRows;
        
        int **res = malloc(sizeof(int*) * numRows);
        int *a = (int* )malloc(sizeof(int) * numRows);
        *returnColumnSizes = a;
    
        for(int i=0; i<numRows; i++)
        { 
            res[i] = (int*)malloc(sizeof(int) * (i+1));
            (*returnColumnSizes)[i] = i+1;
            res[i][0] = 1;
            res[i][i] = 1;
            for(int j=1; j<i; j++)
            { 
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        }
        return res;
    
    }

--------------------

思考的一个问题：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
p是动态开辟内存返回的指针，为什么使用returnColumnSizes = &p有问题，而使用 \*returnColumnSizes = p没问题？

上面这个问题的答案：  
**要在函数内部改变参数的值，只能通过指针间接操作**，简单解释一下，传入函数的指针参数，实际上已经在主函数里面指向了某个变量，通过这个指针参数去对主函数中的变量进行操作，如果在函数体内直接改变了指针的指向，那么主函数中对应的变量在进行后面的操作的时候就会出现错误。

一定要理解力扣的编程规则，时刻注意我们写的是一个函数。

--------------------

我问了好几个人，最近也得到一些答复，发现好多人没注意这一点，补充解释一下：

力扣之所以使用指针传参，是为了返回改变后的行数和列数，而c无法返回多个值，因此只有通过指针操作改变变量的值进而得到改变后的行数和列数，对于简单变量，使用一级指针指向该变量，对于一维数组，使用二级指针指向该一维数组。很显然，此处returnColumnSizes是指向的存放二维数组每行的列数的一维数组。

而要想测试该函数，首先在main中要做的就是令returnColumnSizes指向一个一级指针，后面通过函数对一级指针中的值进行改变，然后进行后续验证的操作。如果我在函数体内直接改变returnColumnSizes的指向，并不会改变一级指针的内容，所以后续使用该一级指针进行操作验证的时候，此时一级指针中的内容是垃圾值，就会出现错误。

所以我在函数内直接改变二级指针的指向，导致main中后续验证出现了错误，而使用\*returnColumnSizes间接对指针操作，修改的是一级指针的内容，所以后续验证就不会出错了。

若完全不顾及力扣的这种测试方式，两种方式都可以编译通过的，因为两种方式都不是错误语句，而且效果也是相同的，只不过一种是直接操作，一种是间接操作。

代码验证：

#include <stdio.h>
    #include <stdlib.h>
    
    int** ggenerate(int numRows, int* returnSize, int** returnColumnSizes){ 
        *returnSize = numRows;
    
        int **res =(int **)malloc(sizeof(int*) * numRows);
        int *a = (int* )malloc(sizeof(int) * numRows);
        *returnColumnSizes = a; // *returnColumnSizes表示一级指针，令一级指针指向a
    
        for(int i=0; i<numRows; i++)
        { 
            res[i] = (int*)malloc(sizeof(int) * (i+1));
            (*returnColumnSizes)[i] = i+1;
            res[i][0] = 1;
            res[i][i] = 1;
            for(int j=1; j<i; j++)
            { 
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        }
        return res;
    
    }
    
    int main() { 
    
         int rowsize; //保存行数的变量
         int *columnSize; //保存列数的一维数组的指针
    
         int *returnSize = &rowsize; //用一个一级指针指向行数的变量
         int **returnColumnSizes;  // 定义一个二级指针
         returnColumnSizes = &columnSize;  // 令该二级指针指向保存列数的一维数组的一级指针
    
         int **res = ggenerate(5, returnSize, returnColumnSizes); //调用函数
    
    	 //输出验证，利用rowsize与columnSize
         for(int i=0; i<rowsize; i++)
         { 
              for(int j=0; j<columnSize[i]; j++)
              { 
                   printf("%d ", res[i][j]);
              }
              printf("\n");
         }
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]

#include <stdio.h>
    #include <stdlib.h>
    
    int** ggenerate(int numRows, int* returnSize, int** returnColumnSizes){ 
        *returnSize = numRows;
    
        int **res =(int **)malloc(sizeof(int*) * numRows);
        int *a = (int* )malloc(sizeof(int) * numRows);
        returnColumnSizes = &a; //改变二级指针的指向，一级指针的指向没有改变
    
        for(int i=0; i<numRows; i++)
        { 
            res[i] = (int*)malloc(sizeof(int) * (i+1));
            (*returnColumnSizes)[i] = i+1;
            res[i][0] = 1;
            res[i][i] = 1;
            for(int j=1; j<i; j++)
            { 
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        }
        return res;
    
    }
    
    int main() { 
    
         int rowsize; //保存行数的变量
         int *columnSize; //保存列数的一维数组的指针
    
         int *returnSize = &rowsize; //用一个一级指针指向行数的变量
         int **returnColumnSizes;  // 定义一个二级指针
         returnColumnSizes = &columnSize;  // 令该二级指针指向保存列数的一维数组的一级指针
    
         int **res = ggenerate(5, returnSize, returnColumnSizes); //调用函数
    
    	 //输出验证，利用rowsize与columnSize
         for(int i=0; i<rowsize; i++)
         { 
              for(int j=0; j<columnSize[i]; j++)
              { 
                   printf("%d ", res[i][j]);
              }
              printf("\n");
         }
    }

运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]  
为进一步证明，不考虑力扣的验证的方式，直接以上帝视角，在知道返回的数组的行数和列数的条件下，输出看看得到的结果是否是正确的：

#include <stdio.h>
    #include <stdlib.h>
    
    int** ggenerate(int numRows, int* returnSize, int** returnColumnSizes){ 
        *returnSize = numRows;
    
        int **res =(int **)malloc(sizeof(int*) * numRows);
        int *a = (int* )malloc(sizeof(int) * numRows);
        returnColumnSizes = &a;
    
        for(int i=0; i<numRows; i++)
        { 
            res[i] = (int*)malloc(sizeof(int) * (i+1));
            (*returnColumnSizes)[i] = i+1;
            res[i][0] = 1;
            res[i][i] = 1;
            for(int j=1; j<i; j++)
            { 
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
    
        }
        return res;
    
    }
    
    int main() { 
    
         int rowsize;
         int *columnSize;
    
         int *returnSize = &rowsize;
         int **returnColumnSizes;
         returnColumnSizes = &columnSize;
    
         int **res = ggenerate(5, returnSize, returnColumnSizes);
    	//在知道返回的数组的行数和列数，进行输出
         for(int i=0; i<5; i++)
         { 
              for(int j=0; j<=i; j++)
              { 
                   printf("%d ", res[i][j]);
              }
              printf("\n");
         }
         printf("\n");
    	 //也对列数打印一下，看看是否修改成功
         for(int i = 0; i < 5; i++)
         { 
              printf("%d ", columnSize[i]);
         }
    
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]  
很明显可以看到，结果是正确的，而用来保存数组列数的指针中的内容是垃圾值。所以证明了上面的解释。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20221022/fe8ec33e4b3d42379c7f79678d56f089.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: /images/20221022/d4938c3a0699410b955b7bb63f8fdab1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]: /images/20221022/af5ee23abde343288e236b9f051e1b81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]: /images/20221022/2f434f96fba64147a19ae96c77c7e3fc.png