Fırlanma LeetCode Həlli ilə matrisin əldə edilib-edilmədiyini müəyyən edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic AmazonBaxılıb 17

Problem bəyanat

Matrisin fırlanma yolu ilə əldə edilib-edilmədiyini müəyyənləşdirin LeetCode Həlli – İki verilmişdir n x n ikili matrislər mat və target, qayıt true etmək mümkündürsə mat bərabərdir target by fırlanan mat in 90 dərəcə artımvə ya false başqa cür.

Nümunələr

Fırlanma LeetCode Həlli ilə matrisin əldə edilib-edilmədiyini müəyyən edin

Input:

 mat = [[0,1],[1,0]], target = [[1,0],[0,1]]

Çıxış:

 true

Explanation:

We can rotate mat 90 degrees clockwise to make mat equal target.

 

Fırlanma LeetCode Həlli ilə matrisin əldə edilib-edilmədiyini müəyyən edinPin

Input:

 mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]

Çıxış:

 true

Explanation:

We can rotate mat 90 degrees clockwise two times to make mat equal target.

Yanaşma

Brute Force yanaşması

İlk ağla gələn yanaşma matrisi fırladıb hədəf matrislə bərabər olub-olmamasından asılı olmayaraq müqayisə etməkdir. Yuxarıdakı prosesi 4 dəfə təkrarlaya bilərik, çünki 4 dəfədən sonra matris özünü təkrarlayacaqdır. The bu yanaşma üçün zaman mürəkkəbliyi O(4*n*n). Burada matrisi fırlatmaq üçün 4 dəfə keçirik, Bunu yalnız bir keçiddən istifadə etməklə etmək olarmı, Baxaq!

Optimal yanaşma

Biz bunu bir keçiddə edə bilərik, Bir keçiddə, matrisi 4 dəfə keçdiyimiz yuxarıdakı yanaşmadan fərqli olaraq, mümkün olan dörd fırlanmanın hamısını müqayisə edə bilərik.

Dörd növbə üçün şərtlər:

  1. matrix[i][j] = hədəf[i][j], əgər verilmiş matris hədəfə bərabərdirsə.
  2. matris[i][j] = hədəf[j][n-1-i] , əgər verilmiş matris saat istiqamətində fırlanırsa, 1 dəfə.
  3. matris[i][j] = hədəf[n-1-i][n-1-j] , əgər verilmişdirsə matris saat əqrəbi istiqamətində 2 dəfə fırlanır.
  4. matris[i][j] = hədəf[n-1-j][i] , o, verilmiş matris saat əqrəbi istiqamətində 3 dəfə fırlanır.

Yuxarıdakı 4 şərti birində yoxlasaq xain, sonra biz bütün mümkün fırlanmaları yoxladıq, əgər onlardan hər hansı biri doğrudursa, hədəfin mümkün olması deməkdir.

Daha yaxşı başa düşmək üçün koda baxaq.

Matrisin fırlanma yolu ilə əldə edilib-edilmədiyini müəyyən etmək üçün kod

C ++ kodu

class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        bool p=true,q=true,r=true,s=true;
        // four variables to check whether target is any rotation of matrix or not.
        
        int n = mat.size();
        int m = mat[0].size();
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]!=target[i][j]){p=false;}
                if(mat[i][j]!=target[n-j-1][i]){q=false;}
                if(mat[i][j]!=target[n-1-i][n-1-j]){r=false;}
                if(mat[i][j]!=target[j][n-1-i]){s=false;}
            }
        }
        
        return p|q|r|s;
        //if any of them is true , means we have find one rotation which equals target.
    }
};

Java kodu

class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        boolean p=true,q=true,r=true,s=true;
        // four variables to check whether target is any rotation of matrix or not.
        
        int n = mat.length;
        int m = mat[0].length;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]!=target[i][j]){p=false;}
                if(mat[i][j]!=target[n-j-1][i]){q=false;}
                if(mat[i][j]!=target[n-1-i][n-1-j]){r=false;}
                if(mat[i][j]!=target[j][n-1-i]){s=false;}
            }
        }
        
        return p|q|r|s;
        //if any of them is true , means we have find one rotation which equals target.
    }
}

Rotasiya ilə matrisin əldə edilib-edilmədiyini müəyyən etmək üçün mürəkkəblik təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

Matrisdən yalnız bir dəfə keçdiyimiz üçün,  bu zaman mürəkkəbliyi O(n*n), burada n*n verilmiş matrisin ölçüsüdür.

Kosmik Mürəkkəblik

Biz yalnız dörd dəyişəndən istifadə edirik kosmik mürəkkəblik O(1) olur.

Translate »