Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The rookie is going to continue on 16

I. Title Description:

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.

Input: matrix = [[1, 2, 3], [4 and 6], [7,8,9]] output: [,4,1 [7], [8,5,2], [9,6,3]]Copy the code

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

Ii. Analysis of Ideas:

Rotation in place: We can’t iterate through the array directly because we need to rotate the array in place. First of all, in situ replacement. For a point, it is actually the sequential replacement of four points. Through thinking, it is not difficult to get the coordinate relationship of four points:

  • [x][y]
  • [y][n-1-x]
  • [n-1-y][x]
  • [n-1-x][n-1-y]

So write the temp loop substitution. So the next step is how to determine the cycle range, it can be seen that the number of rows as long as half, and the number of columns turn inward about two less, so write y and ymax cycle control methods.

Non in situ replacement: this is relatively simple, did not write, directly took the official problem solution record, cycle again.

matrix_new[j][n - i - 1] = matrix[i][j];
Copy the code

Flip: this idea did not expect, the official solution of the problem, as long as a horizontal flip and diagonal flip can get the final answer, in fact, the courtyard said it is not complicated, the calculation of horizontal flip + diagonal flip is still

matrix_new[j][n - i - 1] = matrix[i][j];
Copy the code

What’s interesting is that this method is also in situ substitution, and it’s a little bit unclear why.

[matrix[0][0], matrix[1][1]] = [matrix[1[1], matrix[0][0]];
Copy the code

Iii. AC Code:

1.

/ * * *@param {character[][]} board
 * @return {boolean}* /
var rotate = function(matrix) {
    const n = matrix.length
    let x=0,y=0,xmax=n/2,ymax=n-1
    while(x<xmax){
    while(y<ymax){
        temp=matrix[x][y]
        matrix[x][y]=matrix[n-1-y][x]
        matrix[n-1-y][x]=matrix[n-1-x][n-1-y]
        matrix[n-1-x][n-1-y]=matrix[y][n-1-x]
        matrix[y][n-1-x]=temp
        y++
        
    }
    x++
    y=x
    ymax--
    }
    return matrix
};
Copy the code

2. Non-in-situ replacement

var rotate = function(matrix) {
    const n = matrix.length;
    const matrix_new = 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++) {
            matrix_new[j][n - i - 1] = matrix[i][j]; }}for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) { matrix[i][j] = matrix_new[i][j]; }}};Copy the code

3, turn over

var rotate = function(matrix) {
    const n = matrix.length;
    // flip horizontally
    for (let i = 0; i < Math.floor(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]]; }}// The main diagonal is inverted
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; }}};Copy the code