LeetCode_螺旋遍历_中等_59.螺旋矩阵 II

骑猪看日落 2023-10-06 19:01 7阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**

![在这里插入图片描述][04879a1c3f7741ed9ae39c1e01051343.png]  
输入：n = 3  
输出：\[\[1,2,3\],\[8,9,4\],\[7,6,5\]\]

**示例 2：**  
输入：n = 1  
输出：\[\[1\]\]

**提示：**  
1 <= n <= 20  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/spiral-matrix-ii

## 2.思路 ##

（1）螺旋遍历  
此题思路与[LeetCode\_54.螺旋矩阵][LeetCode_54.]类似。分析题目可知，按照顺时针螺旋顺序生成矩阵中的整数时，从起点 matrix\[0\]\[0\] 开始，总是按照向右→向下→向左→向上→向右→向下→…的方向开始，直到将整个矩阵填满为止。故可以考虑照这个规律来生成矩阵中的所有整数，具体步骤如下：  
① 定义行数和列数均为 n 的矩阵 matrix；  
② 为了防止在按上述方向生成整数时覆盖掉已经生成的整数，所以可以设置一个与矩阵同行同列的 visited 数组，其元素类型为 boolean，若 visited\[i\]\[j\] = true，则说明已经生成过矩阵中的元素 matrix\[i\]\[j\]，否则说明没有生成；  
③ 为了在程序中实现按上述方向生成整数，可以用 direction 来表示即将要生成整数的方向，direction = 1、2、3、4分别表示在矩阵中向右、下、左、上方向生成整数；  
④ 设置起点坐标 i 和 j，在本题中，起点整数为 matrix\[0\]\[0\]，故其初始值均为 num = 1，然后设置 visited\[i\]\[j\] = true，即表示起点已经生成整数，以上准备工作完成后，便可以开始循环生成整数了；  
⑤ 在生成整数过程中，使用 if-else 语句来判断遍历的方向，并且每访问，就将该元矩阵 matrix 中的一个位置，就将生成的整数保存在该位置，此外在生成整数过程中尤其**要注意防止数组越界以及整数覆盖的问题**，当某一个位置的上述四个方向都不能生成整数时，则说明已经将矩阵的所有位置都填满，此时直接退出循环并返回 matrix 即可。

相关题目：  
[LeetCode\_螺旋遍历\_中等\_54.螺旋矩阵][LeetCode_54.]

## 3.代码实现（Java） ##

//思路1————螺旋遍历
    public int[][] generateMatrix(int n) {
        
        int[][] matrix = new int[n][n];
        // visited[i][j] == true 表示已经生成过矩阵中的元素 matrix[i][j]
        boolean[][] visited = new boolean[n][n];
        // direction = 1、2、3、4 分别表示在矩阵中向右、下、左、上方向上生成整数
        //初始时，按照向右→向下→向左→向上→向右→向下→...的方向开始生成整数，直到将整个矩阵填满为止
        int direction = 1;
        //定义生成整数起点的横纵坐标
        int i = 0, j = 0;
        //设生成的起始整数 num = 1
        int num = 1;
        matrix[i][j] = num;
        //将生成整数的起点设置为已访问的状态
        visited[i][j] = true;
        while (true) {
        
            if (direction == 1 && j + 1 < n && visited[i][j + 1] == false) {
        
                //向右生成整数
                while (j + 1 < n && visited[i][j + 1] == false) {
        
                    matrix[i][j + 1] = ++num;
                    visited[i][j + 1] = true;
                    j++;
                }
                direction++;
            } else if (direction == 2 && i + 1 < n && visited[i + 1][j] == false) {
        
                //向下生成整数
                while (i + 1 < n && visited[i + 1][j] == false) {
        
                    matrix[i + 1][j] = ++num;
                    visited[i + 1][j] = true;
                    i++;
                }
                direction++;
            } else if (direction == 3 && j - 1 >= 0 && visited[i][j - 1] == false) {
        
                //向左生成整数
                while (j - 1 >= 0 && visited[i][j - 1] == false) {
        
                    matrix[i][j - 1] = ++num;
                    visited[i][j - 1] = true;
                    j--;
                    ;
                }
                direction++;
            } else if (direction == 4 && i - 1 >= 0 && visited[i - 1][j] == false) {
        
                //向上生成整数
                while (i - 1 >= 0 && visited[i - 1][j] == false) {
        
                    matrix[i - 1][j] = ++num;
                    visited[i - 1][j] = true;
                    i--;
                }
                direction = 1;
            } else {
        
                //生成整数结束
                break;
            }
        }
        return matrix;
    }

[04879a1c3f7741ed9ae39c1e01051343.png]: https://img-blog.csdnimg.cn/04879a1c3f7741ed9ae39c1e01051343.png
[LeetCode_54.]: https://blog.csdn.net/weixin_43004044/article/details/119744180