# Leetcode-D44-array-48 Rotate image & 54 Spiral matrix (review tomorrow)

## 1, Review

1,47. Full arrangement II
It's not bad. The idea is generally right. It's just a little debugging - when size=0, you can't enter the for loop, so you need to judge when size=1, and then directly append (path), and then return

```class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dsf(size,nums,path,res):
for index in range(size):
if index!=0 and nums[index]==nums[index-1]:
continue
if size==1:
res.append(path+[nums[index]])
return
dsf(size-1,nums[:index]+nums[index+1:],path+[nums[index]],res)
nums.sort()
res=[]
path=[]
dsf(len(nums),nums,path,res)

return res
```

## 48. Rotate image

1. Thought of a method of transposing first and then according to the longitudinal axis symmetry in the middle
For the j-th element in the i-th row of the matrix, it appears at the j-th position in the penultimate i-th column after rotation
Try to write the code

3. Note that the rule appears in the j position of the penultimate i column, which is the penultimate!!! No wonder no one uses it. It's better to use the most straightforward one. Transpose it first and then use it symmetrically. Ha ha, ha ha, but it's quite simple to write~

```class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
new_matrix = [[0]*n for _ in range(n)]

for i in range(n):
for j in range(n):
new_matrix[j][n-1-i]=matrix[i][j]

matrix[:]=new_matrix[:]
```

## 54. Spiral matrix (review tomorrow)

1. Matrix again hahaha
2. I thought of a hash table to record whether I passed.
Use recursion to indicate up, down, left and right movement.
3. It's good to think of recursion and try it, but the problem is that it can't

When doing this, I also found another problem, that is, if you return path, you will get None, but if you return directly and take path, you will be fine. I don't understand.

```class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
def clock(begin, l, w, matrix, path):
if begin >= l - begin and begin + 1 >= w - begin and l - begin - 1 <= begin and w - begin - 1 <= begin+1:
return
if begin < l - begin:
for i in range(begin, l - begin):
path += [matrix[begin][i]]
if begin + 1 < w - begin:
for j in range(begin + 1, w - begin):
path += [matrix[j][l - begin-1]]
if l - begin - 1 > begin:
for s in range(l - begin - 1, begin, -1):
path += [matrix[w - begin-1][s-1]]
if w - begin - 1 > begin:
for k in range(w - begin - 1, begin+1, -1):
path += [matrix[k-1][begin]]

clock(begin + 1, l,w, matrix, path)

path = []
clock(0, len(matrix[0]), len(matrix), matrix, path)
return path
```

The answer is very similar to my original idea. Here, the direction vector and the loop with% 4 are very good~

```class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows, columns = len(matrix), len(matrix[0])
visited = [[False] * columns for _ in range(rows)]
total = rows * columns
order = [0] * total

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
row, column = 0, 0
directionIndex = 0
for i in range(total):
order[i] = matrix[row][column]
visited[row][column] = True
nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
directionIndex = (directionIndex + 1) % 4
row += directions[directionIndex][0]
column += directions[directionIndex][1]
return order

```

4. Try to write it yourself~
We still need to look at other people's code to a large extent and summarize it.
(1) Judge whether to return by whether all traversals are completed (in the for loop, record one quantity at a time, and conduct a total of size for loops)
(2) Don't make mistakes in the direction of directions. How do you move it? Change the horizontal axis or the vertical axis. Use% 4 to constantly change direction.
(3) Use the hash matrix visited to record whether it has been accessed
(4) Judge whether the next one has crossed the boundary or has been visited. If so, immediately raise the bow on the original basis and change the direction. If you don't cross the boundary, operate in the original direction.
(5) Iterate again until all are recorded

```class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows,cols = len(matrix),len(matrix[0])
total = rows*cols
res = [0]*total
directions =[[0,1],[1,0],[0,-1],[-1,0]]
row,col=0,0
direction_index = 0
visited=[[False]*cols for _ in range(rows)]
for i in range(total):
res[i] = matrix[row][col]
visited[row][col]=True
nextrow,nextcol = row+directions[direction_index][0],col+directions[direction_index][1]
if nextrow>=rows or nextcol>=cols or visited[nextrow][nextcol]==True:
direction_index = (direction_index+1)%4
row = row+directions[direction_index][0]
col = col +directions[direction_index][1]
return res

```

Keywords: Python leetcode linear algebra

Added by nrg_alpha on Sun, 06 Feb 2022 03:11:03 +0200