在 Java 中旋转 NxN 矩阵 [英] Rotating a NxN matrix in Java

问题描述

这是一个来自 Cracking the Coding Interview 的问题.解决方案说程序先旋转外边缘，然后旋转内边缘.但是，我无法遵循两个 for 循环的逻辑.

This is a question from Cracking the Coding Interview. The solution says that the program rotates the exterior edges, then the interior edges. However, I'm having trouble following the logic of both the for loops.

有人能解释一下代码的逻辑吗(例如他们为什么要做layer top"和bottom -> left"等四个步骤)?顺便提一下，在编码面试中提出这个问题时，一个人的思维过程是怎样的?

Could somebody explain the logic of the code (e.g. why they do "layer < n/2" and the four steps of "left -> top" and "bottom -> left" etc)? On a side note, how would one's thought process be when coming up with this during a coding interview?

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

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

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
        }
    }
}

推荐答案

概览

考虑一个示例矩阵可能如下所示:

Consider a sample matrix could look like this:

ABCD
EFGH
IJKL
MNOP

为了便于说明，ABCD 被视为第 0 行，EFGH 被视为第 1 行，依此类推.第 0 行的第一个像素是 A.

For the purposes of my explanation, ABCD is considered as row 0, EFGH is row 1, and so on. The first pixel of row 0 is A.

另外，当我谈到外壳时，我指的是:

Also, when I talk about the outer shell, I am referring to:

ABCD
E  H
I  L
MNOP

首先让我们看看移动值的代码.

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

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

The first line caches the value in the top position. This refers to the position on the top row of the matrix identified by [first][i]. Eg: saving the A.

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

下一部分将值从左侧位置移动到顶部位置.例如:将 M 放在 A 所在的位置.

The next part moves the value from the left position into the top position. Eg: taking the M and putting it where the A is.

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

下一部分将值从底部位置移动到左侧位置.例如:将 P 放在 M 所在的位置.

The next part moves the value from the bottom position into the left position. Eg: taking the P and putting it where the M is.

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

下一部分将值从右侧位置移动到底部位置.例如:将 D 放在 P 所在的位置.

The next part moves the value from the right position into the bottom position. Eg: taking the D and putting it where the P is.

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

最后一部分将值从缓存(顶部位置)移动到正确的位置.例如:将第一步中的 A 放在 D 所在的位置.

The last part moves the value from the cache (what was the top position) into the right position. Eg: putting the A from the first step where the D is.

接下来是循环.

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

The outer loop runs from row 0 to half the total number of rows. This is because when you rotate row 0, it also rotates the last row and when you rotate row 1, it also rotates the second-to-last row, and so on.

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

The inner loop runs from the first pixel position (or column) in the row to the last. Keep in mind that for row 0, this is from pixel 0 to the last pixel, but for row 1, this is from pixel 1 to the second-to-last pixel, since the first and last pixels are rotated as part of row 0.

所以外循环的第一次迭代使外壳旋转.换句话说:

So the first iteration of the outer loop makes the outer shell rotate. In other words:

ABCD
EFGH
IJKL
MNOP

变成:

MIEA
NFGB
OJKC
PLHD

看看外壳是如何顺时针旋转的，而内核却没有移动.

See how the outer shell has rotated clockwise, but the inner core has not moved.

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

Then the second iteration of the outer loop causes the second row to rotate (excluding the first and last pixels) and we end up with:

MIEA
NJFB
OKGC
PLHD

这篇关于在 Java 中旋转 NxN 矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！