旋轉(zhuǎn)圖像

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

題目分析

基于翻轉(zhuǎn)實(shí)現(xiàn)原地旋轉(zhuǎn)

1.翻轉(zhuǎn)形式一上下翻轉(zhuǎn)

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

2.翻轉(zhuǎn)形式二-左右翻轉(zhuǎn)

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

3.翻轉(zhuǎn)形式三-正向?qū)蔷€翻轉(zhuǎn)

4.翻轉(zhuǎn)形式四-反向?qū)蔷€翻轉(zhuǎn)

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

順時(shí)針90度旋轉(zhuǎn)可以看為上下翻轉(zhuǎn)+ 正向?qū)蔷€翻轉(zhuǎn)

基于翻轉(zhuǎn)實(shí)現(xiàn)

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

        /**
         基于翻轉(zhuǎn)實(shí)現(xiàn)
         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++;
                }
            }
        }
   }

基于原地交換實(shí)現(xiàn)旋轉(zhuǎn)

首先我們來看頂點(diǎn)的元素位置是怎么移動(dòng)的,元素1要放到4位置，4要發(fā)放到16，16要放到13位置,13要最終放到1位置，這樣完成了4個(gè)頂點(diǎn)之間的交換,在交換時(shí),可以將1 放到臨時(shí)變量中，然后沿著圖示的方向?qū)?3 放到1位置,16 放到13位置,4放入16位置,temp 元素1 放入4位置;

如果可以將每行或每列的元素坐標(biāo)計(jì)算出來， 那么也可以完成上述類似元素之間的交換，所以，我們要找出頂點(diǎn)之間的坐標(biāo)計(jì)算關(guān)系;
對于元素2來說,它的坐標(biāo)可以通過s1 頂點(diǎn)就算出來, 為array[s1_x][s1_j+1];
對于元素8來說,它的坐標(biāo)可以通過s2頂點(diǎn)計(jì)算出來,為array[s2_x+1][s2_j];
對于元素15來說,它的坐標(biāo)可以通過s3頂點(diǎn)計(jì)算出來,為array[s3_x][s3_j-1];
對于元素9來說,它的坐標(biāo)可以通過s4頂點(diǎn)計(jì)算出來,為array[s4_x-1][s4_j],
這樣就可以將2,8,15,9這幾個(gè)元素進(jìn)行交換,同理，對于綠色標(biāo)記的這幾個(gè)元素也可以通過計(jì)算坐標(biāo)出來進(jìn)行一輪交換;
以上就完成了最外層一圈元素的交換，此時(shí)，需要將對應(yīng)的s1,s2,s3,s4這幾個(gè)頂點(diǎn)索引遞進(jìn)(s1_x++,s1_j++,s2_x++,s2_j--,s3_x--,s3_j--,s4_x--,s4_j++)，進(jìn)行內(nèi)層一圈元素的交換;
那么什么時(shí)候會(huì)退出呢,當(dāng)s1_j > s2_j 時(shí)，即元素全部旋轉(zhuǎn)完畢;

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

基于原地交換實(shí)現(xiàn)

    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length <= 0){
            return ;
        }
              /**
         方法三:基于原地交換
         */
         //四個(gè)頂點(diǎn)坐標(biāo)
         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 個(gè)元素
            for(int i = 0;i < s2_j - s1_j;i++){
                //基于頂點(diǎn)坐標(biāo)根據(jù)偏移量計(jì)算該行或該列其他元素坐標(biāo)
                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++;
         }
    }
    /**
     最外圈中各個(gè)頂點(diǎn)元素交換
     */
    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;
    }
}