判断矩阵经轮转后是否一致

难度: Easy

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

示例 1：

输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。

示例 2：

输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。

示例 3：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。

提示：

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 不是 0 就是 1

Submission

运行时间: 23 ms

内存: 16.1 MB

from typing import List

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate_matrix(matrix: List[List[int]]) -> List[List[int]]:
            n = len(matrix)
            rotated_matrix = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    rotated_matrix[j][n - i - 1] = matrix[i][j]
            return rotated_matrix
        
        rotations = 0
        while rotations < 4:
            if mat == target:
                return True
            mat = rotate_matrix(mat)
            rotations += 1
        
        return False

solution = Solution()

mat1 = [[0, 1], [1, 0]]
target1 = [[1, 0], [0, 1]]
print(solution.findRotation(mat1, target1))  # Output: True

mat2 = [[0, 1], [1, 1]]
target2 = [[1, 0], [0, 1]]
print(solution.findRotation(mat2, target2))  # Output: False

mat3 = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
target3 = [[1, 1, 1], [0, 1, 0], [0, 0, 0]]
print(solution.findRotation(mat3, target3))  # Output: True

Explain

该题解的思路是通过旋转mat矩阵若干次（最多4次，因为旋转4次后矩阵会恢复原状），并在每次旋转后比较mat和target是否相等。如果在任何一次旋转后mat等于target，则返回True；如果四次旋转都完成后mat仍然不等于target，则返回False。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

from typing import List

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        def rotate_matrix(matrix: List[List[int]]) -> List[List[int]]:
            n = len(matrix)
            rotated_matrix = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    rotated_matrix[j][n - i - 1] = matrix[i][j]
            return rotated_matrix
        
        rotations = 0
        while rotations < 4:
            if mat == target:
                return True
            mat = rotate_matrix(mat)
            rotations += 1
        
        return False

solution = Solution()

mat1 = [[0, 1], [1, 0]]
target1 = [[1, 0], [0, 1]]
print(solution.findRotation(mat1, target1))  # Output: True

mat2 = [[0, 1], [1, 1]]
target2 = [[1, 0], [0, 1]]
print(solution.findRotation(mat2, target2))  # Output: False

mat3 = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
target3 = [[1, 1, 1], [0, 1, 0], [0, 0, 0]]
print(solution.findRotation(mat3, target3))  # Output: True

Explore

在矩阵旋转函数`rotate_matrix`中，通过计算新的索引位置`rotated_matrix[j][n - i - 1] = matrix[i][j]`确保旋转后的索引不会越界。此处，`i`和`j`分别遍历原矩阵的行和列，新矩阵的行索引`j`和列索引`n - i - 1`均在矩阵大小`n`的范围内。因此，通过适当的索引计算避免了越界。

矩阵比较操作是通过直接比较两个矩阵是否相等来进行的，即`mat == target`。此操作会比较两个矩阵的所有元素，确保每一个对应位置的元素都相等。因此，这一比较操作考虑了所有元素的相等性。

将矩阵旋转90度一次后，连续旋转4次将使矩阵恢复到原始状态。因此，检查矩阵是否与目标矩阵相等的操作只需要最多旋转4次。如果在4次内矩阵与目标相等，则返回True；如果4次旋转后仍不相等，则无论继续旋转多少次，矩阵状态会重复，因此返回False。

当前的方法（双层for循环）已经是旋转矩阵的一种基本且有效的实现方式，每个元素都被访问和重置一次。尽管如此，可以考虑使用原地旋转算法来减少空间复杂度，但时间复杂度仍将为O(n^2)。原地旋转涉及更复杂的索引操作和多次元素交换，但不会改变每个元素处理一次的事实。因此，就操作次数而言，优化空间有限。