LeetCode《初级算法》数组之旋转图像

题目

题目链接：leetcode-cn.com/leetbook/re…

题解

JS 实现

一看到题目，可以按照题目要求得到，从外到内，每层旋转 90 度，直到最内层，最内层的情况是只有一个元素或者有四个元素；

再仔细思考一下的话，会发现矩阵经过对角线交换，然后经过对称线交换后刚好是想要的结果；
于是有以下两种解法；

1、直接按照题目要求解题

递归实现

对整个方阵的每一层都旋转，相当于每次对一个更小方阵的最外层旋转；
递归体：对方阵的最外层旋转；
递归结束条件：方阵行数小于2时结束递归调用；

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

    // matrix 为要变换的矩阵, (start,start) 为矩阵的左上角坐标，(end,end) 为矩阵的左下角坐标
    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);

};
复制代码

非递归实现

所有递归操作都可以用循环实现，只不过比递归更难理解，但是非递归方法相对于递归方法的效率更高；

/**
 * @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++) { // 此层循环实现从最外层向里层递进；
        
        for( let j = i;j < len - 1 - i;j++) { // 难点在于不要忘记在向里层前进的过程中方阵减小了，所以这里是 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;
        }


    }

};
复制代码

2、利用矩阵的性质实现

步骤：

方阵（行数和列数相等的矩阵）先按主对角线（左上角到右下角）对称交换所有元素；
再将方阵左右对称交换所有元素；
最后的结果就是矩阵顺时针旋转90度的结果；

/**
 * @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;
    // 按主对角线交换
    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;
        }
    }

    // 按垂直对称轴左右交换
    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;

        }
    }
};

复制代码