在 Java 中旋转 NxN 矩阵

这是破解编码面试中的一个问题。该解决方案表示，程序先旋转外边缘，然后旋转内边缘。但是，我在遵循两个 for 循环的逻辑时遇到了困难。

有人可以解释代码的逻辑吗（例如为什么他们执行“layer top”和“bottom -> left”等四个步骤）？顺便说一句，在编码面试中提出这个问题时，一个人的思维过程会是怎样的？

给定一个由 NxN 矩阵表示的图像，其中的每个像素 图像是4个字节，写一个方法将图像旋转90度。 你能做到这一点吗？

public static void rotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; ++layer) {
        int first = layer;
        int last = n - 1 - layer;
        for(int i = first; i < last; ++i) {
            int offset = i - first;
            int top = matrix[first][i]; // save top

            // left -> top
            matrix[first][i] = matrix[last-offset][first];          

            // bottom -> left
            matrix[last-offset][first] = matrix[last][last - offset]; 

            // right -> bottom
            matrix[last][last - offset] = matrix[i][last]; 

            // top -> right
            matrix[i][last] = top; // right <- saved top
        }
    }
}

Overview

考虑一个样本矩阵可能如下所示：

ABCD
EFGH
IJKL
MNOP

出于解释目的，ABCD 被视为第 0 行，EFGH 被视为第 1 行，依此类推。第 0 行的第一个像素是 A。

另外，当我谈论外壳时，我指的是：

ABCD
E  H
I  L
MNOP

首先让我们看一下移动值的代码。

    int top = matrix[first][i]; // save top

第一行将值缓存在顶部位置。这是指由 [first][i] 标识的矩阵顶行的位置。例如：保存A.

    // left -> top
    matrix[first][i] = matrix[last-offset][first];          

下一部分将值从左侧位置移动到顶部位置。例如：采取M并将其放在A is.

    // bottom -> left
    matrix[last-offset][first] = matrix[last][last - offset]; 

下一部分将值从底部位置移动到左侧位置。例如：采取P并将其放在M is.

    // right -> bottom
    matrix[last][last - offset] = matrix[i][last]; 

下一部分将值从右侧位置移动到底部位置。例如：采取D并将其放在P is.

    // top -> right
    matrix[i][last] = top; // right <- saved top

最后一部分将值从缓存（顶部位置）移动到正确的位置。例如：把A从第一步开始D is.

接下来是循环。

外循环从第 0 行运行到总行数的一半。这是因为当您旋转第 0 行时，它还会旋转最后一行，而当您旋转第 1 行时，它还会旋转倒数第二行，依此类推。

内部循环从行中的第一个像素位置（或列）运行到最后一个像素位置。请记住，对于第 0 行，这是从像素 0 到最后一个像素，但对于第 1 行，这是从像素 1 到倒数第二个像素，因为第一个和最后一个像素作为第 0 行的一部分进行旋转。

因此外循环的第一次迭代使外壳旋转。换句话说：

ABCD
EFGH
IJKL
MNOP

becomes:

MIEA
NFGB
OJKC
PLHD

看看外壳如何顺时针旋转，但内核却没有移动。

然后外循环的第二次迭代导致第二行旋转（不包括第一个和最后一个像素），我们最终得到：

MIEA
NJFB
OKGC
PLHD