每日一题 | 螺旋矩阵2

螺旋矩阵2（209. 中等难度）

题目来源

LeetCode 59. 螺旋矩阵2[1]

题目描述

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

示例

示例 1：

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

示例 2：

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

作者思考

常规走法：一步一步正常走，遇到边界就换方向。

有三个问题要解决：走要怎么走？(前进的规则)；什么时候拐弯？(边界的判断)；怎么拐弯？(转向的方法)；

前进的规则：不难发现在二维矩阵中，每一次移动都对应一次坐标运算。由此我们可以创建一个模拟前进规则的矩阵。

边界的判断：两种情况需要改变方向。当碰到边界时，当下一个位置已经被填充时。

转向的方法：由于元素按照顺时针填充，前进规则矩阵可以根据路线设计成顺时针模式(右下左上)。

按层填充：可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。

官方题解中有该方法的动画，此处不再重复。

🧠 题解

// 常规走法，模拟路线class Solution {   public int[][] generateMatrix(int n) {             int[][] matrix = new int[n][n];       if(n == 1){           matrix[0][0] = 1;           return matrix;       }       // 模拟前进规则       int[][] directIndex ={           {0,1},// 右           {1,0},// 下           {0,-1},// 左           {-1,0}// 上       };       int index = 0;// 方向索引，先往右走       int row = 0;int col = 0;       int num = 1;       while(num <= n*n){           // 先填充           matrix[row][col] = num;           num++;           // 预判下一个位置           int next_row = row + directIndex[index][0];           int next_col = col + directIndex[index][1];           // 边界判断           if(next_row < 0 || next_row >=n || next_col < 0 || next_col >=n || matrix[next_row][next_col] != 0){               index = (index + 1) % 4;// 按照顺时针改变方向           }           // 更新现在的位置           row = row + directIndex[index][0];           col = col + directIndex[index][1];       }       return matrix;                                                                     }}

// 按层填充//作者：力扣官方题解//链接：https://leetcode.cn/problems/spiral-matrix-ii/solutions/658676/luo-xuan-ju-zhen-ii-by-leetcode-solution-f7fp/class Solution {   public int[][] generateMatrix(int n) {       int num = 1;       int[][] matrix = new int[n][n];       // 初始边界       int left = 0, right = n - 1, top = 0, bottom = n - 1;       while (left <= right && top <= bottom) {           // 填充本层上边           for (int column = left; column <= right; column++) {               matrix[top][column] = num;               num++;           }           // 填充本层右边           for (int row = top + 1; row <= bottom; row++) {               matrix[row][right] = num;               num++;           }           if (left < right && top < bottom) {               // 填充本层下边               for (int column = right - 1; column > left; column--) {                   matrix[bottom][column] = num;                   num++;               }               // 填充本层左边               for (int row = bottom; row > top; row--) {                   matrix[row][left] = num;                   num++;               }           }           // 缩小边界，进入下一层           left++;           right--;           top++;           bottom--;       }       return matrix;   }}

References

[1]LeetCode 59. 螺旋矩阵2: https://leetcode.cn/problems/spiral-matrix-ii/description/