在 Java 中旋转 NxN 矩阵

概述

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

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];          

下一部分将值从左侧位置移动到顶部位置。例如：拿起并把它放在原来的地方。MA

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

下一部分将值从底部位置移动到左侧位置。例如：拿起并把它放在原来的地方。PM

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

下一部分将值从右侧位置移动到底部位置。例如：拿起并把它放在原来的地方。DP

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

最后一部分将值从缓存（顶部位置）移动到正确的位置。例如：把从第一步放在哪里。AD

接下来是循环。

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

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

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

ABCD
EFGH
IJKL
MNOP

成为：

MIEA
NFGB
OJKC
PLHD

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

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

MIEA
NJFB
OKGC
PLHD

我正在写这个答案，因为即使在阅读了Jason上面发布的答案之后（这很好，并且确实解决了我的几个问题），我仍然不清楚可变“偏移”在这个逻辑中扮演什么角色，所以花了几个小时来理解这一点，我想与大家分享。

这里使用了许多变量，了解每个变量的重要性非常重要。

如果你看一下变量“first”，它是无用的，它本质上是“层”本身，“first”在整个逻辑中根本没有被修改。所以我删除了“第一个”变量（它的工作原理，请继续阅读）。

为了理解这些值在内部 for 循环的每次迭代中如何变化，我打印了这些变量的值。查看输出，了解当我们在内部 for 循环中从一个角移动到另一个角时，哪些值会发生变化，哪些值在遍历单个图层时保持不变，哪些值仅在我们更改图层时更改。

内循环的一次迭代移动一个块。移动单个图层所需的迭代次数将随着我们向内移动而变化。变量“last”为我们完成了这项工作，它限制了内部循环（限制了内层并阻止我们超越shell，建立在Jason使用的命名法之上）

是时候研究输出了。

我用了6x6矩阵。

Input: 

 315 301 755 542 955 33
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 472 348 104 645 17 273

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =0
buffer = 315
offset = i-layer = 0
Current Status: 

 472 301 755 542 955 315
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 273 348 104 645 17 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =1
buffer = 301
offset = i-layer = 1
Current Status: 

 472 479 755 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 551
 933 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 645 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =2
buffer = 755
offset = i-layer = 2
Current Status: 

 472 479 933 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 755
 645 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =3
buffer = 542
offset = i-layer = 3
Current Status: 

 472 479 933 908 955 315
 943 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 745
 273 348 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =4
buffer = 955
offset = i-layer = 4
Current Status: 

 472 479 933 908 943 315
 348 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =1
buffer = 613
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 233 880 613 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 851 634 97 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =2
buffer = 233
offset = i-layer = 1
Current Status: 

 472 479 933 908 943 315
 348 785 251 880 613 301
 104 609 504 61 233 755
 645 97 706 707 913 542
 17 851 634 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =3
buffer = 880
offset = i-layer = 2
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 504 61 233 755
 645 97 706 707 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =2
last =3
i =2
buffer = 504
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33

很抱歉，除了思考图层，i和偏移量的值如何变化以了解这里到底发生了什么之外，没有其他办法。

最后是代码

这是代码，我首先删除了不必要的内容并添加了所有print语句，以防有人想玩更多。此代码还具有随机矩阵初始化和打印功能：

package com.crackingthecodinginterview.assignments.chap1;

public class Problem6RotateMatrix90 {

    public static void main(String args[]){
        int[][] matrix = new int[6][6];
        initializeMatrix(matrix,6);
        System.out.println("Input: ");
        printMatrix(matrix,6);
        rotate(matrix,6);
        printMatrix(matrix,6);
    }

    public static void rotate(int[][] matrix, int n) {
        for (int layer = 0; layer < n / 2; ++layer) {
            System.out.println("\n--------------Starting an iteration of OUTER FOR LOOP------------------");

            int last = n - 1 - layer;
            for(int i = layer; i < last; ++i) {
                int offset = i - layer;
                int buffer = matrix[layer][i]; // save top
                System.out.println("\n--------------Starting an iteration of inner for loop------------------");
                System.out.println("layer ="+layer);

                System.out.println("last ="+last);
                System.out.println("i ="+i);

                System.out.println("buffer = "+buffer);
                System.out.println("offset = i-layer = "+ offset);

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

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

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

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

                //print
                System.out.println("Current Status: ");
                printMatrix(matrix,6);
                System.out.println("--------------Finished an iteration of inner for loop------------------");
            }
            System.out.println("--------------Finished an iteration of OUTER FOR LOOP------------------");

        }
    }

    public static void printMatrix(int[][] matrix,int n){
        System.out.print("\n");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(" "+matrix[i][j]);
            }
            System.out.print("\n");
        }
    }

    public static void initializeMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=(int) (Math.random() * 1000);
            }
        }
    }

}