59. 螺旋矩阵 II [hard]

59. 螺旋矩阵 II [hard]

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

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

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

通过次数40,970 | 提交次数52,683

First Try

2020-07-28

还是跟0054一样的思路，直接模拟贪吃蛇一路往前走。并且由于可以直接在rv中进行标记是否访问过，不需要额外提供visited矩阵。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        dir_idx = 0 
        i, j = 0, 0 
        rv = [[""] * n for _ in range(n)]

        for val in range(1, n ** 2 + 1):
            rv[i][j] = val 
            step_i, step_j = directions[dir_idx]
            ni, nj = i + step_i, j + step_j 
            if ni < 0 or ni >= n or nj < 0 or nj >= n or rv[ni][nj] != "":
                dir_idx = (dir_idx + 1) % 4 
                step_i, step_j = directions[dir_idx]
            i, j = i + step_i, j + step_j 
        
        return rv 

• 执行用时：48 ms, 在所有 Python3 提交中击败了22.06%的用户
• 内存消耗：13.5 MB, 在所有 Python3 提交中击败了14.29%的用户