LeetCode琅琊榜第十五层-旋转图像

LeetCode48.旋转图像

难度:中等

博主空间与往期博客

 题目链接

---

目录

作者原始思路

暴力解法

思路与代码简述

问题

反省

官方解法-等效替代法

方法1-暴力求解

方法目的

方法思想

方法图示

方式实现

方法分析

方法2-原地变化

方法思想

推导过程

代码实现

代码分析

方法3-翻转代替旋转

方法思想

推导过程

方法实现

方法分析

结论

---

作者原始思路 暴力解法

class Solution {
    public void rotate(int[][] matrix) {
        var temp = new int[matrix.length][matrix.length];
        for (int i = 0,n = 0; i < matrix.length && n < matrix.length; i++,n++) {
            for (int j = 0,m = matrix.length - 1; j < matrix.length && m > -1; j++,m--) {
                temp[i][j] = matrix[m][n];
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            System.arraycopy(temp[i], 0, matrix[i], 0, matrix.length);
        }
    }
}

思路与代码简述

• 我们从示例中可以看出,将列表中的元素顺时针旋转90°,就是自下而上的元素变成自左向右的元素,即以列形式的[7,4,1]变成以行形式的[7,4,1]
• 我们不妨建立一个辅助数组temp,按照上面的思路将元素赋值到temp
• 最后将temp里面的元素放回原数组matrix中

问题

• 这种方法需要用到一块额外的空间,没有完成题目中所给出的]请不要使用另一个矩阵来旋转图像的要求'

反省

• 作者的算法虽然可以写出来,但是,这种算法没有推断出最重要的表达式,算法达到了瓶颈,故是较差的

---

官方解法-等效替代法 方法1-暴力求解 方法目的

求出主要的数学表达式

方法思想

利用一个辅助数组,将转换后的结果放入辅助数组中,最后放回原数组中

方法图示

方式实现

class Solution {
    public void rotate(int[][] matrix) {
        var newMatrix = new int[matrix.length][matrix.length];
        var n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newMatrix[j][n - 1 - i] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            System.arraycopy(newMatrix,0,matrix,0,n);
        }
    }
}

方法分析

• 这个方法与作者原始思路是一样的,但是这个方法里面的赋值方式有所不同,即,该方法水平遍历matrix数组,竖直赋值newMatrix数组(如上图所示)
• 由代码中的嵌套for可得,matrix[i][j]就是一行一行的水平遍历
• 当我们在内层循环时,j变i不变,即列变行不变,由于我们是竖直赋值到newMatrix数组的,所以,我们要保证列不变行变,即我们要用i去表示列,j去表示行
• 由题目所给案例得,第一行的元素都在最后一列中,即 列 = (matrix.length - 1) ,第二行在倒数第二列 , 即 列 = (matrix.length - 2) 不妨推出 列 = (matrix - 1 - i)
• 由于该矩阵一定是一个正方形,再题目所给案例得,我们发现 行 = j
• 最终,我们得到了关键表达式  即 matrix[j][n - 1 - i] = matrix[i][j] 当row = i,col = j时,我们换算成 matrix[col][n - 1 - row] = matrix[row][col]

方法2-原地变化 方法思想

• 通过关键表达式从而推算出元素应该如何变换

推导过程

• 1.matrix[col][n - 1 - row] = matrix[row][col]由该关键表达式可知,后面的位置覆盖了前面的位置,所以,我们需要把前面位置的元素放入辅助变量保存起来
• 2.temp = matrix[col][n - 1 - row]
• 3.由于(row,col)这个位置的元素去了(col,n-1-row)位置,所以也应该有元素去(row,col)的位置,否则会出现相同的元素,但是为了便于推导的简单性,我们先不选择这种方向,我们朝另一个方向,即(col,n-1-row)的元素应该去哪
• 4.当row = col, col = n - 1 - row,不妨得出 matrix[n - 1 - row][n - 1 - col] =  matrix[col][n - 1 - row]
• 5.当row = n - 1 - row,col = n - 1 - col,不妨得出matrix[n - 1 - col][row] = matrix[n - 1 -row][n - 1 - col]
• 6.当row = n - 1 - col , col = row,不妨得出matrix[row][col] = matrix[n - 1 - col][row]
• 7.结果我们发现,这四个元素相互覆盖最终完成交换
• 8.注意:千万别合并公因式,不然推不出来

代码实现

class Solution {
    public void rotate(int[][] matrix) {
        var n = matrix.length;
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < (n+1)/2; j++) {
                var temp = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1  - j] = temp;
            }
        }
    }
}

代码分析

• 1.我们可以发现,推导出来的顺序和实际上写的顺序不同,因为上面已经提及到了,推到的顺序时反方向的,所以,我们将推导的公式顺序做出对应的更改即可
• 2.注意:最开始的matrix[j][n - 1 - i]是被覆盖了的,他最原始的元素被保存到了temp中,所以,为了四个能全部交换,我们需要用到temp
• 3.循环次数的图解
  • 3.1图的构建
  • 3.2构建过程
  • 我们从箭头中看出,这就是暴力解法中的赋值规律,我们只是将赋值后的位置元素保存了起来,而里面的逻辑就是完成这一连串的覆盖
  • 此外,我们外层循环只需要做蓝色部分即可,因为当红色箭头有了之后,推导出来的公式就会将黄蓝绿箭头完成
  • 所以得出了对应的i,j情况

方法3-翻转代替旋转 方法思想

• 先将元素进行上下翻转.再沿写斜对角线交换元素

推导过程

• 上下交换后,下面变成 matrix[n - 1 - row][col] = matrix[row][col]
• 对角线交换后,变成 matrix[n - 1 - row][col] = matrix[col][n - 1 - row]
• 所以下面就是matrix[col][n - 1 - row]  = matrix[row][col],恰好满足关键式
• 注意:虽然下面被matrix[row][col]覆盖,但是该位置的表示方式还是matrix[n - 1 - row][col],不可以用matrix[row][col]表示,两个地方不一样

方法实现

class Solution {
    public void rotate(int[][] matrix) {
        var n = matrix.length;
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n; j++) {
                var temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - i][j];
                matrix[n - 1 - i][j] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                var temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

方法分析

• 1.第一个循环是上下进行交换
• 2.第二个循环是沿对角线进行交换,交换的思路类似于数学的反函数
• 3.交换思路如图所示,通过图示即可得到为什么j < i

---

结论

        旋转图像的等效替代方法,更具体的来说就是如何通过两个图像将其转换成同一个图像的转换,再通过具体的数学表达式推出更快捷的方法,通常常常与图相结合,最后我来总结最重要的几点

        1.关键式的推导

                2.一系列公式的推导

                        3.转换思想

                                4.如何用翻转替代旋转