Поворот матрицы на 90 градусов по часовой стрелке — распространенная проблема на компьютерных и технических собеседованиях. Эта задача может быть особенно интересной, поскольку цель состоит в том, чтобы выполнить поворот на месте, не используя дополнительную память для новой матрицы. В этом руководстве мы рассмотрим, как этого добиться, с четким объяснением и примером кода.

Описание проблемы

Вам дана двумерная матрица A размера n x n, представляющая изображение. Ваша задача — повернуть изображение по часовой стрелке на 90 градусов на месте. Если вы используете дополнительный массив, вы получите только частичную оценку.

Проблема Ограничения

1≤n≤1000

Формат ввода

Двумерная матрица A целых чисел

Формат вывода

Повернутая 2D-матрица

Пример ввода

[
    [1, 2],
    [3, 4]
]

Пример вывода

[
    [3, 1],
    [4, 2]
]

Пример объяснения

После поворота матрицы на 90 градусов:

• 1 переходит на позицию 2
• 2 переходит на 4-ю позицию
• 4 переходит на позицию 3
• 3 переходит на позицию 1

Пошаговое решение

Шаг 1: Транспонируйте матрицу

• Транспонирование матрицы означает преобразование ее строк в столбцы, а столбцов в строки. Это можно сделать, поменяв местами элементы по основной диагонали (с верхнего левого угла на нижний правый).

Шаг 2: поменяйте местами каждую строку

• После транспонирования матрицы следующим шагом будет обращение каждой строки. Это фактически повернет матрицу на 90 градусов по часовой стрелке.

Пример кода

Вот функция JavaScript для выполнения поворота:

function rotateMatrix(A) {
    const n = A.length;

    // Step 1: Transpose the matrix
    for (let i = 0; i 





  
  
  Пояснение Кодекса



  
  
  Транспонировать матрицу:

• Проходим по матрице, используя два вложенных цикла.
• Поменяйте местами элементы A[i][j] и A[j][i], чтобы транспонировать матрицу.

Переверните каждую строку:

• Используйте встроенный методverse(), чтобы перевернуть каждую строку транспонированной матрицы.

Верните повернутую матрицу:

• После транспонирования и обращения каждой строки матрица поворачивается на 90 градусов по часовой стрелке.

Заключение

Вращение матрицы на месте — это ценный навык, который демонстрирует ваше понимание манипуляций с массивами и алгоритмов на месте. Транспонируя матрицу, а затем переворачивая каждую строку, вы можете добиться желаемого поворота, не используя дополнительного пространства. Практикуйте этот метод, чтобы улучшить свои способности решать проблемы на технических собеседованиях и в задачах по программированию.