LeetCode 1886题解：矩阵旋转匹配算法与优化-尧图网站建设

1. 题目解析与核心思路

1.1 题目要求拆解

LeetCode 1886题要求我们判断两个n x n的矩阵是否可以通过90度倍数的旋转相互转换。具体来说，给定原始矩阵mat和目标矩阵target，我们需要确定是否存在一个旋转角度（90、180或270度），使得旋转后的mat与target完全一致。

这个题目考察的核心能力包括：

二维数组的操作能力
矩阵旋转的算法实现
边界条件的处理
空间复杂度的优化意识

1.2 矩阵旋转的数学原理

矩阵旋转90度本质上是一种线性变换。对于一个n x n矩阵，顺时针旋转90度可以通过以下两个步骤实现：

转置矩阵（行列互换）
反转每一行的元素顺序

数学表达式为：旋转后的矩阵mat_rotated[i][j] = mat[n-1-j][i]

这个性质非常重要，因为它提供了我们实现旋转操作的理论基础。理解这个原理后，我们可以推导出180度和270度旋转的等效操作。

1.3 解题思路选择

面对这个问题，我们有几种可能的解决路径：

暴力比较法：直接生成所有可能的旋转结果（最多3种），然后逐一与target比较
特征比较法：比较矩阵的某些旋转不变特征（如对角线元素）
原位旋转法：通过原地操作实现旋转，减少空间复杂度

经过分析，暴力比较法虽然时间复杂度较高（O(n^2)），但实现简单直观，适合作为首选方案。特别是考虑到n的限制（n <= 10），这种方法完全可行。

2. 算法实现与优化

2.1 基础实现方案

最直接的实现方式是编写一个旋转函数，然后依次尝试90、180、270度旋转，每次旋转后与目标矩阵比较：

def findRotation(mat, target): n = len(mat) # 0度旋转直接比较 if mat == target: return True # 尝试90、180、270度旋转 rotated = [row[:] for row in mat] # 深拷贝 for _ in range(3): rotated = rotate90(rotated) if rotated == target: return True return False def rotate90(matrix): n = len(matrix) # 转置矩阵 for i in range(n): for j in range(i, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 反转每行 for row in matrix: row.reverse() return matrix

2.2 空间复杂度优化

上面的实现每次旋转都创建了新矩阵，空间复杂度为O(n^2)。我们可以优化为原地旋转：

def findRotation(mat, target): n = len(mat) if mat == target: return True for _ in range(3): # 原地旋转90度 for i in range(n): for j in range(i, n): mat[i][j], mat[j][i] = mat[j][i], mat[i][j] for row in mat: row.reverse() if mat == target: return True return False

这种实现将空间复杂度降到了O(1)，但需要注意这会修改原始矩阵。如果要求不修改原矩阵，需要先做深拷贝。

2.3 提前终止优化

在旋转比较过程中，一旦发现某个旋转角度匹配，可以立即返回，不需要继续尝试其他角度。这在大多数情况下可以节省时间。

3. 边界条件与特殊情况处理

3.1 空矩阵处理

虽然题目保证n >= 1，但良好的编程习惯应该处理边界情况：

if not mat or not target: return False if len(mat) != len(target) or len(mat[0]) != len(target[0]): return False

3.2 单元素矩阵

当n=1时，矩阵只有一个元素，任何旋转都不会改变它：

if n == 1: return mat[0][0] == target[0][0]

3.3 完全相同的矩阵

在旋转前先进行一次直接比较，可以避免不必要的旋转操作：

if mat == target: return True

4. 算法复杂度分析

4.1 时间复杂度

最坏情况下需要尝试3次旋转，每次旋转操作需要O(n^2)时间（转置和反转各需要O(n^2)），所以总时间复杂度为O(n^2)。

4.2 空间复杂度

如果使用原地旋转，空间复杂度为O(1)；如果保留原矩阵则需要O(n^2)的额外空间。

5. 测试用例设计

全面的测试用例应该包括：

常规情况：

mat = [[1,2],[3,4]] target = [[3,1],[4,2]] # 预期：True（90度旋转匹配）

多角度匹配：

mat = [[1,1],[1,1]] target = [[1,1],[1,1]] # 预期：True（任何旋转都匹配）

不匹配情况：

mat = [[1,2],[3,4]] target = [[4,3],[2,1]] # 预期：False

边界情况：

mat = [[1]] target = [[1]] # 预期：True

大矩阵测试（验证性能）：

n = 10 mat = [[(i+j)%10 for j in range(n)] for i in range(n)] target = [row[:] for row in mat] # 旋转target 270度 for _ in range(3): target = rotate90(target) # 预期：True

6. 实际编码中的注意事项

6.1 Python中的列表复制

在Python中直接使用rotated = mat[:]或rotated = list(mat)只能实现浅拷贝，对于二维数组需要使用深拷贝：

# 正确做法 rotated = [row[:] for row in mat]

6.2 矩阵比较

Python中列表的==操作符会递归比较所有元素，但对于大矩阵可能效率不高。可以提前比较某些特征值来快速排除不匹配的情况。

6.3 旋转方向

题目没有明确说明旋转方向，通常默认为顺时针方向。如果面试中遇到，应该先确认旋转方向。

7. 扩展思考

7.1 非方阵情况

如果矩阵不是方阵（m x n），旋转操作会改变矩阵形状。这种情况下判断是否一致需要考虑更多因素。

7.2 任意角度旋转

如果题目改为判断是否可以通过任意角度旋转匹配，问题将变得复杂得多，可能需要使用图像处理中的特征匹配算法。

7.3 其他变换组合

更一般化的问题可能是判断矩阵是否可以通过旋转、翻转、平移等变换的组合相互转换。这类问题在计算机视觉和模式识别中很常见。

8. 同类题目推荐

为了加深对矩阵操作的理解，可以练习以下LeetCode题目：

1. 旋转图像
1. 螺旋矩阵
1. 矩阵置零
1. 生命游戏
1. 重塑矩阵

这些题目都涉及矩阵的各种操作，能够全面提升处理二维数组的能力。

9. 个人实战经验分享

在实际解决这个问题时，我遇到了几个值得注意的点：

旋转方向混淆：最初实现时搞混了顺时针和逆时针旋转，导致结果错误。解决方法是在纸上画出小矩阵的旋转过程，明确坐标变换规律。
原地修改问题：第一次提交时没有注意到原地旋转会修改原矩阵，导致后续测试用例失败。解决方法是在旋转前先复制矩阵。
边界条件遗漏：最初版本没有处理n=1的情况，虽然题目保证n≥1，但良好的编程习惯应该考虑所有边界情况。
Python特性利用：发现可以直接使用mat == target比较矩阵，比逐个元素比较更简洁。但要注意这在大矩阵时可能效率不高。
测试用例设计：特别设计了全相同元素的矩阵用例，验证了算法在这种特殊情况下的正确性。

这个题目虽然难度不大，但很好地训练了对二维数组的操作能力。建议初学者在解决后，尝试用不同方法实现旋转操作，并比较它们的性能差异。

资讯详情

LeetCode 1886题解：矩阵旋转匹配算法与优化