Poseemos la mejor respuesta que encontramos online. Nosotros esperamos que te resulte de ayuda y si quieres comentarnos algún detalle que nos pueda ayudar a mejorar puedes hacerlo..
Visión general
Considere que una matriz de muestra podría verse así:
ABCD
EFGH
IJKL
MNOP
Para los propósitos de mi explicación, ABCD se considera como la fila 0, EFGH es la fila 1, y así sucesivamente. El primer píxel de la fila 0 es A.
Además, cuando hablo de la capa exterior, me refiero a:
ABCD
E H
I L
MNOP
Primero veamos el código que mueve los valores.
int top = matrix[first][i]; // save top
La primera línea almacena en caché el valor en la posición superior. Esto se refiere a la posición en la fila superior de la matriz identificada por [first][i]. Por ejemplo: guardar el A.
// left -> top
matrix[first][i] = matrix[last-offset][first];
La siguiente parte mueve el valor de la posición izquierda a la posición superior. Por ejemplo: tomando el M y ponerlo donde el A es.
// bottom -> left
matrix[last-offset][first] = matrix[last][last - offset];
La siguiente parte mueve el valor de la posición inferior a la posición izquierda. Por ejemplo: tomando el P y ponerlo donde el M es.
// right -> bottom
matrix[last][last - offset] = matrix[i][last];
La siguiente parte mueve el valor de la posición derecha a la posición inferior. Por ejemplo: tomando el D y ponerlo donde el P es.
// top -> right
matrix[i][last] = top; // right <- saved top
La última parte mueve el valor de la caché (cuál era la posición superior) a la posición correcta. Por ejemplo: poner el A desde el primer paso donde el D es.
A continuación, los bucles.
El bucle exterior va desde la fila 0 hasta la mitad del número total de filas. Esto se debe a que cuando gira la fila 0, también gira la última fila y cuando gira la fila 1, también gira la penúltima fila, y así sucesivamente.
El bucle interno se extiende desde la primera posición de píxel (o columna) en la fila hasta la última. Tenga en cuenta que para la fila 0, esto es desde el píxel 0 hasta el último píxel, pero para la fila 1, esto es desde el píxel 1 hasta el penúltimo píxel, ya que el primer y último píxel se rotan como parte de la fila 0 .
Entonces, la primera iteración del bucle externo hace que la capa externa gire. En otras palabras:
ABCD
EFGH
IJKL
MNOP
se convierte en:
MIEA
NFGB
OJKC
PLHD
Vea cómo la capa exterior ha girado en el sentido de las agujas del reloj, pero el núcleo interior no se ha movido.
Luego, la segunda iteración del bucle externo hace que la segunda fila gire (excluyendo el primer y último píxeles) y terminamos con:
MIEA
NJFB
OKGC
PLHD
Estoy escribiendo esta respuesta porque incluso después de leer la respuesta publicada por Jason arriba (es agradable y resolvió un par de preguntas que tenía) todavía no me quedaba claro qué papel juega la variable "compensación" en esta lógica, así que Pasando un par de horas para entender esto, pensé en compartirlo con todos.
Aquí se utilizan muchas variables y es importante comprender el significado de cada una.
Si miras la variable 'primero', es inútil, es esencialmente la 'capa' en sí, 'primero' no se modifica en absoluto en toda la lógica. Así que eliminé la 'primera' variable (y funciona, sigue leyendo).
Para comprender cómo cambia cada uno de estos valores en cada iteración del bucle for interno, imprimí los valores de estas variables. Eche un vistazo a la salida y comprenda qué valores cambian cuando nos movemos de una esquina a otra en el bucle for interno, qué valores permanecen constantes mientras atravesamos una sola capa y qué valores cambian solo cuando cambiamos la capa.
Una iteración del bucle interno mueve un solo bloque. La cantidad de iteraciones necesarias para mover una sola capa cambiará a medida que avancemos hacia adentro. La variable 'última' hace ese trabajo por nosotros, restringe el bucle interno (restringe la capa interna y evita que vayamos más allá del caparazón, basándose en la nomenclatura que usó Jason)
Es hora de estudiar el resultado.
He usado matriz de 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
Lo siento, pero no hay otra forma que reflexionar sobre cómo cambian los valores de layer, iy offset para comprender qué diablos está sucediendo aquí.
Finalmente el código
Aquí está el código donde eliminé lo innecesario primero y agregué todas las declaraciones de impresión, en caso de que alguien quiera jugar más. Este código también tiene inicialización e impresión de matriz aleatoria:
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;iAcabo de ver que hay una forma más sencilla de escribir el código refactorizando "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
Comentarios y puntuaciones del post
Si para ti ha sido de ayuda nuestro post, nos gustaría que lo compartas con el resto entusiastas de la programación y nos ayudes a dar difusión a nuestra información.