【Leetcode】剑指Offer 29：顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 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]
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0:
            return []
        length = len(matrix)
        width = len(matrix[0])
        beginx = 0
        endx = width - 1
        beginy = 0
        endy = length - 1

        res = []
        
        while beginx < width and endx >= 0 and beginy < length and endy >= 0 and (beginx <= endx or beginy <= endy):
            if endy >= beginy:
                for i in range(beginx, endx + 1):
                    res.append(matrix[beginy][i])
            
            if endx >= beginx:
                for i in range(beginy + 1, endy + 1):
                    res.append(matrix[i][endx])

            if endy > beginy:
                for i in range(endx - 1, beginx - 1, -1):
                    res.append(matrix[endy][i])

            if endx > beginx:
                for i in range(endy - 1, beginy, -1):
                    res.append(matrix[i][beginx])

            beginx += 1
            endx -= 1
            beginy += 1
            endy -= 1

        return res
            



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

此题逻辑上很简单，主要是细节上的把握，包括两边界的在奇偶情况下的交错处理，并且在做的过程中，笔者思考到这题是否可以使用数论取模的方法来管理下标索引，这种方法似乎也能够解题。

官方解法：模拟

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return list()
        
        rows, columns = len(matrix), len(matrix[0])
        visited = [[False] * columns for _ in range(rows)]
        total = rows * columns
        order = [0] * total

        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        row, column = 0, 0
        directionIndex = 0
        for i in range(total):
            order[i] = matrix[row][column]
            visited[row][column] = True
            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
                directionIndex = (directionIndex + 1) % 4
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/shun-shi-zhen-da-yin-ju-zhen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

这个解法思路更无脑，但是无脑带来的缺点就是额外会需要一个同矩阵大小的空间来存储标记矩阵。

Python妙解：删除加旋转

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

作者：xiao-ma-nong-25
链接：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/shan-chu-di-yi-xing-ni-shi-zhen-xuan-zhuan-python5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13

虽然此方法一看就不适合算法题哈哈，但是利用zip函数进行旋转矩阵确实很适合学习。此方法笔者最开始想到过类似的，利用删除元素的方法更新边界会容易很多，但是感觉不停调用del很浪费计算时间，故放弃。