初学算法的小菜鸡 - 自学笔记 (第八天): 关于数组的算法

Leetcode题目链接

题目描述

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

示例 1：

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

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

提示：1 <= n <= 20

据说这道题在面试中出现的频率很高，没什么技巧，主要就是用来考察对于代码的掌控能力，以及模拟过程的能力。

模拟的过程看似十分复杂，但实际上是有规律可循的。

模拟过程分析如下：

从上面给出的图中，我们不难看出整个输出过程能够被分成四个主要的步骤分别是：

以图中n = 3为例

最上一行的从左到右。

最右一列的从上倒下。

最下一行的从右到左。

最左一列的从下到上。

事实上，我们可以想象对于任意的N，都一定要经历这四个主要步骤，唯一能够有所不同的就是N的奇偶是否会对我们的模拟过程产生影响。

这里我画了两张图来区分和解释N的奇偶可能对模拟过程产生的影响。

n = 4时 模拟过程如下图：

 n = 3时 模拟过程如下图：

 我利用不同的颜色分别模拟了n=3和n=4时不同奇偶情况下的输出过程，不难看出在n为奇数的情况下我们需要考虑该过程中心区域的特殊情况，而当n为偶数时则不需要考虑中心区的特殊情况。

因此整个模拟过程的代码如下

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];

        // 循环次数：代表模拟4个主要过程的循环次数，例如当n为3时我们只需要模拟最外圈一遍。


        int loop = n / 2; 

        // 定义每次循环起始位置
        int startX = 0;
        int startY = 0;

        // 定义偏移量：当n为4时我们需要经历两遍主要过程，但两遍存在2个单位的偏移，例如最外圈和最内圈
        int offset = 1;

        // 定义填充数字
        int count = 1;

        // 定义中间位置：n为奇数时使用，偶数时不使用
        int mid = n / 2;
        while (loop > 0) {
            int i = startX;
            int j = startY;

            // 模拟上侧从左到右
            for (; j startY; j--) {
                res[i][j] = count++;
            }

            // 模拟左侧从下到上
            for (; i > startX; i--) {
                res[i][j] = count++;
            }

            loop--;

            startX += 1;
            startY += 1;

            offset += 2;
        }

        if (n % 2 == 1) {
            res[mid][mid] = count;
        }

        return res;
    }
}

运行结果如下：