Rotazione di una matrice NxN in Java

Question

Questa è una domanda da Cracking the Coding Interview. La soluzione dice che il programma ruota i bordi esterni, quindi i bordi interni. Tuttavia, ho problemi a seguire la logica di entrambi i cicli for.

Qualcuno potrebbe spiegare la logica del codice (ad esempio perché "strato < n/2" ei quattro passaggi di "sinistra -> alto" e "in basso -> lasciato" ecc.)? In una nota a margine, come sarebbe il processo di pensiero di una persona quando si presentasse questo durante un'intervista di codifica?

Data un'immagine rappresentata da una matrice NxN, dove ogni pixel dell'immagine è 4 byte, scrivere un metodo per ruotare l'immagine di 90 gradi. Puoi farlo a posto?

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

Answer 1

Panoramica

consideri una matrice del campione potrebbe assomigliare a questo:

ABCD 
EFGH 
IJKL 
MNOP 

Ai fini della mia spiegazione, ABCD è considerato fila 0, EFGH è riga 1 , e così via. Il primo pixel di fila 0 è A.

Inoltre, quando parlo di guscio esterno, mi riferisco a:

ABCD 
E H 
I L 
MNOP 

prima cosa diamo un'occhiata al codice che sposta i valori.

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

La prima riga memorizza nella cache il valore nella posizione superiore. Questo si riferisce alla posizione sulla prima riga della matrice identificata da [prima] [i]. Ad esempio: salvataggio di A.

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

La parte successiva sposta il valore dalla posizione sinistra nella posizione superiore. Ad esempio: prendendo il M e mettendolo dove è lo A.

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

La parte successiva sposta il valore dalla posizione inferiore alla posizione sinistra. Ad esempio: prendendo il P e mettendolo dove è lo M.

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

La parte successiva sposta il valore dalla posizione destra nella posizione inferiore. Ad esempio: prendendo il D e mettendolo dove è lo P.

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

L'ultima parte sposta il valore dalla cache (che era la posizione in alto) nella posizione corretta. Ad es .: mettere il A dal primo passo in cui è lo D.

Avanti i cicli.

Il ciclo esterno va dalla riga 0 alla metà del numero totale di righe. Questo perché quando si ruota la riga 0, ruota anche l'ultima riga e quando si ruota la riga 1, ruota anche la penultima riga e così via.

Il ciclo interno viene eseguito dalla prima posizione (o colonna) del pixel nella riga all'ultimo. Tieni presente che per la riga 0, questo è dal pixel 0 all'ultimo pixel, ma per la riga 1, questo è dal pixel 1 al penultimo pixel, poiché il primo e l'ultimo pixel vengono ruotati come parte della riga 0

Quindi la prima iterazione del ciclo esterno fa ruotare il guscio esterno. In altre parole:

ABCD 
EFGH 
IJKL 
MNOP 

diventa:

MIEA 
NFGB 
OJKC 
PLHD 

vedere come il guscio esterno è ruotato in senso orario, ma il nucleo interno non si è mosso.

Poi la seconda iterazione del ciclo esterno fa sì che la seconda fila di ruotare (escluso il primo e l'ultimo pixel) e si finisce con:

MIEA 
NJFB 
OKGC 
PLHD 

Answer 2

appena visto che c'è un modo più semplice per scrivere il codice refactoring "ultima - 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 
      } 
     } 
    } 

Answer 3

sto scrivendo questa risposta perché, anche dopo aver letto la risposta pubblicato da Jason sopra (è bello e ha risolto un paio di domande che avevo) non era ancora chiaro per me che ruolo gioca la compensazione variabile in questa logica, quindi spendere un accoppiamento e di ore per capire questo ho pensato di condividerlo con tutti.

Qui ci sono molte variabili usate ed è importante capire il significato di ognuna.

Se si guarda la variabile "prima", è inutile, è essenzialmente il "livello" stesso, "prima" non viene affatto modificata nell'intera logica. Quindi ho rimosso la variabile 'prima' (e funziona, leggi avanti).

Per comprendere come ciascuno di questi valori cambia in ogni iterazione del ciclo interno per ho stampato i valori di queste variabili. Dai un'occhiata all'output e comprendi quali valori cambiano quando ci spostiamo da un angolo all'altro nel ciclo for interno, i cui valori rimangono costanti mentre attraversi un singolo livello e quali valori cambiano solo quando cambiamo il livello.

Un'iterazione dell'anello interno sposta un solo blocco. Il numero di iterazioni necessarie per spostare un singolo livello cambierà mentre procediamo verso l'interno. La variabile 'ultima' fa questo lavoro per noi, limita il ciclo interno (limita lo strato interno & ci impedisce di andare oltre la shell, sulla base della nomenclatura usata Jason)

Tempo di studiare l'uscita.

Ho usato la matrice 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 

dispiace, ma non c'è modo diverso per riflettere su come i valori di livello, io e il cambiamento di offset per capire cosa diavolo sta succedendo qui.

Infine il codice

Ecco il codice in cui ho tolto prima inutili e ha aggiunto tutte le dichiarazioni di stampa, nel caso in cui se qualcuno vuole giocare di più.Questo codice ha anche l'inizializzazione di matrice casuale e stampa:

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

} 

Answer 4

La soluzione più semplice è:

int[][] a = { {00,01,02 }, { 10,11,12} ,{20,21,22}}; 
System.out.println(" lenght " + a.length); 

int l = a.length; 

for (int i = 0; i <l; i++) { 

    for (int j = l - 1; j >= 0; j--) { 
     System.out.println(a[j][i]); 
    } 
} 

Answer 5

