LeetCode 54.螺旋矩阵 59.螺旋矩阵II

题目

54.螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

54.螺旋矩阵

59.螺旋矩阵II

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

54.螺旋矩阵

这两道思路、算法一致，所以放在一起说。

题目分析

54.螺旋矩阵

题目要求我们顺时针遍历一个二维数组，所谓顺时针遍历，就是先从左到右，直到遇到边界，然后从上到下；接着从右到左；最后从下到上的遍历数组。

以[[1,2,3],[4,5,6],[7,8,9]]为例，先从左到右，1,2,3；然后从上到下,6,9，然后从右到左，8,7，然后从下到上，4；数组还没有遍历完，接着循环上述步骤，从左到右,5。数组遍历完成，最终的序列是1,2,3,6,9,8,7,4,5。

由于我们采取上面的方式遍历，所以我们需要四个索引值，分别代表左、右、上、下的边界。

令四个索引的初值为:l = 0,r = row - 1, t = 0, b = col - 1。

因此，遍历这个二维数组的过程为：

*returnSize = 0;
while (true){
    // 从左到右
    for (int i = l; i <= r; i++) res[(*returnSize)++] = matrix[t][i];
    if (++t > b) break;
    // 从上到下
    for (int i = t; i <= b; i++) res[(*returnSize)++] = matrix[i][r];
    if (l > --r) break;
    // 从右到左
    for (int i = r; i >= l; i--) res[(*returnSize)++] = matrix[b][i];
    if (t > --b) break;
    // 从下到上
    for (int i = b; i >= t; i--) res[(*returnSize)++] = matrix[i][l];
    if (++l > r) break;
}

完整的解答见最后。

59.螺旋矩阵II

有了上一道题的基础，这一道题就易如反掌了，只要按照上面的方式遍历，设置一个初值为1的计数器，随着遍历的过程自增，插入数组中，即可。

int count = 1;
while (count <= n * n){
    for (int i = l; i <= r; i++) res[t][i] = count++;
    if (++t > b) break;

    for (int i = t; i <= b; i++) res[i][r] = count++;
    if (l > --r) break;

    for (int i = r; i >= l; i--) res[b][i] = count++;
    if (t > --b) break;

    for (int i = b; i >= t; i--) res[i][l] = count++;
    if (++l > r) break;
}

完整的解答见最后。

题目示例

54.螺旋矩阵

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    *returnSize = 0;
    if (matrixSize == 0) return 0;

    int* res = (int*)calloc(matrixSize * matrixColSize[0], sizeof(int));

    int l, r, t, b;
    l = 0, t = 0;
    r = matrixColSize[0] - 1;
    b = matrixSize - 1;
    while (true){
        // 从左到右
        for (int i = l; i <= r; i++) res[(*returnSize)++] = matrix[t][i];
        if (++t > b) break;
        // 从上到下
        for (int i = t; i <= b; i++) res[(*returnSize)++] = matrix[i][r];
        if (l > --r) break;
        // 从右到左
        for (int i = r; i >= l; i--) res[(*returnSize)++] = matrix[b][i];
        if (t > --b) break;
        // 从下到上
        for (int i = b; i >= t; i--) res[(*returnSize)++] = matrix[i][l];
        if (++l > r) break;
    }
    return res;
}

59.螺旋矩阵II

nt** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if (n == 0) return 0;

    *returnColumnSizes = (int*)malloc(sizeof(int)*n);

    int** res = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++){
        res[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }

    int count = 1;
    int l, r, t, b;
    l = 0, t = 0;
    r = n - 1, b = n - 1;

    while (count <= n * n){
        for (int i = l; i <= r; i++) res[t][i] = count++;
        if (++t > b) break;

        for (int i = t; i <= b; i++) res[i][r] = count++;
        if (l > --r) break;

        for (int i = r; i >= l; i--) res[b][i] = count++;
        if (t > --b) break;

        for (int i = b; i >= t; i--) res[i][l] = count++;
        if (++l > r) break;
    }
    *returnSize = n;

    return res;
}