“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Title link: 48. Rotate the image

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 and 6], [7,8,9]] output: [,4,1 [7], [8,5,2], [9,6,3]]Copy the code

Example 2

Input: matrix = [,1,9,11 [5],,4,8,10 [2], [13,3,6,7], [15,14,12,16]] output: [,13,2,5 [15], [14,3,4,1], [12,6,8,9], [16,7,10,11]]Copy the code

prompt

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

The code template

/ * * *@param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {};
Copy the code

solution

After reading the question, you may have noticed that the question is accentuated by three words please don’t

Please don’t use another matrix to rotate the image, not a matrix, okay? Why don’t I just use a two-dimensional array? This is a little bit off topic, the implementation of this two-dimensional matrix in the code is a two-dimensional array, so the implication is don’t use extra space, you need to modify the two-dimensional array in place, what if you use extra space? That’s a lot more maneuverable

// Write an arbitrary one
var rotate = function (matrix) {
  const n = matrix.length; // Because n x n matrix
  const temp = new Array(n).fill(0).map(() = > new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      temp[j][n - i - 1] = matrix[i][j]; }}return temp;
  / / if the [[1, 2, 3], [4 and 6], [7,8,9]]
  / / will [,4,1 [7], [8,5,2], [9,6,3]]
};
Copy the code

Void does not return a value in leetcode. The test is to see if you have changed the value of the parameter passed into the function (there is a way, that is, to iterate through the matrix and assign the value), so the difficulty of this problem is to TP in place. How to do that?

It doesn’t matter if you can’t do it in extra auxiliary space, we can see how the rotation of the matrix by 90 degrees works, as follows

How can [1,2,3] move over without changing the position of [3,6,9]?

If you have learned linear algebra, you probably know that the transpose of a matrix, you can swap rows and columns, and here to help you review linear algebra, how to find the transpose matrix

[1, 2, 3] [0, 1],4,7 [1] [4 and 6] x [0, 0] =,5,8 [2],8,9 [7] [0, 1],6,9 [3]Copy the code

The identity matrix of size N, the original matrix x, is actually a diagonal inversion, which helps us to do a row and row inversion in place, and then a mirror operation can solve the problem

,4,1,4,7 [1] [7],5,8 [2] - > [8,5,2],6,9 [3],6,3 [9]Copy the code

So the solution to this problem is

var rotate = function (matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      consttemp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; }}for(let i = 0; i < n; i++) { matrix[i].reverse(); }};// Leetcode's solution is only half reversed, but that's enough
Copy the code

conclusion

I didn’t expect Leetcode to see part of linear algebra, but that knowledge has been lost over time