What is the key insight for Matrix Similarity After Cyclic Shifts?

The main insight is that after n shifts a row returns to its original state, so only k % n shifts need to be simulated.

How do I handle even and odd row shifts?

Even-indexed rows are shifted left, odd-indexed rows are shifted right, and this pattern repeats for k steps.

Can I optimize space for this problem?

Yes, you can perform in-place shifts and compare rows to avoid extra memory allocation for the matrix copy.

Does the problem require simulating all k steps?

No, only the effective shifts k % n are necessary because the matrix repeats every n shifts.

What array plus math techniques are used here?

The techniques involve modular arithmetic to reduce shifts and array manipulation to simulate left and right cyclic shifts efficiently.

#2946

Easy

auto_awesome数组·数学

LeetCode 题解工作台

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

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。矩阵行的下标是从 0 开始的。进行下面操作 k 次：偶数行（0, 2, 4, ...）循环向左移动。奇数行（1, 3, 5, ...）循环向右移动。如果经过 k 步后的最终修改矩阵与原始矩阵相同，则返…

数组数学矩阵模拟

题目描述

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。矩阵行的下标是从 0 开始的。

进行下面操作 k 次：

偶数行（0, 2, 4, ...）循环向左移动。

奇数行（1, 3, 5, ...）循环向右移动。

如果经过 k 步后的最终修改矩阵与原始矩阵相同，则返回 true，否则返回 false。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

输出：false

解释：

在每一步中，行 0 和行 2（偶数下标）进行左移，行 1（奇数下标）进行右移。

示例 2：

输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

输出：true

解释：

示例 3：

输入：mat = [[2,2],[2,2]], k = 3

输出：true

解释：

矩阵中的所有值都相等，即使进行循环移位，矩阵也会保持不变。

提示：

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

lightbulb

解题思路

方法一：模拟

我们遍历矩阵的每个元素，判断其在循环移位后的位置是否与原位置的元素相同。

对于奇数行，我们将元素向右移动 $k$ 个位置，因此元素 $(i, j)$ 在循环移位后的位置为 $(i, (j + k) \bmod n)$ ，其中 $n$ 是矩阵的列数。

对于偶数行，我们将元素向左移动 $k$ 个位置，因此元素 $(i, j)$ 在循环移位后的位置为 $(i, (j - k + n) \bmod n)$ 。

如果在遍历过程中发现有任何一个元素在循环移位后的位置与原位置的元素不同，则返回 $\text{false}$ 。如果遍历完成后所有元素都相同，则返回 $\text{true}$ 。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        n = len(mat[0])
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                if i % 2 == 1 and x != mat[i][(j + k) % n]:
                    return False
                if i % 2 == 0 and x != mat[i][(j - k + n) % n]:
                    return False
        return True

speed

复杂度分析

指标	值
时间	complexity is O(m * n) for m rows and n columns, as each row may be shifted up to n positions. Space complexity is O(m * n) if a copy of the matrix is used for comparison, or O(1) if shifts are done in place.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should identify that k can be reduced modulo n to simplify computation.
question_mark
Look for understanding of row-wise shift direction based on index parity.
question_mark
Expect efficient comparison with original matrix rather than simulating all k shifts explicitly.

warning

常见陷阱

外企场景

error
Forgetting to reduce k modulo the row length leads to unnecessary repeated shifts.
error
Shifting the wrong direction for even or odd rows will produce incorrect results.
error
Assuming uniform rows are trivial without verifying the shift direction logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Matrix similarity after cyclic column shifts instead of row shifts.
arrow_right_alt
Allowing variable shift directions for each row, specified in an input array.
arrow_right_alt
Checking similarity for submatrices after cyclic row shifts rather than the entire matrix.

help

常见问题

外企场景

继续练习

#2961 双模幂运算 #2965 找出缺失和重复的数字 #3044 出现频率最高的质数