螺旋矩阵 | blog

题目描述

leetcode 54：螺旋矩阵

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

示例 1：

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

示例 2：

1 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$

leetcode 59：螺旋矩阵 II

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 20

题解

leetcode 54：螺旋矩阵

简单模拟：

为了避免判断边界，需要在矩阵的最外侧围上一圈 1

代码：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0)
            return list;
        int row = matrix.length, col = matrix[0].length;
        boolean[][] visit = new boolean[row + 2][col + 2];	//记录该位置是否被遍历过
        
        //下面两个 for 循环在 visit矩阵外侧围一圈 1，表示已被访问过，不可再次访问
        for (int i = 0; i < row + 2; i++) {
            visit[i][0] = true;
            visit[i][col + 1] = true;
        }
        for (int j = 0; j < col + 2; j++) {
            visit[0][j] = true;
            visit[row + 1][j] = true;
        }

        int i = 1, j = 1;	//由于外圈多围了一圈，所以初始位置从(0,0)变为了(1,1)
        int direction = 3;  //定义一个变量，记录当前的方向，上下左右分别为：0，1，2，3
        while (true) {
            if (visit[i][j])	//如果四个方向都无路可走了，程序就结束了
                break;
            list.add(matrix[i - 1][j - 1]);	//由于外圈加了一层，所以对应的matrix矩阵中的下标需要减一
            visit[i][j] = true;	//标记当前的格子已被访问过
            switch (direction) {
                case 0:		//上
                    if (visit[i - 1][j]) {	// 如果沿着当前方向走会碰到墙，那么就换个方向
                        direction = 3;	//上面走不通，向右
                        j++;
                    } else {	//否则，继续沿着当前方向走
                        i--;
                    }
                    break;
                case 1:		//下
                    if (visit[i + 1][j]) {
                        direction = 2;	//下面走不通，向左
                        j--;
                    } else {
                        i++;
                    }
                    break;
                case 2:		//左
                    if (visit[i][j - 1]) {
                        direction = 0;	//左面走不通，向上
                        i--;
                    } else {
                        j--;
                    }
                    break;
                case 3:		//右
                    if (visit[i][j + 1]) {
                        direction = 1;	//右面走不通，向下
                        i++;
                    } else {
                        j++;
                    }
                    break;
            }
        }
        return list;
    }
}

leetcode 59：螺旋矩阵 II

代码把上面的代码热热还能用：

代码：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        boolean[][] visit = new boolean[n + 2][n + 2];    //记录该位置是否被遍历过

        //下面两个 for 循环在 visit矩阵外侧围一圈 1，表示已被访问过，不可再次访问
        for (int i = 0; i < n + 2; i++) {
            visit[i][0] = true;
            visit[i][n + 1] = true;
        }
        for (int j = 0; j < n + 2; j++) {
            visit[0][j] = true;
            visit[n + 1][j] = true;
        }

        int i = 1, j = 1;    //由于外圈多围了一圈，所以初始位置从(0,0)变为了(1,1)
        int direction = 3;  //定义一个变量，记录当前的方向，上下左右分别为：0，1，2，3
        int num = 1;        //将要填的数字
        while (true) {
            if (visit[i][j])    //如果四个方向都无路可走了，程序就结束了
                break;
            matrix[i - 1][j - 1] = num++;    //由于外圈加了一层，所以对应的matrix矩阵中的下标需要减一
            visit[i][j] = true;             //标记当前的格子已被访问过
            switch (direction) {
                case 0:        //上
                    if (visit[i - 1][j]) {    // 如果沿着当前方向走会碰到墙，那么就换个方向
                        direction = 3;    //上面走不通，向右
                        j++;
                    } else {    //否则，继续沿着当前方向走
                        i--;
                    }
                    break;
                case 1:        //下
                    if (visit[i + 1][j]) {
                        direction = 2;    //下面走不通，向左
                        j--;
                    } else {
                        i++;
                    }
                    break;
                case 2:        //左
                    if (visit[i][j - 1]) {
                        direction = 0;    //左面走不通，向上
                        i--;
                    } else {
                        j--;
                    }
                    break;
                case 3:        //右
                    if (visit[i][j + 1]) {
                        direction = 1;    //右面走不通，向下
                        i++;
                    } else {
                        j++;
                    }
                    break;
            }
        }
        return matrix;
    }
}