48. Rotate the image

Given an n by n two-dimensional matrix matrix represents an image. Please rotate the image 90 degrees clockwise.

You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Please do not use another matrix to rotate the image.

For example, the side length of the first layer is side, select the front side-1 element, let them rotate, the side length of the second layer is side-2, select the front side-2-1 element, and so on.

class Solution:
    def rotate(self, matrix: List[List[int]]) - >None:
        """ Do not return anything, modify matrix in-place instead. """
        n = len(matrix)
        width = n - 1
        for i in range(n//2) :for j in range(i, i+width):
                matrix[i][j], matrix[j][n-i-1], matrix[n-i-1][n-j-1], matrix[n-j-1][i] = \
                    matrix[n-j-1][i], matrix[i][j], matrix[j][n-i-1], matrix[n-i-1][n-j-1]
            width -= 2
Copy the code

54. Spiral matrix

You are given a matrix matrix with m rows and n columns. Please return all elements in the matrix in clockwise spiral order.

Idea: According to the level of simulation, record his upper, lower, left and right boundaries, traversal one layer each time, traversal divided into four situations

  • Left
  • Left =right and top
  • Left
  • Left =right and top=bottom means one element, just add this one to the result
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) - >List[int] :
        m, n = len(matrix), len(matrix[0])
        left, right, top, bottom = 0, n-1.0, m-1
        res = []
        while left<right and top<bottom:
            for i in range(left, right): res.append(matrix[top][i])
            for i in range(top, bottom): res.append(matrix[i][right])
            for i in range(right, left, -1): res.append(matrix[bottom][i])
            for i in range(bottom, top, -1): res.append(matrix[i][left])
            left, right, top, bottom = left+1, right-1, top+1, bottom-1
        if left == right and top < bottom: res.extend(matrix[i][left] for i in range(top, bottom+1))
        elif left < right and top == bottom: res.extend(matrix[top][left:right+1])
        elif left == right and top == bottom: res.append(matrix[top][left])
        return res
Copy the code

498. Diagonal traversal

Given a matrix mat of size m x n, please return all elements of the matrix in an array in the diagonal traversal order.

Train of thought: follow the direction indicated by the arrow. If you go beyond the boundary, change direction until you reach the bottom right corner and stop the simulation

  • If you go up, row minus 1 column plus 1, if you go out of bounds let’s make columns plus 1
  • If you go down, row plus 1 column minus 1, if you go out of bounds, row plus 1
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) - >List[int] :
        upward = True
        m, n = len(mat), len(mat[0])
        i, j = 0.0
        res = []
        whilei! =morj! =n:if 0<=i<m and 0<=j<n:
                res.append(mat[i][j])
            if upward:
                if 0<=i-1<m and 0<=j+1<n:
                    i -= 1
                    j += 1
                else:
                    j += 1
                    upward = False
            else:
                if 0<=i+1<m and 0<=j-1<n:
                    i += 1
                    j -= 1
                else:
                    i += 1
                    upward = True
        return res
Copy the code