LeetCode 54. Spiral Matrix

Problem

LeetCode 54. Spiral Matrix

1. 题目简述

给出一个m * n的矩阵，将其螺旋打印出来。例如：

Example 1:

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

Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

2. 算法思路

相关问题：

1. LeetCode 59. Spiral Matrix II

极其经典的螺旋打印的问题，这里的暴力做法其实是很麻烦的，用方向数组比较好！

暴力解法——螺旋打印

注意这里的边界情况是只有一行或者一列的情况，要特殊处理，比较麻烦，建议直接去看第二写法或者解法二。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 每次打印一圈，直至index越界直接return，写一个子函数。
        List<Integer> res = new ArrayList();

        helper(matrix, 0, 0, res);

        return res;
    }

    private void helper (int[][] matrix, int i, int j, List<Integer> res) {
        if (matrix.length == 0) {
            return;
        }

        int m = matrix.length, n = matrix[0].length;
        int height = m - 2 * i, width = n - 2 * j;

        // 越界的情况
        if (width <= 0 || height <= 0) {
            return;
        }

        // 剩下一行或一列的情况
        if (height == 1) {
            // 一行
            for (int x = 0; x < width; x++) {
                res.add(matrix[i][j + x]);
            }
            return;
        }
        if (width == 1) {
            // 一列
            for (int x = 0; x < height; x++) {
                res.add(matrix[i + x][j]);
            }
            return;
        }

        // 开始按圈添加res
        // 上方一行，例如[1,2]
        for (int x = 0; x < width - 1; x++) {
            res.add(matrix[i][j + x]);
        }
        // 右侧一列，例如[3,6]
        for (int x = 0; x < height - 1; x++) {
            res.add(matrix[i + x][j + width - 1]);
        }
        // 下方一行，例如[9,8]
        for (int x = 0; x < width - 1; x++) {
            res.add(matrix[i + height - 1][j + width - 1 - x]);
        }
        // 左侧一列，例如[7, 4]
        for (int x = 0; x < height - 1; x++) {
            res.add(matrix[i + height - 1 - x][j]);
        }

        helper(matrix, i + 1, j + 1, res);
    }
}

第二种写法和下面的解法二有异曲同工之妙，最好记一下，这样不需要去使用额外的m*n的空间，也就是isVisited数组。题解链接：题解

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

方向数组巧妙解法

对于这种需要四个方向dfs的题目来说，方向数组最适合不过了，对于四个方向，只需要定义dx和dy即可。也就是说dx = [-1, 1, 0, 0]， dy = [0, 0, -1, 1]，分别对应“上下左右”四个方向，每次只需要判断是否越界或者已经填充即可。这么写的好处是节省脑力，不需要判断每次的长度，很省事！！！但是相应的有一丢丢浪费空间，因为需要额外的bool数组来存储每个数字是否已经打印。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new ArrayList<Integer>();
        }

        int m = matrix.length, n = matrix[0].length;
        // 这里用一个boolean数组来定义是否已经访问过该数字
        boolean[][] isVisited = new boolean[m][n];
        // 定义四个方向，此题的顺序应该是右下左上，注意顺序
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        // 定义一个返回的结果集
        List<Integer> res = new ArrayList();

        int x = 0, y = 0, direction = 0;

        while (res.size() < m * n) {
            res.add(matrix[x][y]);
            isVisited[x][y] = true;
            if (x + dx[direction] < 0 || x + dx[direction] >= m || y + dy[direction] < 0 || y + dy[direction] >= n || isVisited[x + dx[direction]][y + dy[direction]] == true) {
                // 此时需要变更方向
                direction = (direction + 1) % 4;
            }
            x += dx[direction];
            y += dy[direction];
        }

        return res;
    }
}