A.每日一题：2946. 循环移位后的矩阵相似检查

题目链接：2946. 循环移位后的矩阵相似检查（简单）

算法原理：

解法：模拟

1ms击败100.00%

时间复杂度O(mn)

针对每一行a

首先我们要找到左移和右移k次后的位置在哪：

n为该行一维数组的长度

右移k次：i的最终位置在(i+k)%n

左移k次：i的最终位置在(i-k)%n，由于是减法，因此需要额外+n避免负数，且k要%=n，否则会出现（0-3+2）%2=-1的情况

那么接下来就很好解决了，对每一行进行判断：

如果该行是奇数行就右移检查最终是否相同

如果该行是偶数行就左移检查最终是否相同

只要其中有一个不相同，直接返回false

优化

1ms击败100.00%

时间复杂度O(mn)

在上述式子中，如果要保证移位后的数组与原数组相同

右移要保证：a[(i+k)%n]=a[i]①

左移要保证：a[(i-k)%n]=a[i]②

其实这两个式子是等价的，因为我们把 i=(i-k)%n代入①式，会发现：

a[i%n]=a[(i-k)%n]，也就是说a[i]=a[(i-k)%n]，这正好就是①式，因此我们针对奇偶数完全可以只用这一个式子来判断

Java代码：

class Solution { public boolean areSimilar(int[][] mat, int k) { int m=mat.length; for(int i=0;i<m;i++) if(!turn(mat[i],k,i%2==1)) return false; return true; } private boolean turn(int[] a,int k,boolean odd){ int n=a.length; k%=n; int[] ret=new int[n]; if(odd) for(int i=0;i<n;i++) ret[(i+k)%n]=a[i]; else for(int i=0;i<n;i++) ret[(i-k+n)%n]=a[i]; for(int i=0;i<n;i++) if(ret[i]!=a[i]) return false; return true; } }

class Solution { //优化 public boolean areSimilar(int[][] mat, int k) { int m=mat.length; for(int i=0;i<m;i++) if(!turn(mat[i],k)) return false; return true; } private boolean turn(int[] a,int k){ int n=a.length; int[] ret=new int[n]; for(int i=0;i<n;i++) ret[(i+k)%n]=a[i]; for(int i=0;i<n;i++) if(ret[i]!=a[i]) return false; return true; } }