給定一個正整數(shù) n，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣。

示例:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/spiral-matrix-ii
著作權(quán)歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

思路

image.png

??根據(jù)循環(huán)不變原則，我們首先分析最外邊的那個圈，當分析完成一個圈之后，其余的圈可以根據(jù)for循環(huán)來完成，即按照同樣的規(guī)律進行處理。當分析某一個圈的時候，我們假設圈的左上角那個小正方形的坐標是(0,0)，且橫坐標使用i來表示，縱坐標使用j來表示。

??假設累加的數(shù)字為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;

如何為指向指針的指針分配內(nèi)存

其實，指向指針的指針這個概念和指針數(shù)組這個概念是類似的。也就是說，一個指針數(shù)組中有多個指針，其中的每個指針都指向一個一維的數(shù)組。
下面演示為該指針(指向指針的指針)分配內(nèi)存。

int **a = (int **)malloc(n * sizeof(int *));//首先為指針分配內(nèi)存
for(int i = 0;i<n;i++){//然后為指針指向的n個指針分配內(nèi)存。
    a[i] = (int *)malloc(n * sizeof(int));
}

代碼

??結(jié)合上面的分析，可以得出如下代碼。

/**
 * 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èi)圈進行分析，圈的個數(shù)總共有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是奇數(shù)時，會剩下最后一個中心點還沒有遍歷。
        arr[n/2][n/2] = sumC + 1;
    }
    return arr;
}

執(zhí)行結(jié)果

image.png