Вращение матрицы NxN в Java

Question

Это вопрос от Cracking the Coding Interview. В решении говорится, что программа поворачивает внешние края, а затем внутренние края. Однако у меня возникают проблемы с логикой обоих циклов.

Может ли кто-нибудь объяснить логику кода (например, почему они это делают) слой < 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 
     } 
    } 
} 

Answer 1

Обзор

Рассмотрим матрицу образца может выглядеть следующим образом:

ABCD 
EFGH 
IJKL 
MNOP 

Для целей моего объяснения, ABCD рассматривается как строка 0, EFGH является строка 1 , и так далее. Первый пиксель строка 0 является А.

Кроме того, когда я говорю о внешней оболочке, я имею в виду:

ABCD 
E H 
I L 
MNOP 

Сначала давайте посмотрим на код, который перемещает значения.

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

Первая строка кэширует значение в верхнем положении. Это относится к позиции в верхней строке матрицы, идентифицированной [первым] [i]. Например: сохранение 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 

Последняя часть перемещает значение из кеша (то, что было в верхнем положении) в нужное положение. Например: положить A с первого шага, где находится D.

Далее петли.

Внешний цикл работает от строки 0 до половины общего количества строк. Это связано с тем, что когда вы вращаете строку 0, она также вращает последнюю строку, а когда вы вращаете строку 1, она также вращает вторую и последнюю строку и так далее.

Внутренний цикл работает от первого положения (или столбца) пикселя в строке до последнего. Имейте в виду, что для строки 0 это от пикселя 0 до последнего пикселя, но для строки 1 это от пикселя 1 до второго-последнего пикселя, так как первый и последний пиксели вращаются как часть строки 0

Итак, первая итерация внешнего контура заставит внешнюю оболочку вращаться. Другими словами:

ABCD 
EFGH 
IJKL 
MNOP 

становится:

MIEA 
NFGB 
OJKC 
PLHD 

Посмотрите, как внешняя оболочка вращается по часовой стрелке, но внутреннее ядро ​​не перемещается.

Тогда второй итерации внешнего цикла приводит к тому, второй ряд для поворота (за исключением первого и последнего пикселя), и мы в конечном итоге с:

MIEA 
NJFB 
OKGC 
PLHD 

Answer 2

Просто увидел, что есть более простой способ, чтобы написать код рефакторинга «последнее - смещение»:

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

Я пишу этот ответ, потому что даже после прочтения ответа, отправленного Джейсоном выше (это хорошо и не решить несколько вопросов, которые я имел) до сих пор не было ясно мне, какую роль играет переменная смещение в этой логике, поэтому тратить купе e часов, чтобы понять это, я подумал поделиться им со всеми.

Здесь много переменных, и важно понимать значение каждого из них.

Если вы посмотрите на переменную «первым», это бесполезно, это, по сути, сам «слой», «первый» вообще не изменяется во всей логике. Поэтому я удалил «первую» переменную (и она работает, читайте дальше).

Чтобы понять, как каждое из этих значений изменяется на каждой итерации внутреннего цикла, я напечатал значения этих переменных. Взгляните на результат и поймите, какие значения изменяются, когда мы переходим из одного угла в другой во внутреннем цикле for, значения которого остаются постоянными при обходе одного слоя и значения изменяются только при изменении слоя.

Одна итерация внутренней петли перемещает один блок. Число итераций, необходимых для перемещения одного слоя, будет меняться по мере того, как мы идем внутрь. Переменная «последнего» делает эту работу для нас, это ограничивает внутренний контур (ограничивает внутренний слой & останавливает нас от выхода за пределами оболочки, опираясь на номенклатуру Джейсон используется)

времени для изучения выхода.

Я использовал 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 

Извините, но нет другого пути, кроме вдуматься как значения слоя, я и смещения изменения, чтобы понять, что за чертовщина здесь происходит.

Наконец код

Вот код, где я удалил ненужные первый и добавил все операторы печати, в случае, если кто-то хочет больше играть.Этот код также имеет случайную инициализацию матрицы и печать:

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

Самое простое решение:

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

проверить это решение, чтобы сделать это на месте.

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

Вот мое решение в JavaScript, она меняет местами значения между строки и столбца, начиная с верхнего правого края, не собирается внутрь, пока пара снизу левый обменена.

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

Это простое решение, которое отлично работает для меня.

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