1. 题目背景与核心需求解析LeetCode 2946这道题出现在周赛环境中考察的是对矩阵操作和算法效率的把握。题目要求我们判断两个矩阵是否可以通过循环移位操作相互转换。所谓循环移位指的是将矩阵的某一行或某一列的所有元素整体移动k个位置超出边界的元素从另一端重新进入。这个题目在真实面试中具有典型意义——它考察了以下几个关键能力对矩阵基础操作的熟练程度算法设计时边界条件的处理能力时间复杂度与空间复杂度的权衡意识Python语言中高效处理矩阵的技巧我在第一次接触这道题时最困惑的是如何高效实现行列的循环移位以及如何避免不必要的重复计算。经过多次优化后最终找到了一个时间复杂度O(n^2)的解决方案下面将详细拆解思考过程。2. 矩阵循环移位的本质理解2.1 循环移位的数学表达循环移位操作可以形式化定义为对于矩阵的第i行右移k次相当于将元素从位置j移动到(jk)%n对于第j列下移k次相当于将元素从位置i移动到(ik)%m。这里的n和m分别表示矩阵的列数和行数。举个例子对于一个3x3矩阵1 2 3 4 5 6 7 8 9将其第一行右移1位后变为3 1 2 4 5 6 7 8 92.2 移位操作的等价性判断判断两个矩阵是否可以通过循环移位相互转换关键在于发现移位操作不会改变矩阵的相对结构。具体来说行移位只会改变行内元素的相对位置不会改变列方向上的元素组合列移位只会改变列内元素的相对位置不会改变行方向上的元素组合任何行/列移位都是可逆的操作基于这些观察我们可以得出一个重要结论如果矩阵A能通过循环移位变成矩阵B那么A的每一行元素组成的多重集合必须与B的某一行相同A的每一列元素组成的多重集合必须与B的某一列相同这个结论将是我们算法设计的理论基础。3. 算法设计与实现细节3.1 基础解法暴力枚举最直观的思路是尝试所有可能的行和列移位组合def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 检查行是否匹配 for i in range(m): row mat[i] found False for k in range(n): shifted row[k:] row[:k] if shifted target[i]: found True break if not found: return False # 检查列是否匹配 for j in range(n): col [mat[i][j] for i in range(m)] target_col [target[i][j] for i in range(m)] found False for k in range(m): shifted col[k:] col[:k] if shifted target_col: found True break if not found: return False return True这个解法的时间复杂度是O(m^2 n^2)在m和n较大时比如1000x1000的矩阵会非常低效。3.2 优化解法多重集合比较基于前面的理论观察我们可以先检查行和列的多重集合是否匹配from collections import defaultdict def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 检查行多重集合 mat_rows [tuple(sorted(row)) for row in mat] target_rows [tuple(sorted(row)) for row in target] if sorted(mat_rows) ! sorted(target_rows): return False # 检查列多重集合 mat_cols [] target_cols [] for j in range(n): mat_col [mat[i][j] for i in range(m)] target_col [target[i][j] for i in range(m)] mat_cols.append(tuple(sorted(mat_col))) target_cols.append(tuple(sorted(target_col))) if sorted(mat_cols) ! sorted(target_cols): return False return True这个版本的时间复杂度降到了O(mn log n mn log m)因为需要对每行每列进行排序。3.3 最优解法行模式匹配进一步观察可以发现我们实际上只需要找到一个基准行然后确定其他行相对于这个基准行的移位量即可def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 找到第一行的移位量k first_row mat[0] target_first_row target[0] try: k (target_first_row.index(first_row[0]) - 0) % n except ValueError: return False # 检查所有行是否匹配这个k for i in range(m): shifted_row mat[i][k:] mat[i][:k] if shifted_row ! target[i]: return False # 检查列是否匹配 for j in range(n): col [mat[i][(j - k) % n] for i in range(m)] target_col [target[i][j] for i in range(m)] if col ! target_col: return False return True这个算法的时间复杂度是O(mn)是最优的解法。4. Python实现中的关键技巧4.1 矩阵转置的高效实现在处理列操作时常规的做法是使用列表推导式提取列col [mat[i][j] for i in range(m)]但在Python中使用zip函数转置矩阵更为高效transposed list(zip(*mat)) # 获取第j列 col transposed[j]4.2 循环移位的简洁写法Python的切片操作非常适合实现循环移位# 右移k位 shifted row[k:] row[:k] # 左移k位 shifted row[-k:] row[:-k]4.3 避免不必要的列表创建在比较行和列时直接使用生成器表达式而非创建临时列表可以节省内存# 不推荐的写法 if [mat[i][j] for i in range(m)] [target[i][j] for i in range(m)]: pass # 推荐的写法 if all(mat[i][j] target[i][j] for i in range(m)): pass5. 常见错误与调试技巧5.1 边界条件处理在实现循环移位时容易忽略k大于行长度的case。正确的做法是使用模运算k k % n # 对于行移位 k k % m # 对于列移位5.2 空矩阵处理题目没有明确说明是否会出现空矩阵但好的习惯是处理这种边界情况if not mat or not mat[0]: return not target or not target[0]5.3 元素类型不一致虽然题目通常保证输入是整数矩阵但实际编码时要考虑类型一致性if int(mat[i][j]) ! int(target[i][j]): return False6. 性能优化实战6.1 提前终止检查在发现任何不匹配的行或列时可以立即返回False避免不必要的计算for i in range(m): if tuple(sorted(mat[i])) ! tuple(sorted(target[i])): return False6.2 使用集合加速初步检查在正式比较前可以先检查两个矩阵的元素是否完全相同if {x for row in mat for x in row} ! {x for row in target for x in row}: return False6.3 缓存排序结果对于大型矩阵可以缓存行的排序结果sorted_rows_mat [tuple(sorted(row)) for row in mat] sorted_rows_target [tuple(sorted(row)) for row in target] if sorted(sorted_rows_mat) ! sorted(sorted_rows_target): return False7. 测试用例设计完整的解决方案应该通过以下测试用例相同矩阵mat [[1,2],[3,4]] target [[1,2],[3,4]] assert isSimilar(mat, target)行移位mat [[1,2,3],[4,5,6]] target [[3,1,2],[6,4,5]] assert isSimilar(mat, target)列移位mat [[1,2],[3,4],[5,6]] target [[2,1],[4,3],[6,5]] assert isSimilar(mat, target)不匹配矩阵mat [[1,2],[3,4]] target [[1,3],[2,4]] assert not isSimilar(mat, target)空矩阵mat [] target [] assert isSimilar(mat, target)8. 复杂度分析与对比让我们对比三种解法的性能解法时间复杂度空间复杂度适用场景暴力枚举O(m^2 n^2)O(m n)小矩阵(m,n 100)多重集合O(mn log n mn log m)O(mn)中等矩阵(m,n 1000)行模式匹配O(mn)O(1)任意大小矩阵在实际面试中建议从暴力解法开始逐步优化到最优解并清楚说明每步优化的思路。9. 实际工程中的应用场景虽然这是一个算法题但类似的思想在以下场景中有实际应用图像处理中的循环卷积密码学中的置换操作数据库中的循环冗余检查分布式系统中的数据分片验证理解矩阵的循环移位性质有助于我们在这些领域设计更高效的算法。10. 扩展思考如果题目改为允许任意行和列的独立移位而不需要所有行/列移动相同距离问题会变得更加复杂。这种情况下我们需要对每行找到其在目标矩阵中的对应行确定每行的移位量验证这些移位量是否一致即所有行的移位量相同这实际上将问题转化为了一个图匹配问题可以使用并查集等数据结构来解决。
1. 题目背景与核心需求解析LeetCode 2946这道题出现在周赛环境中考察的是对矩阵操作和算法效率的把握。题目要求我们判断两个矩阵是否可以通过循环移位操作相互转换。所谓循环移位指的是将矩阵的某一行或某一列的所有元素整体移动k个位置超出边界的元素从另一端重新进入。这个题目在真实面试中具有典型意义——它考察了以下几个关键能力对矩阵基础操作的熟练程度算法设计时边界条件的处理能力时间复杂度与空间复杂度的权衡意识Python语言中高效处理矩阵的技巧我在第一次接触这道题时最困惑的是如何高效实现行列的循环移位以及如何避免不必要的重复计算。经过多次优化后最终找到了一个时间复杂度O(n^2)的解决方案下面将详细拆解思考过程。2. 矩阵循环移位的本质理解2.1 循环移位的数学表达循环移位操作可以形式化定义为对于矩阵的第i行右移k次相当于将元素从位置j移动到(jk)%n对于第j列下移k次相当于将元素从位置i移动到(ik)%m。这里的n和m分别表示矩阵的列数和行数。举个例子对于一个3x3矩阵1 2 3 4 5 6 7 8 9将其第一行右移1位后变为3 1 2 4 5 6 7 8 92.2 移位操作的等价性判断判断两个矩阵是否可以通过循环移位相互转换关键在于发现移位操作不会改变矩阵的相对结构。具体来说行移位只会改变行内元素的相对位置不会改变列方向上的元素组合列移位只会改变列内元素的相对位置不会改变行方向上的元素组合任何行/列移位都是可逆的操作基于这些观察我们可以得出一个重要结论如果矩阵A能通过循环移位变成矩阵B那么A的每一行元素组成的多重集合必须与B的某一行相同A的每一列元素组成的多重集合必须与B的某一列相同这个结论将是我们算法设计的理论基础。3. 算法设计与实现细节3.1 基础解法暴力枚举最直观的思路是尝试所有可能的行和列移位组合def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 检查行是否匹配 for i in range(m): row mat[i] found False for k in range(n): shifted row[k:] row[:k] if shifted target[i]: found True break if not found: return False # 检查列是否匹配 for j in range(n): col [mat[i][j] for i in range(m)] target_col [target[i][j] for i in range(m)] found False for k in range(m): shifted col[k:] col[:k] if shifted target_col: found True break if not found: return False return True这个解法的时间复杂度是O(m^2 n^2)在m和n较大时比如1000x1000的矩阵会非常低效。3.2 优化解法多重集合比较基于前面的理论观察我们可以先检查行和列的多重集合是否匹配from collections import defaultdict def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 检查行多重集合 mat_rows [tuple(sorted(row)) for row in mat] target_rows [tuple(sorted(row)) for row in target] if sorted(mat_rows) ! sorted(target_rows): return False # 检查列多重集合 mat_cols [] target_cols [] for j in range(n): mat_col [mat[i][j] for i in range(m)] target_col [target[i][j] for i in range(m)] mat_cols.append(tuple(sorted(mat_col))) target_cols.append(tuple(sorted(target_col))) if sorted(mat_cols) ! sorted(target_cols): return False return True这个版本的时间复杂度降到了O(mn log n mn log m)因为需要对每行每列进行排序。3.3 最优解法行模式匹配进一步观察可以发现我们实际上只需要找到一个基准行然后确定其他行相对于这个基准行的移位量即可def isSimilar(mat, target): m, n len(mat), len(mat[0]) # 找到第一行的移位量k first_row mat[0] target_first_row target[0] try: k (target_first_row.index(first_row[0]) - 0) % n except ValueError: return False # 检查所有行是否匹配这个k for i in range(m): shifted_row mat[i][k:] mat[i][:k] if shifted_row ! target[i]: return False # 检查列是否匹配 for j in range(n): col [mat[i][(j - k) % n] for i in range(m)] target_col [target[i][j] for i in range(m)] if col ! target_col: return False return True这个算法的时间复杂度是O(mn)是最优的解法。4. Python实现中的关键技巧4.1 矩阵转置的高效实现在处理列操作时常规的做法是使用列表推导式提取列col [mat[i][j] for i in range(m)]但在Python中使用zip函数转置矩阵更为高效transposed list(zip(*mat)) # 获取第j列 col transposed[j]4.2 循环移位的简洁写法Python的切片操作非常适合实现循环移位# 右移k位 shifted row[k:] row[:k] # 左移k位 shifted row[-k:] row[:-k]4.3 避免不必要的列表创建在比较行和列时直接使用生成器表达式而非创建临时列表可以节省内存# 不推荐的写法 if [mat[i][j] for i in range(m)] [target[i][j] for i in range(m)]: pass # 推荐的写法 if all(mat[i][j] target[i][j] for i in range(m)): pass5. 常见错误与调试技巧5.1 边界条件处理在实现循环移位时容易忽略k大于行长度的case。正确的做法是使用模运算k k % n # 对于行移位 k k % m # 对于列移位5.2 空矩阵处理题目没有明确说明是否会出现空矩阵但好的习惯是处理这种边界情况if not mat or not mat[0]: return not target or not target[0]5.3 元素类型不一致虽然题目通常保证输入是整数矩阵但实际编码时要考虑类型一致性if int(mat[i][j]) ! int(target[i][j]): return False6. 性能优化实战6.1 提前终止检查在发现任何不匹配的行或列时可以立即返回False避免不必要的计算for i in range(m): if tuple(sorted(mat[i])) ! tuple(sorted(target[i])): return False6.2 使用集合加速初步检查在正式比较前可以先检查两个矩阵的元素是否完全相同if {x for row in mat for x in row} ! {x for row in target for x in row}: return False6.3 缓存排序结果对于大型矩阵可以缓存行的排序结果sorted_rows_mat [tuple(sorted(row)) for row in mat] sorted_rows_target [tuple(sorted(row)) for row in target] if sorted(sorted_rows_mat) ! sorted(sorted_rows_target): return False7. 测试用例设计完整的解决方案应该通过以下测试用例相同矩阵mat [[1,2],[3,4]] target [[1,2],[3,4]] assert isSimilar(mat, target)行移位mat [[1,2,3],[4,5,6]] target [[3,1,2],[6,4,5]] assert isSimilar(mat, target)列移位mat [[1,2],[3,4],[5,6]] target [[2,1],[4,3],[6,5]] assert isSimilar(mat, target)不匹配矩阵mat [[1,2],[3,4]] target [[1,3],[2,4]] assert not isSimilar(mat, target)空矩阵mat [] target [] assert isSimilar(mat, target)8. 复杂度分析与对比让我们对比三种解法的性能解法时间复杂度空间复杂度适用场景暴力枚举O(m^2 n^2)O(m n)小矩阵(m,n 100)多重集合O(mn log n mn log m)O(mn)中等矩阵(m,n 1000)行模式匹配O(mn)O(1)任意大小矩阵在实际面试中建议从暴力解法开始逐步优化到最优解并清楚说明每步优化的思路。9. 实际工程中的应用场景虽然这是一个算法题但类似的思想在以下场景中有实际应用图像处理中的循环卷积密码学中的置换操作数据库中的循环冗余检查分布式系统中的数据分片验证理解矩阵的循环移位性质有助于我们在这些领域设计更高效的算法。10. 扩展思考如果题目改为允许任意行和列的独立移位而不需要所有行/列移动相同距离问题会变得更加复杂。这种情况下我们需要对每行找到其在目标矩阵中的对应行确定每行的移位量验证这些移位量是否一致即所有行的移位量相同这实际上将问题转化为了一个图匹配问题可以使用并查集等数据结构来解决。
