Given a positive integer n
, generate an n x n
matrix
filled with elements from 1
to n2
in spiral order.
Example 1:
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 20
Ideas: 跟[LeetCode] 54. Spiral Matrix_Medium tag: array, DFS 的idea一样,只是将visited去掉,可以直接用返回的ans来标记是否visited过
T: O(m * n) S: O(1)
class Solution: def generateMatrix(self, n: int) -> List[List[int]]: self.n = n self.matrix = [[-1] * n for _ in range(n)] self.dirs = [(0, 1), (1, 0), ( 0, -1), (-1, 0)] self.helper(0, 0, 0, 1) return self.matrix def helper(self, i, j, dire, num): self.matrix[i][j] = num nr, nc = i + self.dirs[dire][0], j + self.dirs[dire][1] if 0 <= nr < self.n and 0 <= nc < self.n and self.matrix[nr][nc] == -1: self.helper(nr, nc, dire, num + 1) else: new_dir = (dire + 1) % 4 nr, nc = i + self.dirs[new_dir][0], j + self.dirs[new_dir][1] if 0 <= nr < self.n and 0 <= nc < self.n and self.matrix[nr][nc] == -1: self.helper(nr, nc, new_dir, num + 1)