LeetCode-59.螺旋矩阵-II

本文最后更新于 <span id="expire-date"></span> 天前，文中部分描述可能已经过时。

59.螺旋矩阵 II

题目

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order.

Example 1:

Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1 Output: [[1]]

Constraints:

1 <= n <= 20

题解

这道题并没有考察算法，难点在于寻找螺旋数组生成的规律。

要寻找规律可以模拟生成过程走一遍

初步模拟

此图反映了螺旋数组生成的简单过程，这张图片有很明显的对称特点，而通过这一特点可以提取出生成规律：

若将循环一周作为一个周期，则每个二维数组有 n/2 个周期
每个周期可以拆解为四个部分：从左到右，从上到下，从右到左，从下到上
建立x，y直角坐标系（右手系），新周期的起始位置的横纵坐标与上一周期结束位置的横纵坐标分别相差一

代码如下：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int x = 0, y = 0;
        //设置起始位置
        int deviation = 1;
        //设置偏移量
        int val = 1;
        //定义数值
        int loop = 0;
        //定义周期
        while(loop < n/2){
            int i = x;
            int j = y;
            for(; j < y + n - deviation; j++){
                res[x][j] = val++;
            }
            //从左到右
            for(; i < x + n - deviation; i++){
                res[i][j] = val++;
            }
            //从上到下
            for(; j > y; j--){
                res[i][j] = val++;
            }
            //从右到左
            for(;i > x; i--){
                res[i][j] = val++;
            }
            x++;
            y++;
            //新一周期的横纵坐标加1，相当于沿着方阵的主对角线运动
            deviation += 2;
        	//偏移量加2，因为起始位置加1，故要多加1
        	loop++;
            //周期自增
        }
        if(n%2 == 1){
            res[n/2][n/2] = val;	
        }
        return res;
    }
}

本文作者：Mosquito

本文链接： http://example.com/2022/01/28/LeetCode-59-%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5-II/

Mosquito 天使之吻手打

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

更新于 2022-05-22

# LeetCode