在Java中旋转NxN矩阵
在Java中旋转NxN矩阵
提问于 2014-09-17 12:47:48
这是破解编码面试中的一个问题。解决方案是，程序先旋转外部边，然后旋转内部边。但是，我在理解这两个for循环的逻辑时遇到了问题。
谁能解释一下代码的逻辑(例如，为什么要做"layer < n/2“，以及"left -> 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
}
}
}回答 11
Stack Overflow用户
回答已采纳
发布于 2014-09-17 12:57:56
概述
考虑一个示例矩阵，如下所示：
ABCD
EFGH
IJKL
MNOP出于我的解释的目的，ABCD被认为是行0，EFGH是行1，依此类推。行0的第一个像素是A。
另外，当我谈到外壳时，我指的是：
ABCD
E H
I L
MNOP首先让我们看一下移动值的代码。
int top = matrix[first][i]; // save top第一行将值缓存在顶部位置。这是指由first标识的矩阵的顶行上的位置。例如:保存A。
// left -> top
matrix[first][i] = matrix[last-offset][first]; 下一部分将值从左侧位置移动到顶部位置。例如:将M放在A所在的位置。
// bottom -> left
matrix[last-offset][first] = matrix[last][last - offset]; 下一部分将值从底部位置移动到左侧位置。例如:将P放在M所在的位置。
// right -> bottom
matrix[last][last - offset] = matrix[i][last]; 下一部分将值从右侧位置移动到底部位置。例如:将D放在P所在的位置。
// top -> right
matrix[i][last] = top; // right <- saved top最后一部分将值从缓存(顶部位置)移动到正确的位置。例如:从D所在的第一步开始放置A。
下一个循环。
外部循环从第0行运行到总行数的一半。这是因为当您旋转第0行时，它也会旋转最后一行，而当您旋转第1行时，它也会旋转倒数第二行，依此类推。
内部循环从行中的第一个像素位置(或列)运行到最后一个像素位置。请记住，对于行0，这是从像素0到最后一个像素，但是对于行1，这是从像素1到倒数第二个像素，因为第一个和最后一个像素是作为行0的一部分旋转的。
因此，外部循环的第一次迭代会使外壳旋转。换句话说：
ABCD
EFGH
IJKL
MNOP变成：
MIEA
NFGB
OJKC
PLHD查看外壳如何顺时针旋转，但内核没有移动。
然后，外部循环的第二次迭代导致第二行旋转(不包括第一个和最后一个像素)，我们最终得到：
MIEA
NJFB
OKGC
PLHDStack Overflow用户
发布于 2015-09-07 03:42:49
我之所以写这个答案，是因为即使读了上面Jason发布的答案(它很好，确实解决了我的几个问题)，我仍然不清楚变量“偏移”在这个逻辑中扮演的角色是什么，所以花几个小时来理解它，我想与每个人分享它。
这里使用了许多变量，理解每个变量的重要性是很重要的。
如果你看一下变量'first'，它是没有用的，它本质上是‘层’本身，'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抱歉，除了思考layer、I和offset的值如何变化之外，没有其他方法来理解这里到底发生了什么。
最后是代码
下面的代码中，我首先删除了不必要的内容，并添加了所有的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);
}
}
}
}Stack Overflow用户
发布于 2015-05-25 23:46:50
我刚刚看到有一种通过重构"last -offset“来编写代码的更简单的方法：
public static void rotateInPlace90DegreesClockwise(int[][] matrix) {
int n = matrix.length;
int half = n / 2;
for (int layer = 0; layer < half; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int j = last - offset;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[j][first];
// bottom -> left
matrix[j][first] = matrix[last][j];
// right -> bottom
matrix[last][j] = matrix[i][last];
// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25882480
复制相关文章
相似问题