This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Rotate the image

Given an n by n two-dimensional matrix matrix representing an image. Please rotate the image 90 degrees clockwise.

You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Do not use another matrix to rotate the image.

For details, see the LeetCode official website.

Source: LeetCode link: leetcode-cn.com/problems/ro… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: array traversal

First, look for the rule to find the position to be replaced by the current node. The rule found is that the number at position (x, y) should be placed at position (y, matrix.length – 1-x) after being rotated 90 degrees clockwise. Then, another rule is that when rotated 90 degrees clockwise, In fact, every 4 nodes are rotated once, so the specific processing process is as follows:

  • Start from the first part of the array. X and y are coordinate positions respectively, and the initial values are 0. Count is the total number of all nodes, and last is the value of the current position.
  • Get the nodes that should be replaced according to the rule(nextX, nextY)To determine whether the node has been replaced:
    • If it has been replaced, it traverses the array to find the next node that has not been replaced, initializes x and y as the coordinates of the current node, and temp as the value of the current node, and then performs the next processing.
    • If not, replace the current node’s value with last, replace the previous value with the last record, then update the coordinates of x and y for the current value, update the current position to true to be replaced, and subtract one from count.
  • The condition for the loop to break is that the count is 0, which means that all nodes have been processed.
public class LeetCode_048 {
    public static void rotate(int[][] matrix) {
        boolean[][] flag = new boolean[matrix.length][matrix.length];
        int count = matrix.length * matrix.length;
        int x = 0, y = 0, temp, last = matrix[0] [0];
        while (count > 0) {
            int nextX = y, nextY = matrix.length - 1 - x;
            if (flag[nextX][nextY]) {
                // The next node has been replaced. Look for the next unreplaced node
                for (int i = x; i < matrix.length; i++) {
                    boolean isFound = false;
                    for (int j = 0; j < matrix.length; j++) {
                        if(! flag[i][j]) { x = i; y = j; last = matrix[x][y]; isFound =true;
                            break; }}if (isFound) {
                        break; }}}else {
                // If the next node is not replaced, replace it and mark it as replaced
                temp = matrix[nextX][nextY];
                matrix[nextX][nextY] = last;
                last = temp;
                count--;
                x = nextX;
                y = nextY;
                flag[nextX][nextY] = true; }}}public static void main(String[] args) {
        int[][] matrix = new int[] [] {{1.2.3.4.5}, {6.7.8.9.10}, {11.12.13.14.15}, {16.17.18.19.20}, {21.22.23.24.25}};
        rotate(matrix);
        for (int[] ints : matrix) {
            for (int anInt : ints) {
                System.out.print(anInt + ""); } System.out.println(); }}}Copy the code

May your bad mood last night disappear today when you lift the quilt and pull back the curtain.