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
2. Look at the answer~
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

3. Look at the answer
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