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