LeetCode 54. Spiral Matrix & 剑指Offer 29. 顺时针打印矩阵 [Medium]

发表于 | 更新于 | 分类于 ， | 阅读次数：

LeetCode 54. Spiral Matrix & 剑指Offer 29. 顺时针打印矩阵

题目来源：https://leetcode.com/problems/spiral-matrix

题目难度：Medium

解答1[Java]：

核心思想

从外层向内层，一圈一圈地遍历。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0)
            return ans;
        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
            for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
            if (r1 < r2 && c1 < c2) {
                for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
                for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
            }
            r1++;
            c1++;
            r2--;
            c2--;
        }
        return ans;
    }
}

解答2[Java]：

核心思想

这个才是真的全自动顺时针打印。设计了两个数组，一个 directionOfRow，一个directionOfColumn，这样，directionOfRow[i] 和 directionOfColumn[i] 这么一组数就表示下一步该怎么走，如果越界了，那么 ++i，相当于换成下一种走法。第一圈使用数组行数和列数来判定是否越界，第二圈就要靠 seen 数组来判断。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList();
        if (matrix.length == 0) return ans;
        int R = matrix.length, C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        int[] directionOfRow = {0, 1, 0, -1};
        int[] directionOfColumn = {1, 0, -1, 0};
        int r = 0, c = 0, dierectionCount = 0;
        for (int i = 0; i < R * C; ++i) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int nextR = r + directionOfRow[dierectionCount];
            int nextC = c + directionOfColumn[dierectionCount];
            if (0 <= nextR && nextR < R && 0 <= nextC && nextC < C && !seen[nextR][nextC]) {
                r = nextR;
                c = nextC;
            } else {
                dierectionCount = (dierectionCount + 1) % 4;
                r += directionOfRow[dierectionCount];
                c += directionOfColumn[dierectionCount];
            }
        }
        return ans;
    }
}