循环移位后的矩阵相似检查

难度: Easy

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。请你将矩阵中的奇数行循环右移 k 次，偶数行循环左移 k 次。

如果初始矩阵和最终矩阵完全相同，则返回 true ，否则返回 false 。

示例 1：

输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
输出：true
解释：


初始矩阵如图一所示。
图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。
图三是经过两次循环移位后的最终矩阵状态，与初始矩阵相同。
因此，返回 true 。

示例 2：

输入：mat = [[2,2],[2,2]], k = 3
输出：true
解释：由于矩阵中的所有值都相等，即使进行循环移位，矩阵仍然保持不变。因此，返回 true 。

示例 3：

输入：mat = [[1,2]], k = 1
输出：false
解释：循环移位一次后，mat = [[2,1]]，与初始矩阵不相等。因此，返回 false 。

提示：

1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50

Submission

运行时间: 26 ms

内存: 16.1 MB

from typing import List

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        def rotate_row(row: List[int], shift: int, direction: str) -> List[int]:
            n = len(row)
            if direction == 'right':
                return row[-shift % n:] + row[:-shift % n]
            else:
                return row[shift % n:] + row[:shift % n]
        
        # 创建一个深拷贝的原始矩阵，用于后续比较
        original_mat = [[x for x in row] for row in mat]
        
        m, n = len(mat), len(mat[0])
        
        # 对矩阵的每一行进行循环移位操作
        for i in range(m):
            if i % 2 == 0:
                # 偶数行循环左移 k 次
                mat[i] = rotate_row(mat[i], k, 'left')
            else:
                # 奇数行循环右移 k 次
                mat[i] = rotate_row(mat[i], k, 'right')
        
        # 比较变换后的矩阵和原始矩阵是否相同
        return mat == original_mat

# 测试代码
solution = Solution()
print(solution.areSimilar([[1,2,1,2],[5,5,5,5],[6,3,6,3]], 2))  # True
print(solution.areSimilar([[2,2],[2,2]], 3))  # True
print(solution.areSimilar([[1,2]], 1))  # False

Explain

题解的核心思路是首先对矩阵中的奇数行和偶数行分别进行右移和左移操作，然后比较操作后的矩阵和原始矩阵是否完全相同。首先定义一个旋转行的函数，根据行移动的方向（左或右）和移动的次数来计算新的行顺序。循环遍历矩阵中的每一行，根据行的索引是奇数还是偶数，使用旋转函数进行相应的行移动。最后，将旋转后的矩阵和原始矩阵进行比较，如果两者相等，则返回 true，否则返回 false。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

from typing import List

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        def rotate_row(row: List[int], shift: int, direction: str) -> List[int]:
            n = len(row)
            # 根据方向和偏移量计算新的行顺序
            if direction == 'right':
                return row[-shift % n:] + row[:-shift % n]
            else:
                return row[shift % n:] + row[:shift % n]
        
        # 创建一个深拷贝的原始矩阵，用于后续比较
        original_mat = [[x for x in row] for row in mat]
        
        m, n = len(mat), len(mat[0])
        
        # 对矩阵的每一行进行循环移位操作
        for i in range(m):
            if i % 2 == 0:
                # 偶数行循环左移 k 次
                mat[i] = rotate_row(mat[i], k, 'left')
            else:
                # 奇数行循环右移 k 次
                mat[i] = rotate_row(mat[i], k, 'right')
        
        # 比较变换后的矩阵和原始矩阵是否相同
        return mat == original_mat

# 测试代码
solution = Solution()
print(solution.areSimilar([[1,2,1,2],[5,5,5,5],[6,3,6,3]], 2))  # True
print(solution.areSimilar([[2,2],[2,2]], 3))  # True
print(solution.areSimilar([[1,2]], 1))  # False

Explore

在题目中，选择对偶数行左移和奇数行右移是基于对称性的考虑，这样的操作可以帮助我们在实现时通过统一的处理逻辑来简化编码和调试。实际上，题目的要求是可以自由设定的，左移和右移只是为了达到题目要求的循环移位效果。这种分别处理偶数行和奇数行的方法，可以让我们更加清晰地观察到每一行的变化，同时也是一种有效的避免错误和确认变化是否正确的手段。

在`rotate_row`函数中使用取模操作是为了处理移动次数大于行长度的情况，避免进行无效的全圈循环，从而提高效率。取模操作确保移动次数被简化为一个周期以内的移动，即使移动次数是行长度的整数倍或更多，实际效果相当于没有移动。这样不仅减少了计算和移动的开销，而且代码更加简洁高效。例如，如果一行有5个元素，移动10次和不移动是等效的，通过取模操作可以直接得出这一结果，避免无意义的计算和处理。

在本题解中，我们创建了原始矩阵的深拷贝主要是为了保留一个未修改的版本，以便与修改后的矩阵进行比较，验证是否相同。深拷贝的原始矩阵作为一个不变的参照物，确保我们有一个准确无误的比较基准。对原始矩阵进行操作而不是副本，是为了避免额外的内存使用和可能的性能开销。此外，直接在原矩阵上操作可以减少数据复制的次数，从而在保持代码逻辑清晰的同时也优化性能。