59. 螺旋矩阵 II

难度：中等

题目

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

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

Reference

题解

按顺序填充矩阵，当超出矩阵或遇到已填充元素时转向。

/**
 * 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().
 */
void change(int direction, int *i, int *j, int incre)
{
    switch(direction)
    {
        case 0:
            *j += incre;
            break;
        case 1:
            *i += incre;
            break;
        case 2:
            *j -= incre;
            break;
        case 3:
            *i -= incre;
            break;
    }
}
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    *returnSize = n;
    *returnColumnSizes = (int *)malloc(sizeof(int) * n);

    int i = 0, j = 0, m = 1, direction = 0, **ret = (int **)malloc(sizeof(int *) * n);
    for (i = 0; i < n; i++)
    {
        (*returnColumnSizes)[i] = n;
        ret[i] = (int *)malloc(sizeof(int) * n);
        memset(ret[i], 0, sizeof(int) * n);
    }

    i = 0;
    while (m < n * n)
    {
        ret[i][j] = m;
        change(direction, &i, &j, 1);
        m++;
        if (i < 0 || j < 0 || i >= n || j >= n || ret[i][j])
        {
            change(direction, &i, &j, -1);
            direction = (direction + 1) & 3;
            m--;
        }
    }
    ret[i][j] = m;
    return ret;
}

评论