旋转图像

https://leetcode.cn/problems/rotate-image/

题目分析

基于翻转实现原地旋转

1.翻转形式一上下翻转

截屏2024-07-14 下午2.34.52.png

2.翻转形式二-左右翻转

截屏2024-07-14 下午2.40.30.png

3.翻转形式三-正向对角线翻转

4.翻转形式四-反向对角线翻转

截屏2024-07-14 下午3.09.24.png

顺时针90度旋转可以看为上下翻转+ 正向对角线翻转

基于翻转实现

    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length <= 0){
            return ;
        }

        /**
         基于翻转实现
         1. 先上下交换
         2. 然后对角线交换
         */
        for(int i = 0;i< matrix.length/2;i++){
            for(int j = 0; j < matrix.length;j++){
                int firstNUm = matrix[i][j];
                int newI = matrix.length - i - 1;
                matrix[i][j] = matrix[newI][j];
                matrix[newI][j] = firstNUm;
            }
        }
        //2.然后对角线交换
        for(int i = 0;i< matrix.length;i++){
            int j = 0;
            while(j < matrix.length){
                if(i == j || j > i){
                    break;
                }else{
                    int newI = j;
                    int newJ = i;
                    int firstNum = matrix[i][j];
                    matrix[i][j] = matrix[newI][newJ];
                    matrix[newI][newJ] = firstNum;
                    j++;
                }
            }
        }
   }

基于原地交换实现旋转

首先我们来看顶点的元素位置是怎么移动的,元素1要放到4位置，4要发放到16，16要放到13位置,13要最终放到1位置，这样完成了4个顶点之间的交换,在交换时,可以将1 放到临时变量中，然后沿着图示的方向将13 放到1位置,16 放到13位置,4放入16位置,temp 元素1 放入4位置;

如果可以将每行或每列的元素坐标计算出来， 那么也可以完成上述类似元素之间的交换，所以，我们要找出顶点之间的坐标计算关系;
对于元素2来说,它的坐标可以通过s1 顶点就算出来, 为array[s1_x][s1_j+1];
对于元素8来说,它的坐标可以通过s2顶点计算出来,为array[s2_x+1][s2_j];
对于元素15来说,它的坐标可以通过s3顶点计算出来,为array[s3_x][s3_j-1];
对于元素9来说,它的坐标可以通过s4顶点计算出来,为array[s4_x-1][s4_j],
这样就可以将2,8,15,9这几个元素进行交换,同理，对于绿色标记的这几个元素也可以通过计算坐标出来进行一轮交换;
以上就完成了最外层一圈元素的交换，此时，需要将对应的s1,s2,s3,s4这几个顶点索引递进(s1_x++,s1_j++,s2_x++,s2_j--,s3_x--,s3_j--,s4_x--,s4_j++)，进行内层一圈元素的交换;
那么什么时候会退出呢,当s1_j > s2_j 时，即元素全部旋转完毕;

截屏2024-07-14 下午5.34.37.png

基于原地交换实现

    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length <= 0){
            return ;
        }
              /**
         方法三:基于原地交换
         */
         //四个顶点坐标
         int s1_i = 0;
         int s1_j = 0;
         int s2_i = 0;
         int s2_j = matrix.length - 1;
         int s3_i = matrix.length - 1;
         int s3_j = matrix[0].length - 1;
         int s4_i = matrix.length - 1;
         int s4_j = 0;
         while(s1_j <= s2_j){
            // 每轮交换外层一圈元素，一共需要交换s2_j - s1_j 个元素
            for(int i = 0;i < s2_j - s1_j;i++){
                //基于顶点坐标根据偏移量计算该行或该列其他元素坐标
                int p1_i = s1_i;
                int p1_j = s1_j +i;
                int p2_i = s2_i +i;
                int p2_j = s2_j;
                int p3_i = s3_i;
                int p3_j = s3_j-i;
                int p4_i = s4_i-i;
                int p4_j = s4_j;
                swap(p1_i,p1_j,p2_i,p2_j,p3_i,p3_j,p4_i,p4_j,matrix);
            }
            //外层一圈元素交换完毕后
            s1_i++;
            s1_j++;
            s2_i++;
            s2_j--;
            s3_i--;
            s3_j--;
            s4_i--;
            s4_j++;
         }
    }
    /**
     最外圈中各个顶点元素交换
     */
    private void swap(int p1_i,int p1_j,int p2_i,int p2_j,int p3_i,int p3_j,int p4_i,int p4_j,int[][] array){
        int temp = array[p1_i][p1_j];
        array[p1_i][p1_j] = array[p4_i][p4_j];
        array[p4_i][p4_j] = array[p3_i][p3_j];
        array[p3_i][p3_j] = array[p2_i][p2_j];
        array[p2_i][p2_j] = temp;
    }
}