Easy

题目描述

给你两个大小为 n x n 的二进制矩阵 mat 和 target，如果能够使 mat 经过若干次 90 度顺时针旋转得到 target，则返回 true；否则，返回 false。

示例 1：

输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：我们可以将 mat 顺时针旋转 90 度，使其等于 target。

示例 2：

输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无论如何旋转 mat，都无法使其等于 target。

示例 3：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：我们可以将 mat 顺时针旋转 90 度两次，使其等于 target。

提示：

  • n == mat.length == target.length
  • n == mat[i].length == target[i].length
  • 1 <= n <= 10
  • mat[i][j] 和 target[i][j] 都是 0 或 1

解题思路

这道题的核心思路是：一个矩阵最多只需要旋转4次（每次90度）就能回到原状，所以我们只需要检查矩阵旋转0、1、2、3次后是否与目标矩阵相等。

解法分析：

  1. 暴力模拟法：直接模拟矩阵的旋转过程，每次将矩阵顺时针旋转90度，然后检查是否等于目标矩阵。矩阵90度顺时针旋转的规律是：新矩阵[j][n-1-i] = 原矩阵[i][j]

  2. 优化思路：由于最多只需要旋转4次，我们可以预先生成所有可能的旋转结果，然后逐一比较。

推荐解法： 暴力模拟法，代码简洁且易于理解。

具体步骤：

  • 检查当前矩阵是否等于目标矩阵
  • 如果不等，旋转90度后继续检查
  • 重复最多4次，如果都不匹配则返回false

时间复杂度主要取决于矩阵比较和旋转操作，由于n最大为10，效率完全可以接受。

代码实现

class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        for (int i = 0; i < 4; i++) {
            if (mat == target) return true;
            rotate90(mat);
        }
        return false;
    }
    
private:
    void rotate90(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 转置
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 水平翻转
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        for _ in range(4):
            if mat == target:
                return True
            mat = self.rotate90(mat)
        return False
    
    def rotate90(self, matrix):
        n = len(matrix)
        # 转置后水平翻转
        return [[matrix[n-1-j][i] for j in range(n)] for i in range(n)]

public class Solution {
    public bool FindRotation(int[][] mat, int[][] target) {
        for (int i = 0; i < 4; i++) {
            if (AreEqual(mat, target)) return true;
            Rotate90(mat);
        }
        return false;
    }
    
    private void Rotate90(int[][] matrix) {
        int n = matrix.Length;
        // 转置
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 水平翻转
        for (int i = 0; i < n; i++) {
            Array.Reverse(matrix[i]);
        }
    }
    
    private bool AreEqual(int[][] mat1, int[][] mat2) {
        int n = mat1.Length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat1[i][j] != mat2[i][j]) return false;
            }
        }
        return true;
    }
}

var findRotation = function(mat, target) {
    for (let i = 0; i < 4; i++) {
        if (areEqual(mat, target)) return true;
        rotate90(mat);
    }
    return false;
};

function rotate90(matrix) {
    const n = matrix.length;
    // 转置
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    // 水平翻转
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
}

function areEqual(mat1, mat2) {
    const n = mat1.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (mat1[i][j] !== mat2[i][j]) return false;
        }
    }
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最多旋转4次，每次旋转和比较都是O(n²)，常数因子
空间复杂度O(1)原地旋转，只使用常数额外空间

相关题目