54. 螺旋矩阵 [medium]

https://leetcode-cn.com/problems/spiral-matrix/

给定一个包含 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]

通过次数71,091 | 提交次数174,272

Second Try

2020-07-28

看官方题解，directions可以直接按照右->下->左->上依次顺序, 然后每次需要切换的时候只需要idx + 1即可。考虑循环的问题，则使用取余 direction_idx = (direction_idx + 1) % 4可实现。

思路还是一样的，代码简化了一些。

看官方题解，还可以按照一层一层直接遍历，但就先这样吧。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not (len(matrix) and len(matrix[0])):
            return []
        m, n = len(matrix), len(matrix[0])
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] # 右->下->左->上依次顺序

        rv = []
        visited = set() 
        i, j = 0, 0 
        direction_idx = 0 
        while len(rv) != m * n:
            rv.append(matrix[i][j])
            visited.add(matrix[i][j])
            
            step_i, step_j = directions[direction_idx]
            ni, nj = i + step_i, j + step_j
            if ni < 0 or ni >= m or nj < 0 or nj >= n or matrix[ni][nj] in visited:
                direction_idx = (direction_idx + 1) % 4 # 通过取余，直接实现了循环的效果 
                step_i, step_j = directions[direction_idx]
            i, j = i + step_i, j + step_j

        return rv 

执行用时：48 ms, 在所有 Python3 提交中击败了17.16%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.25%的用户

First Try

2020-07-28

比较占用空间的写法，模拟贪吃蛇的路线一路往前走，如果出界了或是已经走过了，则往回退，然后绕个方向继续往前走。有点状态切换的感觉。

不知有没有数学解法，但计算机搞这种无脑流还是比较方便的，虽然在回退切换路线的时候看起来有点繁琐。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 不知有没有数学解法，还是用空间暴力法一波带走

        if not (len(matrix) and len(matrix[0])):
            return []

        direction = {
            "right": [0, 1],
            "down": [1, 0],
            "left": [0, -1],
            "up": [-1, 0] 
        }
        direction_turn = {
            "right": "down",
            "down": "left",
            "left": "up",
            "up": "right"
        }

        direct = "right"
        i, j = 0, 0
        col = [] 
        visited = set()
        m, n = len(matrix), len(matrix[0])
        while len(col) != m * n:
            if i < 0 or i > m - 1 or j < 0 or j > n - 1 or matrix[i][j] in visited:
                # 超出可接受范围，回退一步，撤销影响，然后走一下正确的步伐
                i -= stepi  
                j -= stepj 
                direct = direction_turn[direct]
                stepi, stepj = direction[direct]
                i += stepi
                j += stepj 
            col.append(matrix[i][j])
            visited.add(matrix[i][j])
            stepi, stepj = direction[direct]
            i += stepi
            j += stepj 

        return col 

执行用时：40 ms, 在所有 Python3 提交中击败了64.88%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.25%的用户

54. 螺旋矩阵 [medium]​

Second Try​

First Try​

54. 螺旋矩阵 [medium]

Second Try

First Try