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

问题描述

这是破解编码面试"中的一个问题.解决方案说，程序先旋转外部边缘，然后旋转内部边缘.但是，我很难遵循两个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< n/2"以及左->顶部"和底->左"四个步骤等)?附带说明一下，在编码面试中提出这个想法时会如何思考?

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矩阵表示的图像，其中image为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

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

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屋！