Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняГлава 29, давайте рассмотрим простую задачу поворота матрицы.
смысл названия
Требования заголовка очень просты: по заданной двумерной квадратной матрице требуется вернутьМатрица повернута на 90 градусоврезультаты после.
Давайте рассмотрим два примера:
отвечать
Эта анимация понятна с первого взгляда, а это значит, что нам нужно повернуть двумерную матрицу на 90 градусов по часовой стрелке. Мы все прекрасно понимаем смысл этого вопроса, но в заголовке есть ограничение:Мы не можем применять дополнительные массивы, чтобы помочь, что ограничивает использование нашего пространства.
Если такого условного ограничения нет, то на самом деле очень просто, нам нужно только вычислить положение каждой координаты после поворота, мы пересоздаем массив и заполняем его последовательно.
Проигнорируем конкретные данные в матрице и посмотрим на изменения координат до и после поворота матрицы. Вот координаты до поворота матрицы:
После поворота координаты становятся:
Глядя на два рисунка выше, мы видим, что для координаты (i, j) результат, полученный после поворота на 90 градусов, должен быть (j, n-1-i). Здесь n — количество строк.
Получив эту формулу, мы можем продолжить обобщение. Мы находим, что точка в (i, j) повернута к (j, n-1-i). И точка в положении (j, n-1-i) поворачивается на (n-1-i, n-1-j), и аналогично (n-1-i, n-1-j) поворачивается на (n )-1-j, i), и, наконец, мы находим, что (n-1-j, i) возвращается к (i, j) после поворота.
То есть за один оборот (i, j), (j,n-1-i), (n-1-i, n-1-j), (n-1-j, i)Элементы в этих четырех позициях меняются местами друг с другом., и не повлияло на другие местоположения. На самом деле это тоже очень легко понять, потому что данный заголовок представляет собой квадратную матрицу.
Мы можем понять это, взглянув на следующий рисунок:
То есть мыНужно пройти только четверть матрицы, а затем получить 4 позиции, которые обмениваются друг с другом через координаты, а затем обмениваются своими элементами.
код
Код очень простой, всего несколько строк:
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 注意一下范围和下标即可
for i in range(n//2):
for j in range(i, n-1-i):
matrix[i][j], matrix[j][n-1-i], matrix[n-1-i][n-1-j], matrix[n-1-j][i] = \
matrix[n-1-j][i], matrix[i][j], matrix[j][n-1-i], matrix[n-1-i][n-1-j]