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

matrix, https://leetcode.cn/problems/matrix-similarity-after-cyclic-shifts/

给你一个下标从 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

这个问题可以通过观察循环移位的性质来简化。

核心思路

1. 循环移位的等价性： 对于一个长度为 $n$ 的序列，将其循环左移 $k$ 次或循环右移 $k$ 次后，如果要求与原序列完全相同，其本质条件是相同的：序列必须具有周期性。

   • 如果向左移 $k$ 位：原位置 $j$ 的元素会移动到 $(j-k)(\mathrm{mod}n)$，或者说新位置 $j$ 的元素来源于原位置 $(j+k)(\mathrm{mod}n)$。
   • 如果向右移 $k$ 位：原位置 $j$ 的元素会移动到 $(j+k)(\mathrm{mod}n)$。

2. 判断条件： 无论奇数行右移还是偶数行左移，矩阵保持不变的充要条件是：对于矩阵中的每一行 mat[i]，其中的每个元素 mat[i][j] 都必须等于它移动 $k$ 个位置后指向的元素。 即：mat[i][j] == mat[i][(j + k) % n]。 注：这里的 $n$ 是列数。由于 $k$ 可能大于 $n$，我们可以先取模 k %= n，如果不取模直接使用 (j + k) % n 结果也是正确的。

   代码实现

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        m = len(mat)
        n = len(mat[0])
        
        # 预处理 k，因为移动 n 次等于没移
        k %= n
        if k == 0:
            return True
        
        for i in range(m):
            for j in range(n):
                # 检查当前元素与循环移动 k 位后的元素是否相等
                # 无论左移还是右移，只要满足 mat[i][j] == mat[i][(j + k) % n]，
                # 该行在循环移动 k 次后就会保持不变。
                if mat[i][j] != mat[i][(j + k) % n]:
                    return False
        
        return True

复杂度分析

• 时间复杂度：$O(m\times n)$。我们需要遍历矩阵中的每一个元素一次。
• 空间复杂度：$O(1)$。只使用了常数级别的额外空间。

为什么不需要区分左右移？

• 偶数行（左移）：要求 mat[i][j] 移动后回到原位，即 mat[i][j] 应该等于移动前在 (j + k) % n 位置的数。
• 奇数行（右移）：要求 mat[i][j] 移动后回到原位，即 mat[i][j] 应该等于移动前在 (j - k) % n 位置的数。
• 实际上，如果一个数组满足 row[j] == row[(j + k) % n]，那么它同时也必然满足 row[j] == row[(j - k) % n]（这只是索引的对称性）。因此，统一使用 (j + k) % n 进行检查即可涵盖两种情况。