Easy

题目描述

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

提示： 你可以将 k 次移位减少到 (k % n) 次移位，因为经过 n 次移位后，矩阵会变得与初始矩阵相似。

解题思路

这道题的关键是理解循环移位的本质和周期性。

基本思路：

  1. 对于长度为 n 的数组，经过 n 次循环移位后会回到原状态
  2. 因此我们可以将 k 优化为 k % n，避免不必要的计算
  3. 对每一行应用相应的移位操作，然后检查是否与原矩阵相同

具体实现：

  • 遍历每一行，根据行号的奇偶性决定移位方向
  • 偶数行：循环左移 k % n 位
  • 奇数行：循环右移 k % n 位
  • 比较移位后的矩阵与原矩阵是否相同

优化点： 由于题目提示，我们可以利用移位的周期性来优化。对于长度为 n 的行，k % n 次移位等效于 k 次移位。这样可以避免多余的计算。

时间复杂度分析： 需要遍历整个矩阵并对每行进行移位操作，总体复杂度为 O(m×n)。

代码实现

class Solution {
public:
    bool areSimilar(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        
        for (int i = 0; i < m; i++) {
            int shifts = k % n;
            if (shifts == 0) continue;
            
            vector<int> original = mat[i];
            vector<int> shifted(n);
            
            if (i % 2 == 0) {
                // 偶数行左移
                for (int j = 0; j < n; j++) {
                    shifted[j] = mat[i][(j + shifts) % n];
                }
            } else {
                // 奇数行右移
                for (int j = 0; j < n; j++) {
                    shifted[j] = mat[i][(j - shifts + n) % n];
                }
            }
            
            if (shifted != original) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        m, n = len(mat), len(mat[0])
        
        for i in range(m):
            shifts = k % n
            if shifts == 0:
                continue
            
            original = mat[i][:]
            
            if i % 2 == 0:
                # 偶数行左移
                shifted = mat[i][shifts:] + mat[i][:shifts]
            else:
                # 奇数行右移
                shifted = mat[i][-shifts:] + mat[i][:-shifts]
            
            if shifted != original:
                return False
        
        return True

public class Solution {
    public bool AreSimilar(int[][] mat, int k) {
        int m = mat.Length, n = mat[0].Length;
        
        for (int i = 0; i < m; i++) {
            int shifts = k % n;
            if (shifts == 0) continue;
            
            int[] original = new int[n];
            Array.Copy(mat[i], original, n);
            
            int[] shifted = new int[n];
            
            if (i % 2 == 0) {
                // 偶数行左移
                for (int j = 0; j < n; j++) {
                    shifted[j] = mat[i][(j + shifts) % n];
                }
            } else {
                // 奇数行右移
                for (int j = 0; j < n; j++) {
                    shifted[j] = mat[i][(j - shifts + n) % n];
                }
            }
            
            for (int j = 0; j < n; j++) {
                if (shifted[j] != original[j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var areSimilar = function(mat, k) {
    const m = mat.length;
    const n = mat[0].length;
    
    // Optimize k by taking modulo n since shifts repeat after n steps
    k = k % n;
    
    // If k is 0, matrix remains unchanged
    if (k === 0) return true;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let newJ;
            if (i % 2 === 0) {
                // Even row - left shift
                newJ = (j + k) % n;
            } else {
                // Odd row - right shift
                newJ = (j - k + n) % n;
            }
            
            if (mat[i][j] !== mat[i][newJ]) {
                return false;
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m×n) - 需要遍历矩阵的每个元素进行移位和比较
空间复杂度O(n) - 需要额外空间存储移位后的行数据