54 螺旋矩阵

1
2
3
4
5
6
7

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

1
2
3
4
5
6
7

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

 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

这里的方法不需要记录已经走过的路径，所以执行用时和内存消耗都相对较小

首先设定上下左右边界
其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案
class Solution:
    def spiralOrder(self, matrix):
        if not matrix:
            return matrix
        result = []
        # 高
        row_length = len(matrix)
        # 几列
        col_length = len(matrix[0])

        # 上边界
        up = 0
        # 下边界
        down = row_length
        #         左边界
        left = 0
        #         右边界
        right = col_length

        # 上下游标
        row_cur = 0
        # 左右游标
        col_cur = 0

        while True:
            # print("left = {}, right = {}, up = {}, down = {}".format(left, right, up, down))
            for col_cur in range(left, right):
                # print("1 {}".format(matrix[row_cur][col_cur]))
                result.append(matrix[row_cur][col_cur])
            # 更新上边界
            up += 1
            if up >= down:
                break

            for row_cur in range(up, down):
                # print("2 {}".format(matrix[row_cur][col_cur]))
                result.append(matrix[row_cur][col_cur])
            # 更新右边界
            right -= 1
            if right <= left:
                break

            for col_cur in range(right - 1, left - 1, -1):
                # print("3 {}".format(matrix[row_cur][col_cur]))
                result.append(matrix[row_cur][col_cur])
            # 更新下边界
            down -= 1
            if down <= up:
                break

            for row_cur in range(down - 1, up - 1, -1):
                # print("4 {}".format(matrix[row_cur][col_cur]))
                result.append(matrix[row_cur][col_cur])
            # 更新左边界
            left += 1
            if left >= right:
                break


        return result

if __name__ == '__main__':
    solution = Solution()
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    matrix = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    matrix = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    result = solution.spiralOrder(matrix)
    print(result)