算法题002：螺旋矩阵 II

发表于 分类于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

题目

题目来源：59. 螺旋矩阵 II

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

示例

示例 1

输入：

1
3

输出：

img

1
[[1,2,3],[8,9,4],[7,6,5]]

示例 2

输入：

1
1

输出：

1
[[1]]

思路

这道题是一道典型的模拟题，我们需要按照遍历整个矩阵。

思路 1

我自己的做法是将矩阵分层（layer），一层一层地遍历。比如，当 $n = 3$ 时，矩阵为

img

此时，我们定义第一层为 layer = 0，包含数字 1 - 8；第二层为 layer = 1，包含数字 9；

遍历每一层时，依次编写向右（1、2）、向下（3、4）、向左（5、6）、向右（7、8）的循环代码

这种方法的重点在于找数学规律，找到 layer 和当前遍历的某一行/某一列的大小关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int counter = 1;

        for (int layer = 0; layer <= n / 2; layer++) {
            // 向右
            for (int j = layer; j < n - layer - 1; ++j, ++counter) {
                ans[layer][j] = counter;
            }
            // 向下
            for (int i = layer; i < n - layer - 1; ++i, ++counter) {
                ans[i][n - layer - 1] = counter;
            }
            // 向左
            for (int j = n - layer - 1; j > layer; --j, ++counter) {
                ans[n - layer - 1][j] = counter;
            }
            // 向上
            for (int i = n - layer - 1; i > layer; --i, ++counter) {
                ans[i][layer] = counter;
            }
        }
        // 对于边长为奇数的方阵，中心元素需要手动处理
        if (n % 2 == 1) {
            ans[n / 2][n / 2] = counter;
        }

        return ans;
    }
}

显然，这种做法很容易错，毕竟找规律挺无聊的。

力扣上的几位大佬，提供了一种不需要找规律的解法，比如 Krahets 的题解：手动地控制上下左右四个边界，当遍历到边界时，就到头了，向下一个方向开始遍历。

思路 2

由于我们要生成一个矩阵（非常规则的图形），我们往往会从宏观的角度控制遍历，即思路 1。所谓宏观，即知道全局，它体现在我的解法的找数学规律，也体现在大佬的解法的控制四个边界。

那我们不妨从微观角度出发：假如我们自己站在一个巨大的、看不到边界的棋盘上，要去填入这些数字，我们会怎么填？我们只能看到四周的格子上的数字。此时，宏观的方法不再奏效，我们应该怎么做？

img

假设我们站在格子 1 上（面朝右），往前走，边走边写数字。当走到了格子 3，发现前面无路可走。因为要顺时针填入数字，我们不妨右拐（面朝下），此时面向的格子，就是要填入数字 4 的格子。

同理，当我们走到了格子 8（面朝上），此时前面的格子已经填入了数字 1。我们再次右拐（面朝右），此时面向的格子，就是要填入数字 9 的格子。

因此，在代码中，我们不妨只关心 agent 当前的坐标，让他认准一个方向一直走，直到遇到边界、或者已经填入了数字，此时右拐即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // (dx[k], dy[k]) 表示移动的方向，按照轮询的顺序，依次是向右、向下、向左、向上、向右 ...
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // (x, y) 是 agent 的坐标;
        // dir 表示当前移动的方向，是 dx, dy 数组的索引
        int x = 0, y = 0, dir = 0;
        // 循环变量，以及循环退出条件
        int counter = 1, limit = n * n;
        while (counter <= limit) {
            // 当前坐标在边界内，同时当前格子没有填入数字
            while (0 <= x && x < n && 0 <= y && y < n && ans[x][y] == 0) {
                ans[x][y] = counter;
                counter++;
                // 继续走
                x += dx[dir];
                y += dy[dir];
            }
            // 回撤一步
            x -= dx[dir];
            y -= dy[dir];
            // 向右转
            dir = (dir + 1) % dx.length;
            // 往前一步后，位置 (x, y) 即为下一轮 while 循环要处理的第一个格子
            x += dx[dir];
            y += dy[dir];
        }
        return ans;
    }
}

思考

我会想出思路 2，是因为我最近做了一道算法题，它要求我顺时针地给一个边长为 n 的等腰直角三角形（直角边平行于坐标轴）填入数字。

比如，当 n = 4 时，要按如下的方式填入数字：

image-20231003171918667

按照思路 1 的解法，从宏观层面找规律，我根本懒得找，想想就麻烦。如果按照大佬们的边界法，斜边遍历的代码（ $x + y \le k$ ），又何尝不是一种找规律？

按照思路 2，所谓顺时针，其实就是轮询这几个方向：向上、向右下、向左。那么，在代码层面就是：

1
2
int[] dx = {-1, 1, 0};
int[] dy = {0, 1, -1};

改一改思路 2 的代码即可。