LeetCode Rotation image of the Elementary Algorithm array — JavaScript

The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

JS implementation

As soon as you see the problem, you can say, from the outside to the inside, rotate each layer by 90 degrees, until you get to the innermost layer, and the innermost layer has only one element or four elements;

And if you think about it a little bit more, you’ll see that when you swap the matrices diagonally, and then you swap them symmetrically, that’s exactly what you want; So there are two solutions;

1. Solve the problem directly according to the topic requirements

The recursive implementation

Rotate each layer of the entire matrix, equal to rotate the outermost layer of a smaller matrix each time; Recursive body: rotation of the outermost layer of the square matrix; Recursive end condition: the recursive call ends when the number of square rows is less than 2;

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

    // matrix is the matrix to be transformed, (start,start) is the upper-left coordinate of the matrix, (end,end) is the lower-left coordinate of the matrix
    function rotateOutside(matrix,start,end) {
        let len = end - start + 1;

        if( len >= 2) {

            let temp = null;
            for( let i = 0; i < len -1; i++) { temp = matrix[start][start + i]; matrix[start][start + i] = matrix[end - i][start]; matrix[end - i][start] = matrix[end][end - i]; matrix[end][end - i] = matrix[start + i][end]; matrix[start + i][end] = temp; } rotateOutside(matrix,start+1,end-1);
        }
    }

    rotateOutside(matrix,0,length - 1);

};
Copy the code

Non-recursive implementation

All recursive operations can be implemented with loops, which are just more difficult to understand than recursion, but non-recursive methods are more efficient than recursive methods.

/ * * *@param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    
    let len = matrix.length; 
    const halfLen = Math.floor(len / 2);
    let temp = null;

    for( let i = 0; i < halfLen; i++) {// This layer circulates from the outermost layer to the inner layer;
        
        for( letj = i; j < len -1- i; j++) {// The difficulty is to remember that the square matrix decreases as you move towards the inner layer, so this is j < len-1- I;
            
            temp = matrix[i][j];
            matrix[i][j] = matrix[len - j - 1][i];
            matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
            matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
            matrix[j][len - i - 1] = temp; }}};Copy the code

2. Use the properties of matrix

• The square matrix (a matrix with the same number of rows and columns) first swaps all elements symmetrically along the main diagonal (upper left to lower right);
• Then swap all the elements symmetrically;
• The final result is 90 degrees clockwise rotation of the matrix;

/ * * *@param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    
    const len = matrix.length; 
    let temp = null;
    // Switch on the main diagonal
    for( let i = 0; i < len -1; i++) {for( let j = i + 1; j < len; j++) { temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; }}// Switch left and right along the vertical axis of symmetry
    let halfLen = Math.floor(len / 2);
    for(let i = 0; i < len; i++) {for(let j = 0; j < halfLen; j ++) {const m = len - 1- j; temp = matrix[i][j]; matrix[i][j] = matrix[i][m]; matrix[i][m] = temp; }}};Copy the code

Juejin. Cn/post / 700669…

If you have a better idea of the solution, welcome to discuss ~