54 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

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

示例 2:

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

解法

• 回溯

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix)==0: return []
        m,n = len(matrix),len(matrix[0])
        memo = [[False for _ in range(n)] for _ in range(m)]
        cur_i,cur_j = 0,0
        dire = [[0,1],[1,0],[0,-1],[-1,0]]
        index = 0
        res = []
        for i in range(m*n):
            res.append(matrix[cur_i][cur_j])
            memo[cur_i][cur_j] = True
            nex_i, nex_j = cur_i+dire[index][0],cur_j+dire[index][1]
            if (0<=nex_i<m) and (0<=nex_j<n) and memo[nex_i][nex_j]==False:
                cur_i,cur_j = nex_i,nex_j
            else:
                index = (index+1)%4
                cur_i, cur_j = cur_i+dire[index][0],cur_j+dire[index][1]
        return res

• 递归

每次打印矩阵最外层的元素，直至矩阵为空。

• 输出矩阵一行，然后去掉第一行，转置矩阵，重复上述操作

#### 例如
'''
[
[1,2,3],
[4,5,6],
[7,8,9]
]
输出第一行 [1,2,3]
反转 
[[4,5,6],   ---> [[6,9],
[7,8,9]]          [5,8],
                  [4,7]]
第一行，[6,9]
反转
[[5,8],     ---> [[8,7],
[4,7]]            [5,4]]
第一行 [8,7]
...
'''
## python中list(zip(*matrix))用法
>>> ls
[[34, 21, 13], [1, 1, 8], [2, 3, 5]]
>>> list(zip(*ls))
[(34, 1, 2), (21, 1, 3), (13, 8, 5)]