螺旋矩阵汇总

2025-03-21 9 min

写在前面

其实螺旋矩阵类的题目按理来说应该是简单的，因为是纯粹的模拟，只不大家定义方向的方式各有不同，以及方向的转换以及判断不够灵活，所以我们就简单试试！

螺旋矩阵

LeetCode原题链接

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例1

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

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

解读

其实这是很经典的顺时针螺旋矩阵了，只需要定义好方向，判断好数组边界以及已访问边界，就可以很顺利解决了。所以接下来我们简单看看实现。

最重要的事情其实是定义好方向，然后根据方向进行走步。

学会优雅的第一步，就是勇敢的派出一个探子，让它去尝试，如果它失败了我们就换方向走一步，否则就原方向走一步

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int n = matrix.length;
        int m= matrix[0].length;
        //此处定义方向，按序分别为右、下、左、上，也就是我们螺旋的顺序
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        //初始化
        int dir_key=0;
        int i=0,j=0;
        for(int c = 0; c < n * m; c++){
            res.add(matrix[i][j]);
            //因为有范围为-100，100，标记已经访问过就可以用101
            matrix[i][j]=101;
            //别管碰不碰壁，先派个探子去送死,如果探子没事我们就坚持方向，如果有事我们就换方向
            int i_try = i + direction[dir_key][0];
            int j_try = j + direction[dir_key][1];
            if(i_try<0 || i_try>=n || j_try<0 || j_try>=m || matrix[i_try][j_try]>100){
                dir_key = (dir_key+1)%4;
            }
            i = i+direction[dir_key][0];
            j = j+direction[dir_key][1];
        }
        return res;
    }
}

螺旋矩阵II

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

解读

其实本质上和上题是同样的思路，只不过一个是写入，一个是读取，不多赘述

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int[][] way = {{0,1},{1,0},{0,-1},{-1,0}};
        int c=0,l=0;
        int way_key = 0;
        for(int i=1;i<=n*n;i++){
            res[c][l]=i;
            int nextc = c + way[way_key][0];
            int nextl = l + way[way_key][1];
            if (nextc < 0 || nextc >= n || nextl < 0 || nextl >= n || res[nextc][nextl] != 0) {
                way_key = (way_key + 1) % 4;
            }
            c = c+way[way_key][0];
            l = l+way[way_key][1];
        }
        return res;
    }
}

螺旋矩阵III

这题还有有一点令人难受的，因为需要剪枝才能让效率稍微好一些，但是我剪的也不是非常好

LeetCode原题链接

题目描述

在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 rows x cols 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

示例 2：

输入：rows = 5, cols = 6, rStart = 1, cStart = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

提示：

1 <= rows, cols <= 100
0 <= rStart < rows
0 <= cStart < cols

解读

其实还是老模板，只不过这次不会碰壁，是由内而外，所以需要自己判断螺旋什么时候需要走多少步。

其实我们可以发现，只要方向由上下变为左右的时候，就需要把螺旋的边长增加1，这点需要自己品味，为什么我设置的初始方向是向上，初始step是0，其实都是有一点意思的。

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int r_n=rStart;
        int c_n=cStart;
        int step =0;
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        int dir_key = 3;
        int count=1;
        int[][] res=new int[rows*cols][2];
        res[0][0]=r_n;
        res[0][1]=c_n;
        while(count<rows*cols){
          	//方向转换
            if(dir_key%2==1){
                step+=1;
            }
            dir_key = (dir_key+1)%4;
          	//	剪枝，如果方向错了，就不用一步一步走了，反正都不会加进去，直接一步走到底
            if((r_n<0&&direction[dir_key][0]<=0)||
                (c_n<0&&direction[dir_key][1]<=0)||
                (r_n>=rows&&direction[dir_key][0]>=0)||
                (c_n>=cols&&direction[dir_key][1]>=0)){
                r_n=r_n+direction[dir_key][0]*step;
                c_n=c_n+direction[dir_key][1]*step;
                continue;
            }
          	// 走步
            for(int i=0;i<step;i++){
                r_n=r_n+direction[dir_key][0];
                c_n=c_n+direction[dir_key][1];
                if(r_n>=0&&r_n<rows&&c_n>=0&&c_n<cols){
                    res[count][0]=r_n;
                    res[count][1]=c_n;
                    count++;
                }
            }
        }
        return res;
    }
}

螺旋矩阵IV

LeetCode原题链接

题目描述

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按螺旋顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

示例 1：

输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。

示例 2：

输入：m = 1, n = 4, head = [0,1,2]
输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。 
注意，矩阵中剩下的空格用 -1 填充。

提示：

1 <= m, n <= 105
1 <= m * n <= 105
链表中节点数目在范围 [1, m * n] 内
0 <= Node.val <= 1000

解读

这题不多说啊，直接照搬II的代码就可以了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] res = new int[m][n];
        for(int i=0;i<m;i++){
            Arrays.fill(res[i],-1);
        }
        //此处定义方向，按序分别为右、下、左、上，也就是我们螺旋的顺序
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        //初始化
        int dir_key=0;
        int i=0,j=0;
        ListNode pre=head;
        while(pre!=null){
            res[i][j] = pre.val;
            pre=pre.next;
            //别管碰不碰壁，先派个探子去送死,如果探子没事我们就坚持方向，如果有事我们就换方向
            int i_try = i + direction[dir_key][0];
            int j_try = j + direction[dir_key][1];
            if(i_try<0 || i_try>=m || j_try<0 || j_try>=n || res[i_try][j_try]!=-1){
                dir_key = (dir_key+1)%4;
            }
            i = i+direction[dir_key][0];
            j = j+direction[dir_key][1];
        }
        return res;
    }
}

关于边界处理

其实I和IV都取巧了，就是在判断有没有达到边界的时候，用了数值的范围。

所以其实墙壁也需要交给我们管理的，所以对于IV的代码，我们也可以这么写。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] res = new int[m][n];
        for(int i=0;i<m;i++){
            Arrays.fill(res[i],-1);
        }
        //此处定义方向，按序分别为右、下、左、上，也就是我们螺旋的顺序
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        //初始化
        int dir_key=0;
        int i=0,j=0;
        ListNode pre=head;
      	//初始化边界
        int top=0,left=0,bottom=m-1,right=n-1;
        while(pre!=null){
            res[i][j] = pre.val;
            pre=pre.next;
            //别管碰不碰壁，先派个探子去送死,如果探子没事我们就坚持方向，如果有事我们就换方向
            int i_try = i + direction[dir_key][0];
            int j_try = j + direction[dir_key][1];
            if(i_try<top || i_try>bottom || j_try<left || j_try>right){
                //碰壁就缩小墙壁
                dir_key = (dir_key+1)%4;
                if(dir_key==0) left+=1;
                if(dir_key==1) top+=1;
                if(dir_key==2) right-=1;
                if(dir_key==3) bottom-=1;
            }
            i = i+direction[dir_key][0];
            j = j+direction[dir_key][1];
        }
        return res;
    }
}