controllo questa soluzione per farlo al suo posto.

public void rotateMatrix(Pixel[][] matrix) { 

    for (int i = 0; i < matrix.length/2; i++) { 

     for (int j = 0; j < matrix.length - 1 - 2 * i; j++) { 
      Pixel tmp = matrix[j + i][matrix.length - 1 - i]; 
      matrix[j + i][matrix.length - 1 - i] = matrix[i][j + i]; 
      matrix[i][j + i] = matrix[matrix.length - 1 - j - i][i]; 
      matrix[matrix.length - 1 - j - i][i] = matrix[matrix.length - 1 - i][matrix.length - 1 - j - i]; 
      matrix[matrix.length - 1 - i][matrix.length - 1 - j - i] = tmp; 
     } 
    } 
} 

Answer 6

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    int n = 5; //5x5 matrix 
    int[][] matrixInitial = initMatrix(n); 
    int[][] matrixFinal = rotate(matrixInitial, n); 
    System.out.println(matrixFinal.length); 

    int m = 4; //4x4 matrix 
    int[][] matrixInitial2 = initMatrix(m); 
    int[][] matrixFinal2 = rotate(matrixInitial2, m); 
    System.out.println(matrixFinal2.length); 
} 

private static int[][] rotate(int[][] matrixInitial, int n) { 
//it is much like square layers. each layer will be read and rotated 
    int layerCount = (n + 1)/2; 
    System.out.println("n: " + n + " layerCount: " + layerCount); 
    int[][] matrixFinal = new int[n][n]; 
    if (n % 2 == 1) { // for odd # layers the centre does not move 
     matrixFinal[n/2][n/2] = matrixInitial[n/2][n/2]; 
     layerCount -= 1; 
    } 

    for (int i = 0; i < layerCount; i++) { 
     int width = n - (2 * i); // width of the layer 
     System.out.println("width: " + width); 
     int[] top = new int[width]; // read top 
     for (int j = 0; j < width; j++) { 
      top[j] = matrixInitial[i][i + j]; 
     } 
     System.out.println("top: " + Arrays.toString(top)); 

     //OK TOP TO RIGHT 

     for (int j = 0; j < width; j++) { // move top to right 
      matrixFinal[j+i][width-1+i] = top[j]; 
     } 

     int[] tempLeft = new int[width]; // left will be read backwards 
     for (int j = 0; j < width; j++) { // reverse the temp 
      tempLeft[j] = matrixInitial[i + j][i]; 
     } 

     int[] left = new int[width]; 
     int indexTemp = 0; 
     for (int j = width-1; j >= 0; j--) { // move temp to left 
      left[indexTemp++] = tempLeft[j]; 
     } 
     System.out.println("left: " + Arrays.toString(left)); 

     //OK LEFT TO TOP 

     for (int j = 0; j < width; j++) { // move left to top 
      matrixFinal[i][j + i] = left[j]; 
     } 

     int[] bottom = new int[width]; read bottom 
     for (int j = 0; j < width; j++) { 
      bottom[j] = matrixInitial[width - 1 + i][j + i]; 
     } 
     System.out.println("bottom: " + Arrays.toString(bottom)); 

     //OK BOTTOM TO LEFT 

     for (int j = 0; j < width; j++) { // move bottom to left 
      matrixFinal[j+i][i] = bottom[j]; 
     } 

     int[] tempRight = new int[width]; // right will be read backwards 
     for (int j = 0; j < width; j++) { 
      tempRight[j] = matrixInitial[j + i][width - 1 + i]; 
     } 
     int[] right = new int[width]; //reverse the temp 
     int indexTemp2 = 0; 
     for (int j = width; j > 0; j--) { 
      right[indexTemp2++] = tempRight[j - 1]; 
     } 
     System.out.println("right: " + Arrays.toString(right)); 

     //OK RIGHT TO BOTTOM 
     for (int j = 0; j < width; j++) { // move right to bottom 
      matrixFinal[width-1+i][j + i] = right[j]; 
     } 

    } 
    for (int i = 0; i < n; i++) { 
     System.out.println(Arrays.toString(matrixFinal[i])); 
    } 
    return matrixFinal; 
} 

private static int[][] initMatrix(int n) { // init the matrix 
    int[][] matrix = new int[n][n]; 
    int fill = 0; 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < n; j++) { 
      matrix[i][j] = fill++; 
     } 
    } 

    for (int i = 0; i < n; i++) { 
     System.out.println(Arrays.toString(matrix[i])); 
    } 
    System.out.println("******"); 
    return matrix; 
} 

Answer 7

Ecco mia soluzione in JavaScript, scambia valori tra una riga ed una colonna a partire dal bordo superiore destro, andando verso l'interno fino a quando la coppia inferiore-sinistra viene scambiato.

function rotateMatrix(arr) { 
    var n = arr.length - 1; 

    for (var i = 0; i < n; i++) { 
     for (var j = 0; j < n - i; j++) { 
      var temp = arr[i][j]; 

      arr[i][j] = arr[n - j][n - i]; // top row 
      arr[n - j][n - i] = temp; // right column 
     } 
    } 

    return arr; 
} 

Answer 8

Ecco una soluzione semplice che funziona perfettamente per me.

private int[][] rotateMatrix(int[][] matrix) 
    { 
     for(int i=0;i<matrix.length-1;i++) 
     { 
      for(int j =i;j<matrix[0].length;j++) 
      { 
       if(i!=j) { 
        int temp = matrix[i][j]; 
        matrix[i][j] = matrix[j][i]; 
        matrix[j][i] = temp; 
       } 
      } 
     } 
     return matrix; 
    }