54. 螺旋矩阵(中等)

Posted on In Views:

1，问题描述

54. 螺旋矩阵

难度：中等

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

示例 1：

img

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

示例 2：

img

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

2，初步思考

​ 参考第59题旋转螺旋，我使用的是模拟法
​ 官方的分层法也是特别简单

3，代码处理

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.ArrayList;
import java.util.List;

public class _54螺旋矩阵 {

    // 解法：分层处理
    public List<Integer> spiralOrder_level(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;// 四角定位
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {// 向右
                res.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {// 向下
                res.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {// 防止单行数据重复读取
                for (int column = right - 1; column >= left; column--) {// 向左
                    res.add(matrix[bottom][column]);
                }
                for (int row = bottom - 1; row > top; row--) {// 向上
                    res.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return res;
    }

    // 解法：数学多进制求解（j列进制处理）
    public List<Integer> spiralOrder_simulation(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int xlen = matrix.length, ylen = matrix[0].length;
        int loop = ylen * xlen;
        int temp = 0;
        int x = 0, y = 0;
        int target = 0;// 0右，1下，2左，3上
        for (int i = 0; i < loop; i++) {
            temp++;
            res.add(matrix[x][y]);
            switch (target) {
                case 0:// 向右
                    if (temp == ylen) {// 转向下
                        temp = 0;
                        xlen--;
                        target = 1;
                        x++;
                    } else {
                        y++;
                    }
                    break;
                case 1:// 向下
                    if (temp == xlen) {// 转向左
                        temp = 0;
                        ylen--;
                        target = 2;
                        y--;
                    } else {
                        x++;
                    }
                    break;
                case 2:// 向左
                    if (temp == ylen) {// 转向上
                        temp = 0;
                        xlen--;
                        target = 3;
                        x--;
                    } else {
                        y--;
                    }
                    break;
                case 3:// 向上
                    if (temp == xlen) {// 转向右
                        temp = 0;
                        ylen--;
                        target = 0;
                        y++;
                    } else {
                        x--;
                    }
                    break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        _54螺旋矩阵 spiralMatrix = new _54螺旋矩阵();
        System.out.println(spiralMatrix.spiralOrder_level(new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        }));
//        System.out.println(spiralMatrix.spiralOrder_level(new int[][]{
//                {1, 2, 3, 4},
//                {5, 6, 7, 8},
//                {9, 10, 11, 12}
//        }));
    }
}