Day64: Rotating image (Item no. 48)

This is the 28th day of my participation in Gwen Challenge

Rotated image (Item No. 48)

The title

Given an n by n two-dimensional matrix matrix represents 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. Please do not use another matrix to rotate the image.

Example 1:

Input: matrix = [[1.2.3], [4.5.6], [7.8.9] output: [[7.4.1], [8.5.2], [9.6.3]]
Copy the code

Example 2:

Input: matrix = [[5.1.9.11], [2.4.8.10], [13.3.6.7], [15.14.12.16] output: [[15.13.2.5], [14.3.4.1], [12.6.8.9], [16.7.10.11]]
Copy the code

Example 3:

Input: matrix = [[1] output: [[1]]
Copy the code

Example 4:

Input: matrix = [[1.2], [3.4] output: [[3.1], [4.2]]
Copy the code

Tip:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

link

Leetcode-cn.com/problems/ro…

explain

This one, this one is second grade elementary school learning to find rules.

First, the simplest solution is to create a new array, fill it with the changed data, and then loop through the new array, replacing the original array.

Is there any other way? Apparently there is, and officials offer two ways of thinking 👇 :

1. Single rotation

   A single rotation is when you traverse an element, you flip it four times, updating four positions

2. First it flips vertically, then diagonally

   This idea is a little bit simpler. In reality, flip it up and down, and then draw a diagonal line from the top left to the bottom right, and flip the elements on both sides of the diagonal to get the answer.

In fact, it is to find the law, how to operate to get the final result, is indeed this logic.

Your own answer (borrow arrays)

This is the kind of answer that you should expect, and the logic of flipping is pretty simple.

For example, if the first line is flipped 👇 :

Flip the second line to get 👇 :

Then there is the simple code 👇 :

var rotate = function(matrix) {
  var n = matrix.length
      newMatrix = Array.from({length: n}, () = > new Array(n))
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      newMatrix[j][n - i - 1] = matrix[i][j]
    }    
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      matrix[i][j] = newMatrix[i][j]
    }    
  }
  return matrix
};
Copy the code

There’s nothing to say, just create an array and replace it.

Better way (vertical flip + diagonal flip)

This method is also simple, but it feels much better than the one-step method.

First, flip it up and down, which is easy, but remember you can only flip it in half, and if you flip it all you’re going to be the same again.

And then we flip the diagonal, and since that diagonal doesn’t move, all we have to do is swap x’s and y’s.

The code looks like 👇 :

var rotate = function(matrix) {
  var n = matrix.length
  // Vertical flip
  for (let i = 0; i < ~~(n / 2); i++) {
    for (let j = 0; j < n; j++) {
      [matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]]
    }
  }
  // Invert the diagonal
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
    }
  }
  return matrix
};
Copy the code

The vertical flip is not a row flip, because arrays are complex objects. If you assign them directly, you change the memory address of the reference, so you still need to assign them one by one.

It’s easier to do a diagonal flip, because the number on the diagonal doesn’t need to be flipped, so the number of rotations is gradually reduced, and you just have to do a half flip.

And when you flip it, you just replace x and y.

A better way (one flip)

The derivation process of this method is extremely complicated, and even if I can understand it with my IQ, I should not remember it next time. I give up here, and interested students can look at the official answer, the process is very detailed.

Click here for the official answer

PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)

If you are interested, you can also check out my personal homepage at 👇

Here is RZ