59. 螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

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

思路

image.png

根据循环不变原则，我们首先分析最外边的那个圈，当分析完成一个圈之后，其余的圈可以根据for循环来完成，即按照同样的规律进行处理。当分析某一个圈的时候，我们假设圈的左上角那个小正方形的坐标是(0,0)，且横坐标使用i来表示，纵坐标使用j来表示。

假设累加的数字为sumC,假设圈的边长为n。

①首先分析上横边，从左向右滑动时，横坐标i=0不变，纵坐标j增加，所以，可以计算出sumC = j + 1;
②然后接着分析右竖边，从上往下滑动时，纵坐标j=(n-1)不变，横坐标i增加，所以，可以计算出sumC = n + i;
③接着分析下横边，从右向左滑动时，横坐标i=(n-1)不变，纵坐标j减小，所以，可以计算出sumC = 3*n -j -2;
④最后分析左竖边，从下向上滑动时，纵坐标j=0不变，横坐标i减小，所以，可以计算出sumC= 4*n -i - 3;

如何为指向指针的指针分配内存

其实，指向指针的指针这个概念和指针数组这个概念是类似的。也就是说，一个指针数组中有多个指针，其中的每个指针都指向一个一维的数组。
下面演示为该指针(指向指针的指针)分配内存。

int **a = (int **)malloc(n * sizeof(int *));//首先为指针分配内存
for(int i = 0;i<n;i++){//然后为指针指向的n个指针分配内存。
    a[i] = (int *)malloc(n * sizeof(int));
}

代码

结合上面的分析，可以得出如下代码。

/**
 * 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** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    *returnSize = n;
    *returnColumnSizes = (int *)malloc(n * sizeof(int));
    for(int i =0;i<n;i++){
        (*returnColumnSizes)[i] = n;
    }
    int **arr = (int **)malloc(n * sizeof(int *));
    for(int i = 0;i < n;i++){
        arr[i] = (int *)malloc(n * sizeof(int));
    }

    int sumC = 0;
    int n_inner = 0;
    for(int k = 0;k<n/2;k++){//从最外圈向最内圈进行分析，圈的个数总共有n/2个。
        n_inner = n - k * 2;//正在分析的这个圈的边长
        // if(n_inner == 1){
        //     arr[n/2][n/2] = sumC + 1;
        // }
        int i = 0,j = 0;
        while(j < n_inner - 1){//上横边
            arr[k][j + k] = j + 1 + sumC;
            j++;
        }
        while(i < n_inner - 1){//右竖边
            arr[i + k][j + k] = n_inner + i + sumC;
            i++;
        }
        while(j > 0){//下横边
            arr[i + k][j+k] = 3 * n_inner - j - 2 + sumC;
            j--;
        }
        while(i > 0){//左竖边
            arr[k + i][k] = 4 * n_inner -i - 3 + sumC;
            i--;
        }
        sumC = arr[k+1][k];//作为下个圈的积累和。
    }
    if(n%2==1){//当n是奇数时，会剩下最后一个中心点还没有遍历。
        arr[n/2][n/2] = sumC + 1;
    }
    return arr;
}

执行结果

image.png

最后编辑于：2020.11.07 11:21:03