How do I rotate a matrix in this problem?

To rotate the matrix, transpose it and then reverse each row. Repeat this up to three times to check all possible 90-degree rotations.

What is the time complexity of the brute force approach?

The brute force approach checks four rotations, each with a time complexity of O(n^2), so the overall complexity is O(n^2).

How do I compare matrices after rotation?

You can compare matrices element by element. If all elements match, the matrices are equal, otherwise they are not.

What if the matrix size increases?

For larger matrices, the brute force solution can be slower. Optimizing the comparison or reducing redundant rotations could help.

Why is the matrix rotation approach relevant to this problem?

The matrix rotation approach is directly related because the task asks you to determine if one matrix can be obtained from another through 90-degree rotations.

#1886

Easy

auto_awesome数组·matrix

LeetCode 题解工作台

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

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

数组矩阵

题目描述

给你两个大小为 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

lightbulb

解题思路

方法一：原地比较

我们观察矩阵的轮转规律，发现对于矩阵中的元素 $\text{mat}[i][j]$ ，它在轮转 90 度后会出现在 $\text{mat}[j][n-1-i]$ 的位置，在轮转 180 度后会出现在 $\text{mat}[n-1-i][n-1-j]$ 的位置，在轮转 270 度后会出现在 $\text{mat}[n-1-j][i]$ 的位置。

因此，我们可以用一个整数 $\textit{ok}$ 来记录当前轮转的状态，初始值为 $0b1111$ ，表示四种轮转状态都可能。对于矩阵中的每个元素，我们比较它在不同轮转状态下的位置与目标矩阵中的对应位置的元素是否相等，如果不相等，则将对应的轮转状态从 $\textit{ok}$ 中去掉。最后，如果 $\textit{ok}$ 不为零，说明至少有一种轮转状态可以使矩阵与目标矩阵一致，返回 $\textit{true}$ ；否则，返回 $\textit{false}$ 。

时间复杂度 $O(n^2)$ ，其中 $n$ 是矩阵的大小。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        n = len(mat)
        ok = 0b1111
        for i in range(n):
            for j in range(n):
                if mat[i][j] != target[i][j]:
                    ok &= ~0b0001
                if mat[j][n - 1 - i] != target[i][j]:
                    ok &= ~0b0010
                if mat[n - 1 - i][n - 1 - j] != target[i][j]:
                    ok &= ~0b0100
                if mat[n - 1 - j][i] != target[i][j]:
                    ok &= ~0b1000
                if ok == 0:
                    return False
        return ok != 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of matrix manipulation.
question_mark
Candidate implements multiple rotations efficiently.
question_mark
Candidate chooses the simplest solution if time constraints allow.

warning

常见陷阱

外企场景

error
Forgetting to handle all four rotations (0, 90, 180, 270 degrees).
error
Incorrectly checking matrix equality after rotation, leading to false negatives.
error
Overcomplicating the solution with unnecessary optimizations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the matrix is not binary, but contains other integer values?
arrow_right_alt
How would the solution change if the matrix was non-square (rectangular)?
arrow_right_alt
Can you optimize further if the matrix size is fixed and small?

help

常见问题

外企场景

继续练习

#1878 矩阵中最大的三个菱形和 #1895 最大的幻方 #1901 寻找峰值 II