顺时针打印矩阵

475 字

2 分钟

顺时针打印矩阵

2021-07-13

2026-10-12

数据结构与算法

「剑指Offer」Swift

题目描述#

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

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

示例 2：

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

5
限制：
6

7
```C++
8
0 <= matrix.length <= 100
9
0 <= matrix[i].length <= 100

注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof

题解链接

GitHub

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路#

出现需要变更方向的点的拐向是一定的：
- 当前向➡️扫描，拐点一定向↓
- 当前向↓扫描，拐点一定向←
- 当前向←扫描，拐点一定向↑
- 当前向↑扫描，拐点一定向➡️

flags为标记数组，用来标识已经扫描过的下标

在一个方向上：扫描到边界 或者 扫描到已标记的坐标 则触发转向

代码#

1
class Solution {
2
    enum Dirction {
3
        /// x + 1
4
        case Right
5
        /// y + 1
6
        case Down
7
        /// x - 1
8
        case Left
9
        /// y - 1
10
        case Up
11
    }
12

13
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
14
        var result: [Int] = []
15
        let height = matrix.count
16

17
        guard let first = matrix.first, height > 0 else {
18
            return result
19
        }
20

21
        let width = first.count
22
        var x = 0, y = 0
23
        var dir: Dirction = .Right
24

25
        var flags: [[Bool]] = Array(repeating: Array(repeating: false, count: width), count: height)
26

27
        while x >= 0, y >= 0, x < width, y < height, result.count < width * height {
28
            flags[y][x] = true
29
            result.append(matrix[y][x])
30

31
            switch dir {
32
            case .Right:
33
                if x + 1 < width, flags[y][x + 1] == false {
34
                    x += 1
35
                }
36
                else {
37
                    dir = .Down
38
                    y += 1
39
                }
40
            case .Down:
41
                if y + 1 < height, flags[y + 1][x] == false {
42
                    y += 1
43
                }
44
                else {
45
                    dir = .Left
46
                    x -= 1
47
                }
48
            case .Left:
49
                if x - 1 >= 0, x - 1 < width, flags[y][x - 1] == false {
50
                    x -= 1
51
                }
52
                else {
53
                    dir = .Up
54
                    y -= 1
55
                }
56
            case .Up:
57
                if y - 1 >= 0, y - 1 < height, flags[y - 1][x] == false {
58
                    y -= 1
59
                }
60
                else {
61
                    dir = .Right
62
                    x += 1
63
                }
64
            }
65
        }
66

67
        return result
68
    }
69
}

反转链表

一套iOS底层试卷