LeetCode_59_SpiralMatrixII

1. question: 螺旋数组II（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/spiral-matrix-ii

示例 1：

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

示例 2：

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

提示：

1 <= n <= 20

2. answers

这道题没什么思路，直接参考博客的答案。不要被螺旋的思路限制住。

首先我们求解的数组，也就是N*N的数组，因为螺旋可以看成是宏观上的外圈到内圈，所以我们可以模拟螺旋由外到内填充数组。

1. 一圈可分成四个方向，并且方向是按照数值逐步增大的。四个方向依次是：左——>右；上——>下；右——>左；下——>上。可按照四个方向分别填充。
2. 为了方便，将四个方向分别划分成等量的元素。如上图中的1,2；3,4；5,6；7,8。那么每边的元素个数怎么确定呢？可归纳一下，最外圈一定就是N-1；内一圈，因为圈存在两边，所以内一圈的一边就比外圈少2。
3. 每个方向的尾元素和下个方向的首元素在数组下标(x,y)是有关系的，要么x+1,要么y+1。或者减一。

因此，经过上述步骤，可填充一圈。那么如何确定有圈数s呢？

因为，一圈是有两侧的，若干个圈的两侧（类似树的年轮）共同组成了横截面，也就是N。因此如果N是偶数，则圈数就是除2；如果是奇数，则最内圈，实际上就是一个元素，1+2s=N，相当于对2取整。至于最内的元素，可单独赋值。

此时，还需要确定的一点是：相邻两圈的关系，显然每圈都被分为四个方向边，且都是依照上面顺序来填充的，显然外圈的尾元素（最后一条边的尾元素）和内圈的首元素是相邻的，即x1 = x0, y1 = y0+1。

代码如下所示（注意，循环时的退出已经满足了，所以上面四条边的首尾元素的下标关系要重新判断。）：

public class Solution_0057 {

    public static int[][] generateMatrix(int n) {

        int[][] result = new int[n][n];

        int cycle = n / 2;
        int countPer = n - 1;
        int num = 1;

        int x1, y1;
        int x2, y2;
        int x3, y3;
        int x4 = -1, y4 = -1;    // 构造初始位置，虚拟上一圈的最后一条边的最后一个元素。

        while(cycle > 0) {

            // 填充由左到右
            // 此时改变的第一个元素(x1, y1)和上一边的最后一个元素(x4, y4)的关系，x1=x4, y1=y4+1
            // (因为上一圈退出循环时，x4已经自减1了，所以此时x1=x4+1)
            // 循环时，x保持不变，y递增1
            x1 = x4 + 1;
            y1 = y4 + 1;
            for (int i = 0; i < countPer; i++)
                result[x1][y1++] = num++;



            // 填充由上到下
            // 此时该边的第一个元素(x2, y2)和上一边的最后一个元素(x1, y1)的关系，x2=x1, y2=y1+1 (因为退出循环时，y1已经自加1了，所以此时y2=y1)
            // 循环时，x递增1，y保持不变
            x2 = x1;
            y2 = y1;
            for (int i = 0; i < countPer; i++)
                result[x2++][y2] = num++;

            // 填充由右到左
            // 此时该边的第一个元素(x3, y3)和上一边的最后一个元素(x2, y2)的关系，x3=x2+1, y3=y2 (因为退出循环时，x2已经自加1了，所以此时x3=x2)
            // 循环时，x保持不变，y递减1
            x3 = x2;
            y3 = y2;
            for (int i = 0; i < countPer; i++)
                result[x3][y3--] = num++;

            // 填充由下到上
            // 此时该边的第一个元素(x4, y4)和上一边的最后一个元素(x3, y3)的关系，x4=x3, y4=y3-1 (因为退出循环时，y3已经自减1了，所以此时y4=y3)
            // 循环时，x递减1，y保持不变
            x4 = x3;
            y4 = y3;
            for (int i = 0; i < countPer; i++)
                result[x4--][y4] = num++;

            // 进行下一圈，并设置好下一圈每边的元素个数。
            cycle--;
            countPer -= 2;
        }

        // 如果n是奇数，那么一定存在最后一个元素。但是仍然满足上面的规则，（注意，此时是退出循环的位置）
        // 上一圈的最后一边的最后一个位置，一定是在下一圈的第一条边的第一个位置的左边。
        // 但是因为循环的缘故，所以此时的下标已经是超出循环了，而且最后一条边是自下而上，所以此时的位置就是在下一圈起始节点的左上方。
        // 由此可得下一圈的坐标：x4 + 1, y4 + 1;
        if( n % 2 == 1)
            result[x4 + 1][y4 + 1] = num;

        return result;
    }

    public static void main(String[] args) {

//        int[][] result = generateMatrix(3);
        int[][] result = generateMatrix(1);

        for(int[] temp: result) {

            for(int i: temp)
                System.out.print(i + "\t");

            System.out.println();
        }
    }
}

仔细分析上面的代码，可以看到，其实每圈循环的时候，除了最开始的下标更新，后面三个方向的下标实际上是一样的（因为每个方向的循环退出时，刚好是下一个方向的首元素），所以没必要设置那么多的变量。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。