Algoritma untuk Menentukan Apakah Matriks Dapat Diperoleh Dengan Rotasi

Diberikan dua matriks biner nxn mat dan target, kembalikan true jika memungkinkan untuk membuat mat sama dengan target dengan memutar mat dalam peningkatan 90 derajat, atau salah sebaliknya.

Petunjuk:
Berapa jumlah rotasi maksimum yang harus Anda periksa?
Apakah ada rumus yang dapat Anda gunakan untuk memutar matriks 90 derajat?

C++ Putar dan Periksa

Kita dapat mendefinisikan fungsi untuk memutar matriks sebesar 90 derajat searah jarum jam: pertama-tama transpos matriks, lalu balikkan setiap baris. Dan kemudian, hanya perlu memeriksa paling banyak empat rotasi:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        function<void(vector<vector<int>>&)> rotate = [](vector<vector<int>>& M) {
            int rows = static_cast<int>(M.size());
            int cols = static_cast<int>(M[0].size());
            // transpose the matrix
            for (int i = 0; i < rows; ++ i) {
                for (int j = 0; j < i; ++ j) {
                    swap(M[i][j], M[j][i]);
                }
            }
            // then reverse each row
            for_each(begin(M), end(M), [](auto &a) {
                reverse(begin(a), end(a));
            });
        };
        for (int i = 0; i < 4; ++ i) {
            if (mat == target) return true;
            rotate(mat);
        }
        return false;
    }
};
class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        function<void(vector<vector<int>>&)> rotate = [](vector<vector<int>>& M) {
            int rows = static_cast<int>(M.size());
            int cols = static_cast<int>(M[0].size());
            // transpose the matrix
            for (int i = 0; i < rows; ++ i) {
                for (int j = 0; j < i; ++ j) {
                    swap(M[i][j], M[j][i]);
                }
            }
            // then reverse each row
            for_each(begin(M), end(M), [](auto &a) {
                reverse(begin(a), end(a));
            });
        };
        for (int i = 0; i < 4; ++ i) {
            if (mat == target) return true;
            rotate(mat);
        }
        return false;
    }
};

Di sini, kami menggunakan std::for_each untuk membalik setiap baris matriks. Kompleksitas waktu adalah O(NM) di mana N dan M adalah jumlah baris dan kolom matriks. Rotasi dilakukan di tempat dan dengan demikian kompleksitas ruang adalah O(1).

Putar dan Periksa Matriks dengan Python

Dengan Python, kita dapat menggunakan [::-1] untuk membalikkan vektor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate(M):
            if not M:
                return M
            rows, cols = len(M), len(M[0])
            for i in range(rows):
                for j in range(i):
                    M[i][j], M[j][i] = M[j][i], M[i][j]
            for i in range(rows):
                M[i] = M[i][::-1]
            return M
        for i in range(4):
            if mat == target:
                return True
            rotate(mat)
        return False
class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate(M):
            if not M:
                return M
            rows, cols = len(M), len(M[0])
            for i in range(rows):
                for j in range(i):
                    M[i][j], M[j][i] = M[j][i], M[i][j]
            for i in range(rows):
                M[i] = M[i][::-1]
            return M
        for i in range(4):
            if mat == target:
                return True
            rotate(mat)
        return False

Kompleksitas ruang dan waktu yang sama. Transpose + reverse membuat rotasi.

–EOF (Blog Komputasi & Teknologi Terbaik) —

Peringkat Bintang GD
Memuat…

535 kata
Postingan terakhir: Teaching Kids Programming – Algoritma Pencarian Kedalaman Pertama untuk Menghitung Garis Vertikal di Pohon Biner
Postingan Berikutnya: Mengajar Pemrograman Anak – Tanda Hasil Kali Array